Nib asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
how does a fast fourier transform work
Any sound is a stack of pure waves, and the Fourier transform finds which ones. The fast version is not an approximation: it gives the very same numbers, just sooner.
The slow way: for each of N frequencies, multiply all N samples by a spinning arrow and add. That is N times N. A million samples means over a trillion multiplications.
Here is the trick. Split the samples into the even-numbered ones and the odd-numbered ones. Each half needs only a half-size transform, and those cost much less.
Then stitch the halves together. Output k is the even answer plus a twiddle factor times the odd answer. Output k plus N over 2 reuses that same product, subtracted.
Now repeat. Each half splits again, and again, down to single samples. For eight samples that is three halvings, because two cubed is eight. In general, log base two of N.
Add it up: about N work per level times log N levels. For a million samples, 21 million steps instead of 1.1 trillion: roughly fifty thousand times fewer.
Split into evens and odds, reuse the halves, repeat: that one idea turned an impossible trillion steps into a few million.