NEXTFASTFFT Next higher number with a fast FFT
Usage: nfft=nextfastfft(n);
NEXTFASTFFT(n) returns the next number greater than or equal to n,
for which the computation of a FFT is fast. Such a number is solely
comprised of small prime-factors of 2, 3, 5 and 7.
NEXTFASTFFT is intended as a replacement of nextpow2, which is often
used for the same purpose. However, a modern FFT implementation (like
FFTW) usually performs well for sizes which are powers or 2,3,5 and 7,
and not only just for powers of 2.
The algorithm will look up the best size in a table, which is computed
the first time the function is run. If the input size is larger than the
largest value in the table, the input size will be reduced by factors of
2, until it is in range.
[n,nfft]=NEXTFASTFFT(n) additionally returns the table used for
lookup.
References:
J. Cooley and J. Tukey. An algorithm for the machine calculation of
complex Fourier series. Math. Comput, 19(90):297--301, 1965.
M. Frigo and S. G. Johnson. The design and implementation of FFTW3.
Proceedings of the IEEE, 93(2):216--231, 2005. Special issue on
"Program Generation, Optimization, and Platform Adaptation".
P. L. Soendergaard. LTFAT-note 17: Next fast FFT size. Technical report,
Technical University of Denmark, 2011.
Url: http://ltfat.github.io/doc/fourier/nextfastfft.html
See also: ceil23, ceil235, demo_nextfastfft.
Package: ltfat