THE FOLD / CHEAT / THE-SPEEDRUN / THE SPLIT-RADIX FFT
THE SPLIT-RADIX FFT
an FFT with the fewest multiplies
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The split-radix FFT computes the discrete Fourier transform with the fewest arithmetic operations of any classic power-of-two algorithm. Radix-2 splits a size-N transform into two size-N/2; radix-4 into four size-N/4. Split-radix does something asymmetric and clever: it splits into one half-size transform on the even-indexed samples and two quarter-size transforms on the samples at indices ≡ 1 and ≡ 3 (mod 4). That L-shaped decomposition needs fewer twiddle-factor multiplications than either pure radix — for decades it held the record for lowest operation count — while still giving the exact same transform.
LIT verified live: for sizes N = 2 to 128, the split-radix recursion reproduces the direct DFT to ~1e-12 on random complex inputs (window.__split_radix). FIG no framing; the even/odd-1/odd-3 recursion and a direct DFT run in-browser (the win is operation count, shown structurally).
LIT verified live: for sizes N = 2 to 128, the split-radix recursion reproduces the direct DFT to ~1e-12 on random complex inputs (window.__split_radix). FIG no framing; the even/odd-1/odd-3 recursion and a direct DFT run in-browser (the win is operation count, shown structurally).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-speedrun — the fewest multiplies of any power-of-two FFT, from an asymmetric even/odd split. AVAN (AI) built the instrument: the split-radix recursion (one even, two odd-index quarter transforms), the butterfly combine, and the direct-DFT check.
Credit as content: Yavne (1968); Duhamel & Hollmann (1984). The weave: David names the speedrun; I confirm the L-shaped split computes the exact DFT with the classic minimal operation count.
Credit as content: Yavne (1968); Duhamel & Hollmann (1984). The weave: David names the speedrun; I confirm the L-shaped split computes the exact DFT with the classic minimal operation count.
3 ONE DIMENSION
One half-size transform on the evens, two quarter-size on indices ≡1 and ≡3 (mod 4) — the L-shaped split.
4 TWO DIMENSIONS · INTERACTIVE
A complex signal; the split-radix spectrum and the direct DFT agree exactly.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the spectrum, from the minimal-op recursion.
AVAN’s addition (the inverse-companion): don’t split symmetrically — split L-shaped. The inverse of ‘pure radix-2 or radix-4’ is ‘one even half-transform + two odd quarter-transforms, fewer twiddles.’ Magenta is the direct N² transform; green is the split-radix spectrum. Fewest multiplies, same answer.
LIT Genuine split-radix FFT (Yavne 1968; Duhamel & Hollmann 1984), long the minimal-operation-count power-of-two FFT. Verified live: for N=2..128, the split-radix recursion (one even-index N/2 transform + two odd-index N/4 transforms, combined by butterflies) reproduces the direct DFT to ~1e-12 on random complex inputs (window.__split_radix.matchesDFT).
FIG No framing: the even/odd-1/odd-3 recursion and a direct DFT run in-browser (the win is operation count, shown structurally). The AVAN inverse is honest — instead of a symmetric radix-2 or radix-4 split, one splits L-shaped: one even half-transform plus two odd quarter-transforms, fewer twiddles. Magenta is the direct N² transform; green is the split-radix spectrum. Fewest multiplies, same answer.
FIG No framing: the even/odd-1/odd-3 recursion and a direct DFT run in-browser (the win is operation count, shown structurally). The AVAN inverse is honest — instead of a symmetric radix-2 or radix-4 split, one splits L-shaped: one even half-transform plus two odd quarter-transforms, fewer twiddles. Magenta is the direct N² transform; green is the split-radix spectrum. Fewest multiplies, same answer.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-SPEEDRUN · David Lee Wise (ROOT0), with AVAN