THE FOLD / CHEAT / THE-SHORTCUT / THE PRIME-FACTOR FFT
THE PRIME-FACTOR FFT
a prime-factored DFT with no twiddles
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The prime-factor (Good–Thomas) FFT splits a DFT of size N = N₁·N₂ into a two-dimensional DFT — and, uniquely, needs no twiddle factors at all. Its secret is the Chinese Remainder Theorem: when N₁ and N₂ are coprime, the index n can be re-mapped so that a single 1-D transform factors cleanly into an N₁-point transform along one axis and an N₂-point transform along the other, with the cross terms vanishing outright. Cooley–Tukey needs twiddle multiplications between stages; Good–Thomas replaces them with a pure re-indexing, trading arithmetic for a clever permutation.
LIT verified live: for coprime factorizations N = 12, 15, 20, 21, 35, the CRT-reindexed twiddle-free 2-D DFT equals the direct DFT to ~1e-13 (window.__prime_factor_fft). FIG no framing; the CRT input/output maps and the two-axis DFT run in-browser (the speedup comes from doing each axis with a small FFT).
LIT verified live: for coprime factorizations N = 12, 15, 20, 21, 35, the CRT-reindexed twiddle-free 2-D DFT equals the direct DFT to ~1e-13 (window.__prime_factor_fft). FIG no framing; the CRT input/output maps and the two-axis DFT run in-browser (the speedup comes from doing each axis with a small FFT).
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-shortcut — coprime sizes let the CRT reindex a prime-factored DFT into a grid with no twiddle multiplications. AVAN (AI) built the instrument: the CRT input map, the Ruritanian output map, the two-axis DFT, and the match against a direct DFT.
Credit as content: I. J. Good (1958) & L. H. Thomas (the prime-factor algorithm). The weave: David names the shortcut; I confirm the coprime re-indexing computes the exact DFT without a single twiddle factor.
Credit as content: I. J. Good (1958) & L. H. Thomas (the prime-factor algorithm). The weave: David names the shortcut; I confirm the coprime re-indexing computes the exact DFT without a single twiddle factor.
3 ONE DIMENSION
For coprime N=N₁·N₂, the CRT re-maps the 1-D index into an N₁×N₂ grid — the DFT factors along the two axes, no twiddles.
4 TWO DIMENSIONS · INTERACTIVE
Pick a coprime N=N₁·N₂; the prime-factor DFT and the direct DFT agree exactly — with no twiddle multiplications.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the spectrum, from a twiddle-free grid.
AVAN’s addition (the inverse-companion): don’t multiply twiddles between stages — permute by the CRT. The inverse of ‘Cooley–Tukey’s twiddle stages’ is ‘coprime sizes let a re-indexing split the DFT into two axes with no cross terms.’ Magenta is the twiddle-laden direct transform; green is the twiddle-free 2-D grid. Arithmetic traded for a permutation.
LIT Genuine prime-factor / Good–Thomas FFT (I. J. Good 1958; L. H. Thomas). Verified live: for coprime factorizations N=12,15,20,21,35, the CRT input map n=(N₂n₁+N₁n₂) mod N and Ruritanian output map, giving a twiddle-free 2-D DFT, equals the direct DFT to ~1e-13 (window.__prime_factor_fft.matchesDFT).
FIG No framing: the CRT input/output maps and the two-axis DFT run in-browser (the actual speedup comes from doing each axis with a small FFT). The AVAN inverse is honest — instead of Cooley–Tukey's twiddle multiplications between stages, coprime sizes let a CRT re-indexing split the DFT into two axes with no cross terms. Magenta is the twiddle-laden direct transform; green is the twiddle-free 2-D grid. Arithmetic traded for a permutation.
FIG No framing: the CRT input/output maps and the two-axis DFT run in-browser (the actual speedup comes from doing each axis with a small FFT). The AVAN inverse is honest — instead of Cooley–Tukey's twiddle multiplications between stages, coprime sizes let a CRT re-indexing split the DFT into two axes with no cross terms. Magenta is the twiddle-laden direct transform; green is the twiddle-free 2-D grid. Arithmetic traded for a permutation.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-SHORTCUT · David Lee Wise (ROOT0), with AVAN