The shortcut
that let computers
hear.
How the Fast Fourier Transform recovers the component frequencies of a signal — and how a factorization Gauss found in 1805 became standard computing infrastructure through a specific, traceable chain of events in the 1960s.
A recorded signal is several frequencies added together.
A microphone records one squiggly line: air pressure rising and falling over time. That line may contain a singer, a bass note, room echo, and electrical hum all at once.
The time view tells us what happened when. It does not plainly show what pitches are present.
The frequency view says how much of each repeating pattern is in the mixture.
The transform does not invent new information. It rotates the same data into a view where repeating structure is easier to see.
That simple change of view supports noise removal, compression, image reconstruction, spectrum analysis, and wireless communication. The hard part was once the cost: asking every candidate frequency how well it matched every sample.
The DFT tests the data against every candidate frequency in turn.
The Discrete Fourier Transform takes N samples and returns N frequency bins. For each bin, it compares the data with a spinning reference wave.
Start with a slow cycle. Then try faster ones, one by one.
When the data and test wave line up, their products reinforce. When they do not, positives and negatives cancel.
Magnitude says "how much." Phase says "where in its cycle."
This is the idea behind the standard DFT formula. Complex numbers are a compact way to track the cosine and sine parts together.
Each output asks about all eight inputs. Scale up: N outputs × N comparisons ≈ N² work.
Factor the transform, and reuse the sub-results.
When N can be factored, the same DFT can be reorganized into smaller DFTs. The common radix-2 version splits the samples into even-numbered and odd-numbered positions, solves both halves, then combines them.
A "butterfly" combines a pair with one add, one subtract, and a twiddle factor.
Each split halves the problem. A million samples require about 20 levels, not a million full passes.
The answer. The FFT computes the DFT. It is an organization of the arithmetic, not an approximation.
One important correction: "the Cooley–Tukey algorithm" is a family of factorizations, not only powers of two. Radix-2 is simply the easiest version to picture.
A million samples: one trillion vs. twenty million.
Big-O notation hides constants, but it reveals the growth curve. A direct DFT grows roughly as N². A radix-2 FFT grows roughly as N log2N.
about one trillion sample–frequency pairings
about twenty million units on this simple comparison
bars shown at proportional scale · not linear beyond illustration
Same destination. A radically shorter route: roughly 50,000× fewer units at N = 1,000,000.
That gap turned once-impractical ideas into routine ones: live filtering instead of later analysis; larger images; more radio channels; faster simulation. On real hardware, memory movement, precision, parallelism, and specialized libraries also matter. But the growth-rate advantage is the foundation.
Gauss found the factorization in 1805. The infrastructure to exploit it did not exist until the 1960s.
Factor a large transform into smaller ones.
Analyze more sampled data than direct calculation allowed.
Code, machines, journals, seminars, and people who crossed institutional lines.
An invention can exist without becoming an innovation. Infrastructure begins when knowledge can travel and other people can depend on it.
In unpublished work on interpolating the orbits of asteroids, Carl Friedrich Gauss described a factorization equivalent in its basic structure to an FFT. The work was written in Latin and not published until 1866.6
Versions of the "method of subseries" appeared in work by Runge and König, Danielson and Lanczos (1942), Yates, Good, Thomas, and others. Some were specialized; some lived outside the communities that later needed them.1,3,6
For hand calculation and small N, clever trigonometric tables and constant-factor tricks could beat a general recursive method. There was little reason to build software, training, and hardware around transforms too small to reveal the FFT's scaling advantage.1,6
Electronic computers could hold larger datasets. Seismology, speech, astronomy, and communications produced urgent demand. Princeton, IBM, and Garwin's cross-field network could move an idea from notation to code to users.
A nuclear-test-detection problem meets a factorization sketched on a notepad.
The documentary record supports the notepad episode. This illustration is interpretive, not a photograph.
Accuracy note: accounts differ in small details of routing and motivation. Cooley said Garwin initially described a helium-3 crystal problem and that Cooley learned later of the test-ban purpose. The broader nuclear-test-detection setting is independently repeated by IBM and IEEE histories.2,3
At a meeting of President Kennedy's Science Advisory Committee, John Tukey of Princeton worked through Fourier formulas on a notepad. Richard Garwin, then at IBM's Watson laboratory at Columbia, recognized the importance.1,2
The committee was considering remote detection of underground nuclear tests. Seismic records demanded spectral analysis at a scale that direct Fourier calculation made costly.2
Garwin took notes back to IBM, asked the research computing group for a numerical analyst, and was routed to James Cooley. Cooley later recalled that Garwin's persistent calls moved the work up his priority list.1,3
IBM's history says Cooley met Tukey at Princeton, returned to Yorktown Heights, and wrote a Fortran implementation. Princeton supplied the factorization insight; IBM supplied people, a large machine, and a route to use.2,4
Publication made the method citable and testable by others.
IEEE recognizes the first demonstration of the Cooley–Tukey FFT at IBM Research. The implementation showed orders-of-magnitude speed gains on a general-purpose scientific computer.2,4
Cooley wrote one-, two-, and three-dimensional code, including an in-place radix-2 scheme that reused storage. Garwin circulated it through his network. Seminars at IBM exposed it to mathematicians and APL designers.1,3
"The collaboration was lighter than legend suggests. Cooley wrote that the paper made one round trip between him and Tukey, with a few phone calls. Tukey edited, added references, and became coauthor."3
"An Algorithm for the Machine Calculation of Complex Fourier Series," vol. 19, pp. 297–301.5
The paper did not make the mathematics true. It made the method visible, citable, testable, and portable.
Six places the transform runs quietly, at scale.
Find tones, remove hum, shape equalizers, estimate spectra, and build efficient filters.
Compression and restoration use frequency structure. MRI reconstruction moves between measured frequency-space data and an image.
Analyze earthquakes, stars, vibrations, fluids, and correlations. Fast convolution accelerates many physical models.
OFDM divides a radio channel into many narrow subcarriers. IFFTs assemble symbols for transmission; FFTs separate them at the receiver. 5G NR uses OFDM waveforms.
FFT-based convolution can speed some large filters and long sequences. Spectral features and frequency-domain operators appear in audio, vision, and scientific AI.
Not every codec literally runs an FFT. JPEG, for example, uses a related cosine transform. The larger family shares the strategy of exposing frequency structure.
Once the transform is cheap, engineers stop budgeting for whether to run it and start building systems that assume it runs continuously.
Application claims are stated at the level the evidence supports. "Later AI" means important uses of FFTs in selected models and operators, not that all AI depends on them.
Four active research directions extend the same underlying idea.
When a signal's spectrum is sparse — most frequencies contribute almost nothing — MIT researchers Hassanieh, Indyk, Katabi, and Price showed the transform can be computed without even reading every sample, in sublinear time. Later work has pushed the sample count and dimensionality further.
The quantum analogue runs in O((log N)²) gates on a quantum computer, versus the FFT's O(N log N) classically. It is the core subroutine of Shor's algorithm for integer factoring, which would threaten RSA-style encryption at sufficient quantum scale.
In 2021, Google researchers replaced the self-attention layers in a BERT-style transformer with a fixed, unlearned Fourier transform. FNet reached 92–97% of BERT's accuracy on the GLUE benchmark while training up to 80% faster on GPUs.
FourCastNet, built on Fourier neural operators, generates a global medium-range weather forecast in under two seconds — orders of magnitude faster than physics-based numerical weather prediction — by learning atmospheric dynamics directly in frequency space.
None of these results replace the 1965 algorithm for its original job. Each trades the same hard direct computation for a cheaper one in frequency space, in a setting the original algorithm was not built for: sparse data, quantum hardware, and learned models.
The result depended on a sequence of specific, non-obvious conditions.
Garwin happened to sit close enough to notice Tukey's work and knew enough physics, policy, and computing to see its value.
Princeton gave Tukey freedom across mathematics, statistics, and policy. IBM Research could assign Cooley, run code on the 7094, convene seminars, and distribute programs.
Tukey compressed the idea. Garwin pushed it. Cooley made it practical, memory-aware, and publishable. Adoption then grew through users in signal processing and science.
Cooley's retrospective says IBM considered patent possibilities, then chose to place the algorithm in the public domain to keep others from patenting it. The paper and a hardware disclosure were part of that strategy.1,3
The Fourier transform reveals the frequencies inside sampled data. Doing it directly compares every sample with every frequency, so the work grows as N². The FFT gets the same answer by splitting the problem and reusing partial results, so work grows near N log N. That gap made frequency analysis cheap enough to become a building block of modern computing.
Priority is not the most useful question here. Gauss had the mathematics. Cooley and Tukey arrived when machines, data volumes, and institutions were finally able to use it. What was new was the alignment of an old result with new scale, code, and distribution.
The outcome required an existing mathematical result, a pressing computational need, and institutions able to carry it from notation into working code.
- Cooley & Tukey retrospective, Citation Classics (1993), including meeting, routing, public-domain decision, and earlier work: garfield.library.upenn.edu/classics1993/A1993MJ84400001.pdf
- IBM Research, "How IBM Research first demonstrated the Cooley-Tukey FFT" (2025): research.ibm.com/blog/how-ibm-research-first-demonstrated-the-revolutionary-cooley-tukey-fft
- James Cooley, "The Re-Discovery of the Fast Fourier Transform Algorithm" / oral-history account: carmamaths.org/resources/jon/Preprints/Talks/CARMA-CE/FFT.pdf
- Princeton ECE / IEEE Milestone, 1964 demonstration: ece.princeton.edu/news/ieee-commemorates-1964-demonstration-fast-fourier-transform-milestone-plaque
- Cooley & Tukey, original 1965 paper, AMS: community.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1.pdf
- Heideman, Johnson & Burrus, "Gauss and the History of the FFT" (1984): faculty.washington.edu/seattle/physics541/2010-Fourier-transforms/history-3.pdf
- Hassanieh, Indyk, Katabi & Price, "Simple and Practical Algorithm for Sparse Fourier Transform," SODA (2012): groups.csail.mit.edu/netmit/sFFT/soda_paper.pdf
- Quantum Fourier Transform complexity and its role in Shor's algorithm: arxiv.org/abs/1511.04818
- Lee-Thorp, Ainslie, Eckstein & Ontanon, "FNet: Mixing Tokens with Fourier Transforms" (2021): arxiv.org/abs/2105.03824
- Pathak et al., "FourCastNet: A Global Data-driven High-resolution Weather Model using Adaptive Fourier Neural Operators" (2022): arxiv.org/abs/2202.11214
All graphics are original schematic illustrations. No archival photograph is presented as documentary evidence.