Sixty Years of FFT
April 1965. While the world was busy with Cold War paranoia and the early days of Moore’s Law, a mathematician and a statistician quietly dropped a paper that would become one of the most cited—and least celebrated—pieces of engineering ever written. Cooley and Tukey’s Fast Fourier Transform didn’t promise to change the world. It just made it a lot more efficient. The FFT reduced the computation of discrete Fourier transforms from O(n²) to O(n log n). This exponential unlock made it so that the Fourier transform could run on machines that fit in rooms, and later, in pockets.
Frequency, Everywhere
We don’t live in the time domain anymore. We stream music, compress images, diagnose diseases, and simulate the weather—all using frequency-domain representations. The FFT made this shift technically and economically viable. And yet, despite its pervasiveness, the FFT has managed to remain in the background. It’s not flashy. It doesn’t show up in headlines or product launches. It’s more like gravity: assumed, unglamorous, and impossible to avoid. Consider the Following:
- Every song you’ve streamed was likely encoded, filtered, and compressed with help from FFTs.
- Every image you’ve zoomed into, every FaceTime call you’ve made, every WiFi signal you’ve relied on—all FFT.
- Radar and sonar. Medical imaging. Earthquake detection. Even Google’s speech recognition models—FFT, FFT, FFT.
And it’s still evolving. Today’s implementations run on GPUs, FPGAs, and even edge AI chips. FFTs are optimized for SIMD instructions and tuned for cache efficiency. There are entire software libraries—FFTW, KissFFT, cuFFT—dedicated solely to making this one algorithm run just a little faster.
A Mathematical Fossil That Still Works
At 60, the FFT is one of those rare pieces of engineering that hasn’t aged out of relevance. It’s as much a cultural artifact as it is a computational tool—proof that a good idea, once unlocked, can scale across decades, industries, and paradigms. It’s also a reminder that not all revolutions announce themselves. Some just show up in a short paper with the title An Algorithm for the Machine Calculation of Complex Fourier Series, and quietly start running the world in the background.