Fast Fourier transform

Lore & Background

Gauss did not analyze the method's complexity and eventually used other methods. C. Danielson and Cornelius Lanczos published their version to compute DFT for x-ray crystallography, realizing one could use periodicity to double n with only slightly more than double the labor. J. Good published a paper establishing the prime-factor FFT algorithm for sizes where n = n₁n₂ with coprime factors. Tukey conceived the idea during a meeting of President Kennedy's Science Advisory Committee discussing detecting nuclear tests. Richard Garwin recognized the algorithm's general applicability and gave Tukey's idea to Cooley for implementation. As Tukey did not work at IBM, the algorithm went into the public domain, making it indispensable in digital signal processing.

Reader's Guide

The fast Fourier transform is significant because it made the discrete Fourier transform computationally practical for large sequences, reducing the number of operations from O(n²) to O(n log n). The FFT is not a new transform but an algebraic refactoring of the DFT, yielding mathematically equivalent results with infinite precision. In the presence of round-off error, many FFT algorithms are more accurate than evaluating the DFT definition directly. Its legacy includes widespread application in engineering, music, science, and mathematics. Many FFT algorithms depend on the factorization of n, but there are FFTs with O(n log n) complexity for all n, including prime values. The inverse DFT is the same as the DFT with opposite sign in the exponent and a 1/n factor, so any FFT algorithm can be adapted for it.

Did You Know?

• The FFT reduces the complexity of computing the DFT from O(n²) to O(n log n).
• Tukey's idea for the FFT arose during a meeting of President Kennedy's Science Advisory Committee about detecting nuclear tests.