The discrete Fourier transform (DFT) is the digital counterpart of the Fourier series: take samples of a signal at equal time intervals, and compute the complex coefficients that describe how much of each oscillation frequency the signal contains. Every signal-processing operation that involves frequencies — playing an MP3, sending a packet over Wi-Fi, reconstructing an MRI scan, analysing a star’s light, multiplying large integers — uses the DFT or a close relative at its core.
The formula for the DFT is short but the computation is large. The -th coefficient is
Compute one and you do complex multiplications and additions. Compute all of them and you do multiplications and additions. For that is a million operations, manageable. For — a digital photograph — that is a trillion operations, which is impossible to do in real time even on modern hardware. The naive DFT scales catastrophically.
In 1965, J. W. Cooley of IBM and John Tukey of Princeton published a recursive algorithm that brought the cost of computing the DFT down to . This was not a small improvement; it was a transformation in what was practically computable. The new algorithm was called the Fast Fourier Transform, or FFT, and it is now used so universally in digital systems that “FFT” and “Fourier transform” are often used interchangeably in engineering practice. This article is about what the algorithm does, how it works, and why it sits among the most consequential mathematical inventions of the twentieth century.
The trick: divide the sum by parity
The clever move is to split the sum over the samples into two halves: the samples with even indices and the samples with odd indices. Writing — a primitive -th root of unity — we have
The factor is the corresponding root of unity for a smaller DFT of size . So if we call the DFT of the even-indexed samples and the DFT of the odd-indexed samples, both of size , then
By the periodicity of the roots of unity, the other half of the spectrum follows from the same two smaller DFTs:
The constant is called the twiddle factor. Two smaller DFTs plus twiddle multiplications and additions reconstruct the full DFT. If we recursively apply this same idea to the two smaller DFTs, then to the four still-smaller ones, and so on, the recursion ends after levels at trivial DFTs of size . Counting the operations at each level — butterflies per level, levels — gives a total cost of . That is the entire idea of the FFT in one paragraph.
The butterfly
The elementary operation of the algorithm — take two inputs and , multiply by a twiddle factor , and output the pair — is called a butterfly, because its flow graph looks like wings. The picture below shows a butterfly diagram for an point FFT, drawn in the standard “decimation-in-time” form.
Read the diagram left to right. The four inputs are presented in bit-reversed order — — which arranges the recursion correctly. In the first stage, two independent size- butterflies compute the sums and differences of pairs; this is where the smaller DFTs live. In the second stage, two more butterflies combine these intermediate results, multiplied by the appropriate twiddle factors , to produce the final outputs .
The diagram for would have three stages and twelve butterflies. The diagram for in general has stages with butterflies each, for a total of butterflies — and that is the famous operation count.
How much does this save?
The improvement is staggering for any nontrivial . The table below shows the ratio of operations between the naive DFT and the FFT for several powers of two.
| Naive | FFT | Speedup | |
|---|---|---|---|
| 8 | 64 | 24 | 3× |
| 1024 | 1,048,576 | 10,240 | 100× |
| × | |||
| × |
By the time reaches the size of a digital photograph, the FFT is about fifty-thousand times faster than the naive DFT. At the size of a high-resolution audio file or a long scientific signal, the speedup is in the tens of millions. Many applications that we take for granted — real-time audio effects on a phone, live video filters, GPS reception — exist only because of this efficiency. The naive DFT would simply not finish in time.
The Gauss precedent
A surprising historical wrinkle: the FFT was not originally invented in 1965. Carl Friedrich Gauss had developed essentially the same recursive idea around 1805, while computing the orbit of the asteroid Pallas (and later Juno) from sparse astronomical observations. He needed to interpolate a curve through a small number of data points, and he discovered the same divide-and-conquer trick that Cooley and Tukey would rediscover 160 years later. Gauss wrote the idea up briefly in his unpublished mathematical notebooks; it was not until the 1970s that Herman Goldstine identified the work as a complete FFT and pointed out the historical precedent.
Why did Gauss’s algorithm not change history? Because the speedup over is only impressive when both quantities are large. For small , as a hand computer Gauss had no occasion to use, the savings are noticeable but unspectacular. The FFT becomes a transformative algorithm only when runs into the thousands and millions — sizes that only digital computers can routinely handle. Gauss’s invention was a brilliant piece of computational mathematics; Cooley and Tukey’s invention was the same piece of mathematics applied to a world in which had suddenly become an everyday number. The same algorithm changed history twice and got credit only the second time.
Where the FFT lives
The FFT is, by common acclamation, the most-used numerical algorithm in the history of computing. A partial list of its appearances:
Audio compression. MP3, AAC, and Opus encoders all begin by computing FFTs of short audio segments to find which frequencies are present and which can be discarded as inaudible to the human ear.
Image compression. JPEG uses the closely related discrete cosine transform on blocks of an image, again to identify spatial frequencies that can be quantised or removed without visible degradation.
Wireless communication. Modern cellular standards (4G LTE, 5G) and Wi-Fi use OFDM (orthogonal frequency-division multiplexing), in which an FFT at the transmitter spreads data across many narrow frequency bands, and an inverse FFT at the receiver reconstructs the message. Every wireless device you own contains an FFT chip.
Medical imaging. Magnetic resonance imaging (MRI) measures data in the frequency domain directly; an inverse FFT converts the raw data into the spatial image you see on the radiologist’s screen.
Polynomial and integer multiplication. Multiplying two polynomials of degree naively takes operations. Using FFT-based multiplication via convolution it takes . The same idea, applied to integers, gives the Schönhage–Strassen algorithm for multiplying large integers — used by GMP, RSA encryption implementations, and scientific computing libraries.
Partial differential equations. Many numerical methods for diffusion, wave propagation, and fluid flow use FFTs to handle the spatial derivatives quickly. Spectral methods in computational physics depend on this entirely.
Astronomy and seismology. Pulsar timing, gravitational-wave detection, and earthquake analysis all use FFTs to extract structure from long time series of measurements.
It is no exaggeration to say that the entire digital world — from a phone call to a satellite image — is powered, somewhere in its plumbing, by FFTs running by the billions per second on chips around the planet.
A small piece of mathematics with an outsized impact
What makes the FFT remarkable, as a piece of mathematics rather than as a piece of engineering, is the combination of its elementary core and its outsized consequences. The trick — split the sum into even and odd indices and reuse twiddle factors — fits on the back of an envelope. The recursion is so transparent that anyone who has seen merge sort understands it within a minute. The proof of correctness is one line. The implementation in any reasonable programming language fits on a single screen.
And yet this small piece of mathematics restructured the field of signal processing, made digital communications practical, enabled music and image compression at scales the inventors could not have dreamed of, and gave applied mathematics one of its most successful tools. The FFT is the working example, par excellence, of how a single insight about the structure of a problem — split, conquer, and reuse — can change what is computationally possible. Gauss saw the trick first; Cooley and Tukey saw why it mattered. Without them, the modern digital world would be slower by orders of magnitude, and many of its routine operations would be entirely out of reach.
Frequently asked
Did Gauss really discover the FFT before Cooley and Tukey?
Essentially yes. In 1805, while computing the orbit of the asteroid Juno, Gauss developed a recursive method that is mathematically equivalent to the modern Cooley–Tukey algorithm. He wrote it in his unpublished notebooks; the work was discovered and analysed by Herman Goldstine only in the 1970s, well after the modern algorithm had become famous. Gauss did not see the algorithmic significance — for a hand computer, the savings of N log N over N² are visible but not transformative. The same trick on a 1965 mainframe processing a million samples turned an overnight job into a few seconds, which is what made the algorithm legendary.
Why is N log N such a big improvement over N²?
Because the gap grows enormously with N. For N = 1024 (a small audio frame), N² is about a million operations while N log N is about ten thousand — a hundred-fold speedup. For N = one million (a digital photograph), N² is a trillion operations, while N log N is twenty million — a 50,000-fold speedup. Many applications that are routine today, including real-time spectrum analysis, image compression, and direct-sequence cellular communication, are simply impossible at the naive O(N²) rate. The FFT made an entire family of techniques feasible at all.
What is a 'butterfly' in FFT terminology?
A butterfly is the elementary operation of the FFT: two inputs a and b, a twiddle factor ω, and two outputs (a + ω·b) and (a − ω·b). The flow graph of these operations, when drawn, looks like the wings of a butterfly — hence the name. A full N-point FFT consists of (N/2)·log₂N butterflies arranged in log₂N successive stages, each combining the results of smaller FFTs. The total operation count is therefore O(N log N).
Where is the FFT used today?
In essentially every modern technology that processes signals. JPEG image compression uses the related discrete cosine transform, computed with FFT-like methods. MP3 and AAC audio encoders use FFTs to identify frequencies the ear cannot hear and remove them. Wi-Fi, 4G, and 5G cellular networks use OFDM (orthogonal frequency-division multiplexing), which depends on FFTs at both transmitter and receiver. MRI machines reconstruct images from frequency-domain data using FFTs. Astronomers analyse pulsar signals, seismologists analyse earthquake data, financial analysts study time-series, and engineers solve partial differential equations — all using FFTs. It has been called the most important numerical algorithm of all time.