1
$\begingroup$

Knowing that computing an FFT is faster if the amount of samples is a power of 2 I have always tried to pad the inputs to Matlab's FFT with zeros until the next power of 2 is achieved. Matlab's function fftfilt which implements a FIR filter with the overlap-add method does the same, selecting the FFT size as 2^nextpow2(FIR_coeff + input_signal-1).

However I realize that if the amount to be padded is too long compared to the original size this my actually be inefficient. For instance if a 130000 samples FFT was to be computed. Assuming a huge and unpractical single FFT was carried out. As the next power of 2 of 130000 is 131072 maybe despite adding 1072 zeros it would be more efficient than performing the 130000 samples FFT directly. The worst case would be having (power of 2) + 1 samples and trying to pad to the next power of 2, specially if the number of samples is large. For instance in my example having 131073 samples which next power of 2 is 262144 would add 131071 zeros! Starting at which point in terms of ratios between original size and padding size would it be better not to pad? I'm looking for a practical and approximate idea. Let's say something like: do not pad if you are adding more than 5% of original size in zeros.

$\endgroup$
  • 2
    $\begingroup$ tic toc will answer your question $\endgroup$ – Stanley Pawlukiewicz Mar 1 '18 at 5:32
  • 2
    $\begingroup$ Not quite a dup of : dsp.stackexchange.com/questions/10043/… . You can pad to a product of many small primes (2,3,5,7,11, etc.) with many modern FFT frameworks/libraries optimized for those product lengths. $\endgroup$ – hotpaw2 Mar 1 '18 at 9:28
  • $\begingroup$ @StanleyPawlukiewicz I know tic toc can help me. I also imagine that in some other platforms the result may vary. But maybe there has been some research about this and there might be a useful or practical hint $\endgroup$ – VMMF Mar 12 '18 at 14:00
  • 1
    $\begingroup$ @VMMF there are too many variables today. All the old analytic results counted multiplications because that was the bottle neck. That isn’t the case anymore. FFTW will actually do optimizations on its plan if you tell it to. There isn’t a lot of general universal results that applies everywhere $\endgroup$ – Stanley Pawlukiewicz Mar 12 '18 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.