FFTs were first discussed by Cooley and Tukey (1965), although Gauss had actually described the critical factorization step as early as 1805 (Bergland 1969, Strang
1993). A discrete Fourier transform
can be computed using an FFT by means of the Danielson-Lanczos
lemma if the number of points is a power of two. If the number
of points
is not a power of two, a transform can be performed on
sets of points corresponding to the prime factors of which is slightly degraded in speed. An efficient real Fourier
transform algorithm or a fast Hartley transform
(Bracewell 1999) gives a further increase in speed by approximately a factor of two.
Base-4 and base-8 fast Fourier transforms use optimized code, and can be 20-30% faster
than base-2 fast Fourier transforms. prime factorization
is slow when the factors are large, but discrete Fourier transforms can be made fast
for ,
3, 4, 5, 7, 8, 11, 13, and 16 using the Winograd
transformalgorithm (Press et al. 1992,
pp. 412-413, Arndt).
Fast Fourier transform algorithms generally fall into two classes: decimation in time, and decimation in frequency. The Cooley-Tukey FFT algorithm
first rearranges the input elements in bit-reversed order, then builds the output
transform (decimation in time). The basic idea is to break up a transform of length
into two transforms of length using the identity
points from 
to 
, where lg is the base-2 logarithm.
is a power of two. If the number
of points 
is not a power of two, a transform can be performed on
sets of points corresponding to the prime factors of 
which is slightly degraded in speed. An efficient real Fourier
transform algorithm or a fast Hartley transform
(Bracewell 1999) gives a further increase in speed by approximately a factor of two.
Base-4 and base-8 fast Fourier transforms use optimized code, and can be 20-30% faster
than base-2 fast Fourier transforms. prime factorization
is slow when the factors are large, but discrete Fourier transforms can be made fast
for 
,
3, 4, 5, 7, 8, 11, 13, and 16 using the Winograd
transform algorithm (Press et al. 1992,
pp. 412-413, Arndt).
into two transforms of length 
using the identity
