In 1965, James Cooley and John Tukey published a paper that transformed scientific computing.
The Fast Fourier Transform (FFT).
It is widely regarded as one of the most important numerical algorithms of the 20th century, and was included in the top algorithms list by IEEE’s Computing in Science & Engineering.
Let's talk about the problem it solved
The Discrete Fourier Transform (DFT) converts a signal from the time domain into its constituent frequencies.
Computed directly, it requires:
O(N²) operations.
For N = 1,000,000 data points, that’s on the order of 10¹² operations.
The key formula
Xₖ = Σ xₙ · e^(−i2πkn/N) for n = 0 to N−1
A DFT of size N can be decomposed into smaller DFTs by separating the input into even- and odd-indexed elements and exploiting symmetries of complex exponentials.
Applying this idea recursively reduces the computational complexity to:
O(N log N)
For N = 1,000,000, this is on the order of 20 million operations.
# Some History #
Variants of this approach were described earlier by Carl Friedrich Gauss around 1805 in work related to astronomical calculations. However, these ideas were not developed into a general-purpose algorithm or widely disseminated at the time.
The 1965 paper by Cooley and Tukey brought the method into practical use in modern computing.
FFT is a fundamental building block in many fields:
→ Audio - spectral analysis, compression, speech processing
→ Images - filtering, compression, computer vision
→ Communications - OFDM systems used in 4G LTE and 5G NR
→ Wi-Fi - IEEE 802.11 standards
→ Medicine - MRI and CT image reconstruction
→ Science - signal analysis in physics and engineering