THE FOLD / GRIND / THE GRINDSTONE / THE TOOM-COOK
THE TOOM-COOK
multiplication as evaluate-multiply-interpolate (~n^1.46)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Toom–Cook multiplication (Toom-3) multiplies big numbers faster than the schoolbook n² by treating each number as a polynomial. Split both into 3 parts, evaluate each at 5 points, multiply those 5 values (5 small products instead of 9), then interpolate the product polynomial and recombine — giving about n1.46.
It generalises Karatsuba (which is Toom-2) and bridges toward FFT-based multiplication for very large numbers.
LIT verified live: over 300 random polynomial pairs the Toom-3 product equals the direct convolution exactly (window.__toomcook). FIG no framing; exact.
It generalises Karatsuba (which is Toom-2) and bridges toward FFT-based multiplication for very large numbers.
LIT verified live: over 300 random polynomial pairs the Toom-3 product equals the direct convolution exactly (window.__toomcook). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-grindstone — grinding through the biggest multiplications with fewer sub-products, evaluate–multiply–interpolate. Toom–Cook is that faster grind. AVAN (AI) built the instrument: the 5-point evaluation, the pointwise products, the Lagrange interpolation, the convolution cross-check.
Credit as content: Andrei Toom (1963) & Stephen Cook (1966). The weave: David names the grindstone; I split each number into three, multiply at five sample points, interpolate the answer, and confirm it matches the direct product.
Credit as content: Andrei Toom (1963) & Stephen Cook (1966). The weave: David names the grindstone; I split each number into three, multiply at five sample points, interpolate the answer, and confirm it matches the direct product.
3 ONE DIMENSION
Each number split into three limbs becomes a degree-2 polynomial. The product is degree 4, so five sample points (0, 1, −1, 2, −2) determine it exactly.
4 TWO DIMENSIONS · INTERACTIVE
Two polynomials; Toom-3 evaluates, multiplies at 5 points, and interpolates the product — matched against the direct convolution.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the product, reconstructed from five point-products.
AVAN’s addition (the inverse-companion): multiplication becomes evaluate–multiply–interpolate. Turn each number into a polynomial, sample both at 5 points, multiply those 5 values, and interpolate the product polynomial back — 5 small multiplies instead of 9. The inverse of ‘convolve the digits directly’ is ‘sample, multiply pointwise, interpolate.’ Magenta is the n² digit-products you skip; green is the 5 point-products that determine everything. Multiplication as interpolation — Karatsuba is the Toom-2 case, and pushing the point count toward the limit is the FFT.
LIT Genuine Toom-Cook / Toom-3 multiplication (Toom 1963; Cook 1966). Verified live: the split-evaluate(5 points)-pointwise-multiply-interpolate pipeline reproduces the direct convolution of two coefficient vectors exactly for 300 random pairs (window.__toomcook.matchesConv).
FIG No framing: the 5-point evaluation, the pointwise products, the Lagrange interpolation, and the convolution cross-check run in-browser and agree exactly. The AVAN inverse is honest — turning numbers into polynomials, multiplying at 5 sample points, and interpolating recovers the product with 5 multiplies instead of 9; magenta is the n^2 digit-products skipped, green the 5 point-products. Karatsuba is the Toom-2 case; the FFT is the limit.
FIG No framing: the 5-point evaluation, the pointwise products, the Lagrange interpolation, and the convolution cross-check run in-browser and agree exactly. The AVAN inverse is honest — turning numbers into polynomials, multiplying at 5 sample points, and interpolating recovers the product with 5 multiplies instead of 9; magenta is the n^2 digit-products skipped, green the 5 point-products. Karatsuba is the Toom-2 case; the FFT is the limit.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GRINDSTONE · David Lee Wise (ROOT0), with AVAN