Fast Fourier transform
Algorithm computing discrete Fourier transforms in O(n log n) time.
The fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) or its inverse, converting a signal between its original domain (often time or space) and a representation in the frequency domain. By factorizing the DFT matrix into sparse factors, the FFT reduces computational complexity from O(n²) to O(n log n), enabling practical analysis of long sequences. This speed difference is enormous for sequences with thousands or millions of values. The DFT itself decomposes a sequence into components of different frequencies, but direct computation from its definition is often too slow. The FFT achieves its speed by refactoring the DFT algebraically, so both perform mathematically equivalent operations with infinite precision. In practice, many FFT algorithms are more accurate under round-off error than direct DFT evaluation. Numerous FFT algorithms exist, relying on theories from complex arithmetic to group and number theory. The best-known depend on factoring the sequence length n, but algorithms with O(n log n) complexity exist for all n, including prime values. Many FFTs exploit that the transform uses an nth primitive root of unity, allowing application to analogous transforms over finite fields, like number-theoretic transforms. The inverse DFT, identical but with opposite sign and a 1/n factor, is easily adapted from any FFT algorithm. The basic ideas were popularized in 1965, though some algorithms date to 1805. Carl Friedrich Gauss developed an unpublished method in 1805 for interpolating asteroid orbits, similar to the 1965 algorithm by James Cooley and John Tukey. Between these, Frank Yates published an interaction algorithm in 1932 for Hadamard and Walsh transforms, still used in experimental design. In 1942, G. C. Danielson and Cornelius Lanczos used periodicity to double DFT size with slightly more than double the labor, though without analyzing O(n log n) scaling. I. J. Good published a prime-factor FFT in 1958 for composite sizes with coprime factors. Cooley and Tukey’s 1965 paper generalized the algorithm for any composite n and analyzed its O(n log n) complexity. Tukey conceived the idea during a meeting on detecting Soviet nuclear tests via sensors; Richard Garwin recognized its broader applicability, including to spin orientations in a Helium-3 crystal, and had Cooley implement it. The algorithm entered the p
- field
- Digital signal processing, numerical analysis
- known_for
- Fast computation of the discrete Fourier transform
- complexity_reduction
- From O(n²) to O(n log n)
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.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record