Next: 3D Fourier Transforms
Previous: Danielson-Lanczos Lemma
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
- 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