Question

Suppose h(k) and x(k) are both of length L = 2048. a) Find the number of real FLOPs for a fast linear convolution of h(k) with x(k). b) Find the number of real FLOPs for a direct linear convolution of h(k) with x(k). c) Express the answer to (a) as a percentage of the answer to (b).

Answer 1

number of real FLOPs for fast linear convolution is 311300 FLOPs

number of real FLOPs for direct linear convolution is 8388608 FLOPs

311300 FLOPs as a percentage of the answer to 8388608 FLOPs is 3.711 %

Step-by-step explanation:

Given data

length L = 2048

to find out

number of real FLOPs for fast linear convolution and a direct linear convolution

solution

we know here h(k) and x(k) are both of length L so

for FLOP for fast linear convolution of L point is given by

fast linear convolution = 12
`log_(2)` (2L) + 8L + 4 .................1

put here L = 2048

that is 12× (2048) × (12) + (8) × (2048) + ( 4 ) = 311300

so number of real FLOPs for fast linear convolution is 311300 FLOPs

and

FLOPs for direct linear convolution is express as

that is = 2 × L²

so put L = 2048

that is = 2 × 2048² = 8388608

so number of real FLOPs for direct linear convolution is 8388608 FLOPs

and

we have find 311300 FLOPs as a percentage of the answer to 8388608 FLOPs

so 311300/8388608 = 0.03711

311300 FLOPs as a percentage of the answer to 8388608 FLOPs is 3.711 %