Any signal is a sum of pure waves; the Fourier transform finds which. Done naively it costs N² steps; the FFT does it in N log N by splitting the problem in half again and again — a speedup so large it made whole fields possible. Its data is complex (two reals), and its butterfly hands back two outputs at once — pressing the array-of-pairs and multiple-return the box lists.
THE TECHNIQUE split in half, combine with a twiddle
Split the samples into evens and odds, transform each half, then combine with a twiddle factor (a point on the unit circle). Recurse, and N² collapses to N log N. Below: a signal built from a few pure frequencies, and its spectrum — the peaks name the frequencies. live demo
HISTORY & CREDIT the textbook case of Stigler’s law
“Cooley-Tukey, 1965” — the algorithm was independently invented at least a couple dozen times before them, first by Gauss. cited
1805 · Carl Friedrich Gauss writes the fast method in unpublished Latin notes — before Fourier published the transform (1822). Printed only in 1866, it was invisible to the field. 1903 / 1942 · Runge, then Danielson & Lanczos (for X-ray scattering from liquids) derive the doubling/butterfly by hand — a near-miss on a Nobel-scale idea, 23 years early. 1965 · James Cooley (IBM) & John Tukey (Princeton) publish the general form — at the exact moment digital computers made it transformative. Richard Garwin was the catalyst; Tukey supplied the insight, Cooley wrote the code. 1984 · Heideman, Johnson & Burrus assemble the full multiple-discovery history and restore Gauss.
Its modern rediscovery was driven by the Cold-War need to detect Soviet nuclear tests from seismometer data — corroborated, not folklore. Gauss, 1805
RECOMMEND FOR I-13 complex data, two-output butterflies
A complex number is two reals (as Mandelbrot-019 already showed), so the butterfly’s complex multiply runs in real I-13 — e.g. (3+4i)(1+2i):
$ i13 run cmul.i13 # one butterfly's complex multiply, on f64 pairs
cr = -5 ci = 10 # (3+4i)(1+2i) = -5 + 10i
Recommend: the FFT presses two box frontiers at once. Its data is an array of complex — and I-13 arrays hold f64, so complex must be an array-of-pairs (or two parallel real arrays, which works today). And each butterfly takes two complex in, gives two complex out — a multiple-return, the last withheld frontier (now named by darts 045, 048, 052, 055, and here). Twiddle factors are cos/sin from the stdlib. Runs today: with two parallel f64 arrays and each butterfly writing its two outputs separately, the transform is expressible now; a complex/pair value and multiple-return would make it read like the textbook.