Fast Fourier transform
Transformada rápida de Fourier (FFT)
- Date
- 1965 · confidence high
- Place
- Yorktown Heights, New York (IBM), and Princeton
- Credited to
- James Cooley and John Tukey; the method had already been used by Gauss in 1805
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What was discovered
Algorithm that computes the discrete Fourier transform in n log n time instead of n^2, making real-time spectral analysis feasible. It is the most influential numerical algorithm of the 20th century.
Gauss described the same algorithm in an 1805 manuscript (published in 1866) to interpolate asteroid orbits, even before Fourier's own work.
What it led to
- digital signal processing
- fast multiplication of integers and polynomials
- spectral analysis
- spectral methods for PDEs
- Digital processing of audio, image and video (MP3, JPEG)
- OFDM communications for Wi-Fi, 4G and 5G
- Medical imaging (MRI) and radio astronomy
Built on
- Fourier series and transform1807
- Fourier series
- Gauss (orbit interpolation, 1805)
- Danielson and Lanczos (1942)
- digital computer
- detection of nuclear tests
Made possible
- Magnetic resonance imaging (MRI)1973-1977
- JPEG and MP3 compression
- OFDM (Wi-Fi, 4G, 5G)
- magnetic resonance and tomography
- detection of nuclear tests
- MP3 and JPEG
- Wi-Fi and 4G
- digital signal processors