The Butterfly

Split it in two, and again, and the fast answer is the same answer.

The radix‑2 Cooley–Tukey FFT splits a length‑N signal into its even and odd halves, transforms each, then butterflies them back with twiddle factors W_N^k = e^−2πi·k/N. It runs in N log N instead of N² — and gives the byte‑for‑byte same result as the brute‑force O(N²) DFT. Once you trust that, multiplying two polynomials becomes pointwise multiplication in frequency: the convolution theorem, made exact.

x · y = ifft( fft(x̂) · fft(ŷ) )

Signal

length-8 radix-2 FFT · bit-reversed in, natural order out —

top wing E[k] + W·O[k] bottom wing E[k] − W·O[k] twiddle W_N^k (a rotating phasor)

—

Polynomial A

—

Polynomial B

—

Schoolbook — O(n²) coefficient convolution

conv(a, b) · the ground truth, multiply term by term

Via the FFT — pointwise in frequency

ifft( fft(â) · fft(b̂) ) · zero-padded to the next power of two

The FFT is one of the most consequential algorithms ever written — it is why digital audio, images, and radio are practical. Here it is operable and self‑proving: the fast divide‑and‑conquer transform agrees with the brute‑force sum to machine precision (two strangers’ code, one answer), and the convolution theorem turns polynomial multiplication into pointwise products that are byte‑identical to the schoolbook result. Drop the padding and the wraparound bites — the teeth are visible. One algorithm: radix‑2, power‑of‑two N.

← Fourier Epicycles (the slow drawing-DFT) ← The Shannon Limit