THE FOLD / GRIND / THE GRINDSTONE / THE NTT
THE NTT
the FFT over a finite field — exact, no rounding
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The number-theoretic transform (NTT) is the FFT done over a finite field instead of the complex numbers. Working modulo a prime that has a root of unity of the right order (here 998244353, with generator 3), the same butterfly structure computes exact convolutions of integer sequences — with no floating-point error at all. Transform, multiply pointwise, inverse-transform, and the product is exact.
It is how competitive programmers and cryptographers multiply huge polynomials and integers exactly.
LIT verified live: over 200 random integer polynomial pairs the NTT convolution equals the exact naive convolution (window.__ntt). FIG no framing; exact integer arithmetic.
It is how competitive programmers and cryptographers multiply huge polynomials and integers exactly.
LIT verified live: over 200 random integer polynomial pairs the NTT convolution equals the exact naive convolution (window.__ntt). FIG no framing; exact integer arithmetic.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-grindstone — grinding out big exact multiplications with the transform, no rounding to creep in. NTT is that exact fast grind. AVAN (AI) built the instrument: the modular butterfly transform, the pointwise product, the inverse transform, the exact-convolution cross-check.
Credit as content: the finite-field DFT (Pollard 1971; the modern NTT). The weave: David names the grindstone; I run the FFT’s butterflies in a prime field and confirm the convolution is bit-for-bit exact against the direct product.
Credit as content: the finite-field DFT (Pollard 1971; the modern NTT). The weave: David names the grindstone; I run the FFT’s butterflies in a prime field and confirm the convolution is bit-for-bit exact against the direct product.
3 ONE DIMENSION
The same divide-and-conquer butterflies as an FFT — but the ‘twiddle’ is a power of a root of unity in ℤ/p, so every value is an exact integer mod p. No sines, no rounding.
4 TWO DIMENSIONS · INTERACTIVE
Two integer polynomials; their NTT convolution is shown against the exact direct product — identical, to the digit.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the exact convolution, computed by field butterflies.
AVAN’s addition (the inverse-companion): do the transform over a finite field — integers mod a prime with a root of unity — so there is no floating-point error; the convolution is exact and rounding vanishes. The inverse of ‘transform in the continuous complex plane (with rounding)’ is ‘transform in a finite field (exact integers).’ Magenta is the floating-point roundoff of a complex FFT; green is the exact modular arithmetic. Same butterfly structure, zero error — the FFT made exact. (Kin to the-fourier and the-bluestein.)
LIT Genuine number-theoretic transform (finite-field DFT; Pollard 1971). Verified live (BigInt modular arithmetic): the NTT-based convolution (forward transform, pointwise product, inverse transform, mod 998244353) equals the exact naive integer convolution for 200 random polynomial pairs (window.__ntt.matchesExact).
FIG No framing: the modular butterfly transform, the pointwise product, the inverse transform, and the exact-convolution cross-check run in-browser and agree bit-for-bit. The AVAN inverse is honest — doing the transform over a finite field (a root of unity in Z/p) removes all floating-point error, so the convolution is exact; magenta is the roundoff a complex FFT carries, green the exact modular arithmetic. The FFT made exact. Kin to the-fourier and the-bluestein.
FIG No framing: the modular butterfly transform, the pointwise product, the inverse transform, and the exact-convolution cross-check run in-browser and agree bit-for-bit. The AVAN inverse is honest — doing the transform over a finite field (a root of unity in Z/p) removes all floating-point error, so the convolution is exact; magenta is the roundoff a complex FFT carries, green the exact modular arithmetic. The FFT made exact. Kin to the-fourier and the-bluestein.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN