An Algorithm for the Machine Calculation of Complex Fourier Series
Reuse the sums you'd otherwise repeat, and the Fourier transform drops from N² to N log N.
The trick that turned an impossibly slow calculation into one your phone does thousands of times a second — and quietly switched on the digital age of sound, images, and wireless.
The idea, unpacked
A Fourier transform takes a signal — a sound wave, a radio burst — and works out which pure frequencies it is built from. The exact recipe for doing this was centuries old, but it was punishingly slow: to analyze N samples you had to do roughly N × N multiplications. Double the data and the work quadrupled. For real signals N is large, and on the computers of the early 1960s that was close to hopeless.
Cooley and Tukey found a shortcut. The calculation was full of repetition — the same little products computed over and over. By splitting the signal in half, then in half again, and reusing the shared pieces, they cut the cost from N² down to about N × log N. For a thousand samples, that is the difference between a million steps and a few thousand.
Where it came from
In 1965 James Cooley, a programmer at IBM Research, and John Tukey, a Princeton statistician, published a short paper in Mathematics of Computation. By Cooley's own later account, the idea had surfaced when Tukey sketched it at a meeting of a U.S. government science advisory committee: a pressing problem of the day was detecting distant nuclear tests from faint seismometer traces, which meant computing Fourier transforms of long records quickly. Cooley wrote the program, and the paper followed.
The timing was everything. The same mathematical trick had been discovered before — Gauss had it around 1805 — but it kept being forgotten, because before fast computers nobody urgently needed it. Cooley and Tukey published exactly when machines and problems had grown large enough to make it indispensable, and this time it stuck.
Why it mattered
Almost anything digital that involves sound, pictures, or radio leans on the Fourier transform somewhere — and the FFT is what makes it fast enough to feel free. It is part of why your music streams, your photos compress, your phone talks to a cell tower, and a hospital scanner can turn faint radio echoes into an image. An algorithm that merely rearranges arithmetic became one of the quiet load-bearing walls of modern technology.
A precise analogy
Picture scoring a huge round-robin tournament where every player has met every other. Done naively, you re-add the same sub-totals again and again. A smarter clerk groups the players, works out each group's sub-total once, and reuses it everywhere it is needed. The FFT is that clerk: it spots the sums the brute-force method keeps recomputing, does each one only once, and combines them in a handful of rounds — log N rounds, not N.
Its place in the story
The continuous mathematics behind this goes back to Joseph Fourier, who argued in 1822 that any signal can be built from simple waves (see his Analytical Theory of Heat in this Library). Turning that idea into samples a computer can hold relies on the sampling theorem at the heart of Shannon's 1948 information theory. The FFT is the bridge that made all of it practical — and six decades on, it remains among the most-run algorithms on Earth.
An efficient method for the calculation of the interactions of a 2^m factorial experiment was introduced by Yates and is widely known by his name.
In their full generality, Good's methods are applicable to certain problems in which one must multiply an N-vector by an N × N matrix which can be factored into m sparse matrices, where m is proportional to log N.