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 as a combination of two DFTs of length .
- If is a power of 2, we may apply this lemma recursively until we require trivial DFTs of length 1.
- The cost is therefore instead of which for is roughly times faster.
- This result can be generalised for the case when contains prime factors other than 2.

Peter D. Haynes 2001-11-07