The encyclopedia · Engineering & Operations · Technical decision · 1965
Cooley-Tukey FFT turned a huge Fourier computation into a cheap one
In 1965 Cooley and Tukey split a transform into even and odd halves, cutting N² work to N log N.
IBM Research
the move
The discrete Fourier transform turns a list of samples into the frequencies that make them up, but doing it directly means each of the N outputs must combine all N inputs, so the work grows like N². For signals in the real world that was far too slow to compute in real time.
Cooley and Tukey spotted that a length-N transform splits cleanly into two length-N/2 transforms, one from the even-indexed samples and one from the odd-indexed ones, which can then be combined. Repeating that split produces ever-smaller transforms, so each stage processes all N samples once and there are only about log2 N stages.
The result is that the same numbers come out in N log N time instead of N². An example in the paper set N=8,192, where the FFT finished in about five seconds on an IBM 7094 while the conventional approach took roughly half an hour, and that gap is exactly why Wi-Fi, MP3 and MRI can be processed live.
why it works
- Splitting once turns one large transform into two half-size ones that are each cheaper to compute.
- Doing the split recursively gives about log2 N rounds, each touching N samples once.
- The huge N² to N log N drop turns a take-half-an-hour job into a five-second one.
what transfers
When a computation grows quadratically, look for a way to write the same result as smaller copies of itself; reusing those smaller answers turns a hopeless problem into a trivial one.
what came after
The Cooley-Tukey FFT became the foundation of modern digital signal processing, used to run Wi-Fi and mobile networks, compress audio as MP3, and reconstruct images in MRI, and it underpins everything from seismology to the quantum Fourier transform behind Shor's algorithm.
references
spotted an error? The archive wants to know.