Nib asked
How does a fast Fourier transform work?
The fast Fourier transform gives exactly the same answer as the slow one: it just splits the samples into evens and odds, reuses the two half-size answers, and repeats, cutting N squared work to about N log N.
6 steps, drawn by Nib. Read it here, or watch him draw it. Updated .
1same answer
The Fourier transform takes a signal measured over time, such as a sound, and reports how much of each pure frequency it contains. The fast Fourier transform (FFT) is not a rougher version of that idea. Up to tiny rounding errors it returns exactly the same numbers as the direct calculation. All it changes is the route to them.
The FFT is the same transform, computed by a cleverer route.
a common mix-upThe FFT is not an approximation of the Fourier transform: it gives the same answer as the slow method, up to rounding.
2the slow way
The direct method, the discrete Fourier transform (DFT), builds each output frequency by multiplying every one of the N samples by a spinning complex number and adding the results. With N outputs, each needing N products, the cost is N squared. For N = 1,048,576 (2 to the 20th power) that is about 1.1 trillion multiplications.
Direct method: N outputs, N products each, so N squared work.
How many multiplications does the direct method need for 1,024 samples?
Show the answer
About 1,024 squared, which is 1,048,576.
3split in two
Take samples numbered 0, 2, 4, and so on, and run a transform of size N/2 on them. Do the same for samples 1, 3, 5, and so on. Each half-size transform costs (N/2) squared, so two of them cost N squared over 2: half the original, before any further trick.
Two half-size transforms cost half as much as one full-size one.
4the butterfly
Write E[k] for the transform of the even samples, O[k] for the odd ones, and W for the spinning factor e to the minus 2 pi i over N (the twiddle factor). Then X[k] = E[k] + W^k O[k]. Because W^(k+N/2) = −W^k, and E and O repeat every N/2, the second half is X[k+N/2] = E[k] − W^k O[k]. One multiplication yields two outputs, and the crossed shape of the diagram gives the butterfly its name.
One twiddle product, added once and subtracted once, gives two outputs.
Why can X[k+N/2] reuse the product W^k O[k]?
Show the answer
Because W to the power k plus N over 2 equals minus W to the k, and E and O repeat every N over 2.
5keep halving
The halves are themselves transforms, so each can be split the same way. Halving N = 8 gives 4, then 2, then 1, and a transform of one sample is just the sample. That is log base 2 of N levels, and every level does N/2 butterflies.
Halve repeatedly: log base 2 of N levels, each doing about N work.
6the payoff
Each of the log₂ N levels costs on the order of N steps, so the whole FFT costs about N log₂ N. At N = 1,048,576 that is about 21 million against 1.1 trillion: roughly 52,000 times fewer. Gauss used the idea around 1805 for asteroid orbits, but it spread after Cooley and Tukey published it in 1965. The classic version needs N to be a power of two; other sizes can be factored similarly.
N squared becomes about N log N: about 52,000 times fewer steps at a million samples.
Roughly how many times faster is N log N than N squared at N = 1,048,576?
Show the answer
About 52,000 times (N divided by log₂ N, which is 2^20 / 20).
Split into evens and odds, reuse the halves, repeat: that one idea turned an impossible trillion steps into a few million.