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

Answer:

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 %

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 %