The Algorithm Gauss Had in 1805 and Nobody Read

James Cooley and John Tukey's paper "An Algorithm for the Machine Calculation of Complex Fourier Series" appeared in Mathematics of Computation in April 1965. Six pages. It cut the cost of computing a discrete Fourier transform of N points from order N² to order N log N — for N = 1024, a thousandfold speedup.

The origin story is unusual for an algorithm. Tukey, on President Kennedy's Science Advisory Committee, was working on how to detect Soviet nuclear tests by ringing the country with seismographs and Fourier-analyzing the signals. He sketched the recursive halving idea — compute the DFT of an N-point sequence by combining two DFTs of N/2-point sequences — at a meeting. Cooley, at IBM, wrote it up.

What Cooley and Tukey did not know is that Carl Friedrich Gauss had written the same algorithm in 1805, computing the orbits of the asteroids Pallas and Juno from sparse observations. Gauss never published the calculation. It appeared in Volume 3 of his collected works in 1866, in a treatise titled Theoria Interpolationis Methodo Nova Tractata, written in Neo-Latin. Michael Heideman, Don Johnson, and C. Sidney Burrus uncovered the connection in 1984 and published it in IEEE ASSP Magazine.

The awkward part of the history is that the FFT was independently discovered at least a dozen times between 1805 and 1965 — Runge and König in 1924, Danielson and Lanczos in 1942 — and each time the result lived in a corner of one field and didn't propagate. What Cooley and Tukey added was timing: a digital computer that could actually run the thing, and a paper short enough to read.