THE FOLD / CHEAT / THE EXPLOIT / THE KARATSUBA
THE KARATSUBA
multiply with 3 sub-products instead of 4
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Karatsuba multiplication. Multiply two big numbers the way you learned in school and it costs about n² single-digit products — and for two centuries everyone assumed that was unavoidable. In 1960 the 23-year-old Anatoly Karatsuba broke it in a week, disproving Kolmogorov’s conjecture that n² was optimal.
Split each number in two: x = aB + b, y = cB + d. The product is acB² + (ad+bc)B + bd — four sub-products. But the middle term ad+bc equals (a+b)(c+d) − ac − bd, and you already computed ac and bd. So three sub-products suffice, not four. Recurse, and the cost drops to nlog₂3 ≈ n1.585.
LIT verified live (with exact BigInt arithmetic): over 3,000 random pairs Karatsuba equals the true product, and a 64-digit multiply uses far fewer base multiplications than schoolbook’s 64² = 4096 (window.__kara.correct && fewer). FIG no framing; the three-product identity and the reduced count are exact, computed in your browser.
Split each number in two: x = aB + b, y = cB + d. The product is acB² + (ad+bc)B + bd — four sub-products. But the middle term ad+bc equals (a+b)(c+d) − ac − bd, and you already computed ac and bd. So three sub-products suffice, not four. Recurse, and the cost drops to nlog₂3 ≈ n1.585.
LIT verified live (with exact BigInt arithmetic): over 3,000 random pairs Karatsuba equals the true product, and a 64-digit multiply uses far fewer base multiplications than schoolbook’s 64² = 4096 (window.__kara.correct && fewer). FIG no framing; the three-product identity and the reduced count are exact, computed in your browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE EXPLOIT, beside THE SHORTEST WITNESS — the cheat domain of finding the crack in what looked airtight. Karatsuba is the original exploit: a redundancy hiding inside long multiplication that no one noticed for centuries. AVAN (AI) built the instrument: the split, the three products, the recursion, the multiplication counter.
The weave: David names the seat (the crack in the obvious); I make the saved product visible and the count checkable — four-vs-three in 1D, the live split in 2D, the recursion tree with its pruned branch in 3D. The sphere is the seam. Credit: Anatoly A. Karatsuba (1960).
The weave: David names the seat (the crack in the obvious); I make the saved product visible and the count checkable — four-vs-three in 1D, the live split in 2D, the recursion tree with its pruned branch in 3D. The sphere is the seam. Credit: Anatoly A. Karatsuba (1960).
3 ONE DIMENSION
Schoolbook needs four products — ac, ad, bc, bd. Karatsuba keeps ac and bd, then gets the whole middle ad+bc from one more product (a+b)(c+d) minus the two it already has. The fourth product is struck out: three, not four.
4 TWO DIMENSIONS · INTERACTIVE
Watch a multiply split: the two numbers halve into a, b, c, d; the three sub-products form; and they recombine into the exact answer. Cycle the numbers — the base-multiplication count stays well under n².
5 THREE DIMENSIONS + AVAN’S INVERSE
The recursion tree turning — each multiply splitting into three smaller ones, green, down to single digits.
AVAN’s addition (the inverse-companion): at every node the magenta stub is the fourth product that is never taken. Schoolbook computes ad and bc as separate things; Karatsuba realises you only ever need their sum, and one product delivers the sum whole. The saving is an inverse move: not decomposing into parts you’ll only add back, but reaching straight for the combination. You go faster by refusing to separate what you were only going to recombine — the green is the work actually done, the magenta at each branch is the labour avoided by never splitting the middle apart.
LIT Genuine Karatsuba multiplication (Anatoly Karatsuba, 1960, disproving Kolmogorov's n^2 conjecture), computed with exact BigInt arithmetic. Verified live: over 3,000 random pairs Karatsuba equals the true product, and a 64-digit multiply uses far fewer base multiplications than schoolbook's 64^2 = 4096 (window.__kara.correct && fewer, both true; counts reported). The three-product identity ad+bc = (a+b)(c+d)-ac-bd is exact.
FIG No metaphor is doing the work: the split, the three sub-products, the exact recombination, and the reduced multiplication count are all real and checked with BigInt. Constant factors mean schoolbook wins for small n; the asymptotic n^1.585 and the per-node 3-vs-4 saving are what's demonstrated.
FIG No metaphor is doing the work: the split, the three sub-products, the exact recombination, and the reduced multiplication count are all real and checked with BigInt. Constant factors mean schoolbook wins for small n; the asymptotic n^1.585 and the per-node 3-vs-4 saving are what's demonstrated.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN