Fast Fourier Transforms

J. W. Cooley and J. W. Tukey, ``An algorithm for the machine calculation of complex Fourier series'', Math. Comput. 19, 297 (1965).

• The Danielson-Lanczos lemma enables us to write a discrete Fourier transform (DFT) of length $n$ as a combination of two DFTs of length $n/2$.
• If $n$ is a power of 2, we may apply this lemma recursively until we require $\log_2 n$ trivial DFTs of length 1.
• The cost is therefore ${\cal O}(n \log_2 n)$ instead of ${\cal O}(n^2)$ which for $n \sim 10 000$ is roughly $1 000$ times faster.
• This result can be generalised for the case when $n$ contains prime factors other than 2.