Skip to content

Cooley, Tukey, and the Fast Fourier Transform

Abstract

The Fast Fourier Transform (often called the most important numerical algorithm of the twentieth century) was born from Cold War arms control. At a 1963 meeting of the President’s Science Advisory Committee on detecting Soviet underground nuclear tests, Princeton statistician John Tukey sketched a way to compute Fourier transforms with drastically fewer operations. Physicist Richard Garwin spotted what it was worth, IBM’s James Cooley turned it into a working algorithm, and their 1965 paper reduced the cost of frequency analysis from N² to N·log N, turning a computation that took weeks into one that took seconds. Only afterwards did anyone notice that Carl Friedrich Gauss had written down essentially the same trick in 1805, and left it unpublished in Latin.

The Problem: Hearing the Frequencies

The Fourier transform decomposes a signal into its constituent frequencies, the mathematical act behind every spectrum analyzer, audio codec, image compressor, and radio receiver. Computed naively, the discrete Fourier transform (DFT) of N samples requires on the order of N² operations. For the long seismometer time series of the 1960s (thousands of sensors, millions of samples) that was computationally hopeless. Frequency analysis was theoretically the right tool for almost everything and practically affordable for almost nothing.

Arms Control as Midwife

The United States could verify a nuclear test ban only if underground Soviet tests could be distinguished from earthquakes, a signal-processing problem on a global network of seismometers. In 1963, during a meeting of President Kennedy’s Science Advisory Committee on exactly this question, John W. Tukey, the Princeton and Bell Labs statistician who had coined the word “bit” (and was among the first to use “software” in print), worked out that a DFT could be computed recursively, splitting the problem in half again and again, for a total cost of N·log N.

Richard Garwin of IBM, sitting in the meetings, recognized the scheme’s significance far beyond seismology and pressed IBM’s mathematics department to find someone to program it. The task landed on James W. Cooley at the IBM Watson Research Center, who developed and implemented the general algorithm on an IBM 7094 in 1964. The paper (“An Algorithm for the Machine Calculation of Complex Fourier Series,” published April 1965 in Mathematics of Computation) became one of the most cited mathematics papers ever written.

Notably, IBM favored publishing the algorithm openly rather than patenting it, placing it in the public domain, where nothing could stop its spread. It spread everywhere.

DFT cost, N = 1,000,000 samples:

  Naive:        N² = 10¹²  operations
  Cooley–Tukey: N·log₂N ≈ 2×10⁷ operations

  Speedup: ~50,000×  — the difference between
  "weeks on a mainframe" and "real time"

Gauss Got There First, and Told No One

The 160-Year Anticipation

After the 1965 paper’s explosive reception, historians found that Carl Friedrich Gauss had used the same divide-and-conquer scheme around 1805 to interpolate the orbits of the asteroids Pallas and Juno, before Fourier had even published the analysis the transform is named for. Gauss recorded it in a Neo-Latin manuscript that was published only posthumously in his collected works, where nobody looked. The episode is a standing lesson in scientific communication: an unpublished result, however brilliant, does not exist. (Partial rediscoveries kept happening in between, Danielson and Lanczos published a doubling method in 1942, and kept being overlooked, because before electronic computers the trick saved hours of hand calculation rather than opening new worlds.)

What the FFT Unlocked

The FFT converted the Fourier transform from a theoretical ideal into the default operation of the digital age. Digital signal processing became a field; spectrum analysis became routine lab equipment; medical imaging (CT and MRI reconstruction), radar and sonar processing, audio and image compression (MP3, JPEG’s DCT cousin), OFDM modulation in Wi-Fi, 4G/5G and DSL, all are FFT machines. It is running in essentially every phone call and every streamed song, billions of times per second worldwide. The IEEE recognized the 1964 demonstration with a Milestone award, and the algorithm routinely tops lists of the most important algorithms of the century alongside the great algorithmic ideas it exemplifies: divide and conquer, and the power of an asymptotic improvement to change what is possible rather than merely what is fast.

Cooley (1926–2016) spent his career at IBM and became the FFT’s historian and evangelist. Tukey (1915–2000) continued a career so broad (exploratory data analysis, the box plot, robust statistics) that the FFT is only one line in it; his statistical legacy runs through modern data analysis.

📚 Sources