Everyone multiplies long numbers the way you learned in school: n² digit-products. In 1960 a 23-year-old showed you can do it in three multiplications instead of four per split — and in doing so disproved his professor’s conjecture in a week. The recursion runs in I-13; only its reason to exist — enormous numbers — asks for the one withheld feature.
THE TECHNIQUE buy one multiply with two adds
Split each number into high and low halves. The naive product needs four sub-products; Karatsuba computes a=xh·yh, d=xl·yl, and one cross term (xh+xl)(yh+yl)−a−d — three multiplications. Recursively, that turns n² into ≈n1.585. live demo
HISTORY & CREDIT a week that broke a conjecture
The polite version — “Karatsuba improved multiplication” — buries the drama: he demolished a Kolmogorov conjecture, fast. cited
1960 · Andrey Kolmogorov, at a Moscow State seminar, conjectures multiplication requires Ω(n²) operations — a lower bound he believed firm. within a week · Anatoly Karatsuba, 23, in that seminar, finds the three-multiply split — disproving the conjecture. Kolmogorov was reportedly amazed and ended the seminar. the twist · Kolmogorov wrote up the result himself (1962), under Karatsuba’s name — and Karatsuba said he only learned it was published from the reprints mailed to him. after · it opened the whole field of fast algorithms — Toom–Cook, then Schönhage–Strassen, then Harvey–van der Hoeven’s 2019 O(n log n).
Credit given generously here: the professor publishing the student’s refutation of the professor. the good kind
RECOMMEND FOR I-13 runs — but its purpose needs bignum
Split (via % and /), three recursive multiplies, recombine. I-13 runs it and gets the exact product:
$ i13 run karatsuba.i13
k = 7006652 # Karatsuba split (base 100)
direct = 7006652 # 1234 * 5678 -> they MATCH
Recommend: the withheld arbitrary-precision integers — and Karatsuba is the sharpest case for them yet. The algorithm exists for multiplying numbers with thousands of digits, where it beats schoolbook badly; on f64 (≤ ~15 exact digits) the recursion is correct but there is nothing big enough to be worth it. The math runs on the 13 symbols; its reason to exist is exactly the value kind the corpus has, so far, chosen not to add. The tally: darts 032, 035, 036 and now 041 all land on bignum. Four independent darts → the clearest single architectural signal the campaign has produced. The author’s call, on the record.