The Fourier transform done directly costs N×N multiplies — hopeless for a million samples. The FFT splits the signal into evens and odds, transforms each half, and recombines with a ‘butterfly’ — recursively — dropping the cost to N×log N. For a million samples that’s a MILLION-fold speed-up. It’s one of the most important algorithms ever written. Slide N and watch the two curves diverge.
The Cooley–Tukey FFT computes the same DFT in O(N log N) instead of O(N²) by exploiting symmetry: split x into even- and odd-indexed samples, transform each of length N/2, then combine with twiddle factors (the ‘butterfly’: X[k]=E[k]+WⁿᵏO[k], X[k+N/2]=E[k]−WⁿᵏO[k]), recursing down to size 1. The result is bit-for-bit the DFT (verified here against the naive transform) but for N=2²⁰ it is ~50000× fewer operations. It underlies real-time audio, radar, fast convolution, and polynomial multiplication. A fail-loud self-check throws unless the radix-2 FFT equals the naive DFT to 1e−6. ◆ real signal math, node-verified.
Classic radix-2 wants N a power of two (mixed-radix/Bluestein handle other sizes); floating-point rounding gives ~1e−6 agreement, not literally identical bits. The N log N speed-up and exact-transform equivalence are real.