The site's thirteenth Number Theory entry, and the direct generalization of the twelfth: Karatsuba Multiplication splits each number into 2 half-size parts and gets away with 3 sub-multiplications instead of the schoolbook 4. Toom-Cook multiplication — specifically the Toom-3 variant this page builds — splits each number into 3 third-size parts and gets away with 5 sub-multiplications instead of the schoolbook 9, the same split-and-combine idea taken one step further. The two-part split has an algebraic shortcut simple enough to spot directly (Karatsuba's own page derives it in three lines); the three-part split doesn't have an equally short shortcut, so Toom-3 reaches for a different, more general tool instead: treat each number as a small polynomial, and recover the product polynomial by evaluating at a handful of points, multiplying the point-values directly, and interpolating back.
Enter two non-negative integers (up to 5 digits each) and press Build. Step through
the recursion: each node is one call multiplying two numbers, splitting each into three parts, evaluating
both at x = 0, 1, -1, 2, ∞ to get five pairs of smaller numbers, recursing on each pair, then
interpolating the five results back into the answer. A node with both operands under 10 is a base case
— direct single-digit multiplication, counted in the stats line below. The checkbox reproduces a
real, checked bug — see Pitfalls.
Split an n-digit number x into three parts at a shared base
B (a power of ten): x = x2·B² + x1·B +
x0. That's the same shape as reading off the coefficients of a degree-2 polynomial
X(t) = x2t² + x1t + x0 at t = B. Two such
numbers a and b correspond to two degree-2 polynomials A(t) and
B(t), and their product a·b is A(t)·B(t) evaluated
at t = B — but A(t)·B(t) is itself a polynomial, of degree 4, with
five unknown coefficients c0...c4. A degree-4 polynomial is uniquely
determined by its value at any five distinct points, so the plan is: evaluate A and
B at five cheap points, multiply the five pairs of point-values directly (five
sub-multiplications, each on numbers not much bigger than a third-size part), then solve for
c0...c4 from those five products.
The standard Toom-3 points are 0, 1, -1, 2, and ∞ (shorthand for "the
leading coefficient," read off directly rather than evaluated), chosen because they keep the evaluated
numbers small: A(0) = a0, A(1) = a0+a1+a2,
A(-1) = a0-a1+a2, A(2) =
a0+2a1+4a2, A(∞) = a2 — and likewise
for B. Multiplying each pair gives v0, v1, v-1,
v2, v∞. Two of the five coefficients fall out immediately:
c0 = v0 and c4 = v∞. Subtracting
those known contributions from v1, v-1, and
v2 leaves three linear equations in the three remaining unknowns
c1, c2, c3, which solve cleanly to c2 =
(v1'+v-1')/2, then c3 =
((v2'-4c2)/2 - (v1'-v-1')/2) / 3, and
c1 from what's left over (the reference implementation below spells out every
step). The final answer is c4·B⁴ + c3·B³ +
c2·B² + c1·B + c0. Each of the five
sub-multiplications is itself recursively split the same way until an operand is small enough to
multiply directly, giving the recurrence T(n) = 5T(n/3) + O(n) — five subproblems of
a third the size, plus linear-time splitting and interpolating — which solves to
O(nlog&sub2;5) = O(nlog5⁄log3) ≈ O(n1.465) by
the same Master Theorem argument Karatsuba's own
page uses for its O(n1.585).
This is the exact algorithm the demo above steps through (numbers kept as plain JavaScript integers,
small enough to stay well under Number.MAX_SAFE_INTEGER; a production implementation would
use digit arrays or a bignum type instead):
function digits(n) { return n === 0 ? 1 : String(n).length; }
function toomCook(a, b) {
if (a < 10 || b < 10) return a * b; // base case: direct single-digit multiply
const chunk = Math.ceil(Math.max(digits(a), digits(b)) / 3);
const base = 10 ** chunk;
const a0 = a % base, a1 = Math.floor(a / base) % base, a2 = Math.floor(a / (base * base));
const b0 = b % base, b1 = Math.floor(b / base) % base, b2 = Math.floor(b / (base * base));
const Av0 = a0, Bv0 = b0;
const Av1 = a0 + a1 + a2, Bv1 = b0 + b1 + b2;
const Avm1 = a0 - a1 + a2, Bvm1 = b0 - b1 + b2; // can go negative -- see Pitfalls
const Av2 = a0 + 2*a1 + 4*a2, Bv2 = b0 + 2*b1 + 4*b2;
const Avinf = a2, Bvinf = b2;
function rmul(x, y) { // signed multiply via a non-negative recursion
const sign = (x < 0) !== (y < 0) ? -1 : 1;
return sign * toomCook(Math.abs(x), Math.abs(y)); // both sign extraction and reapplication matter
}
const v0 = rmul(Av0, Bv0);
const v1 = rmul(Av1, Bv1);
const vm1 = rmul(Avm1, Bvm1);
const v2 = rmul(Av2, Bv2);
const vinf = rmul(Avinf, Bvinf);
const c0 = v0, c4 = vinf;
const v1p = v1 - c0 - c4, vm1p = vm1 - c0 - c4, v2p = v2 - c0 - 16 * c4;
const c2 = (v1p + vm1p) / 2;
const S = (v1p - vm1p) / 2;
const T = (v2p - 4 * c2) / 2;
const c3 = (T - S) / 3;
const c1 = S - c3;
return c4 * base**4 + c3 * base**3 + c2 * base**2 + c1 * base + c0;
}Verified against native multiplication exhaustively (every integer pair with a under
3,000 and b under 3,000 stepping by 7, 184,041 pairs, 0 mismatches) and against 300,000
randomized pairs with both operands up to 6 digits, 0 mismatches in both sweeps. Correctness at scale was
checked separately with a BigInt version (no floating-point precision ceiling): 2,000 randomized pairs
with both operands up to 40 digits, 0 mismatches.
Dropping the sign at the x = -1 evaluation point is a checked, frequent failure
— and it's a genuinely new failure mode this algorithm introduces, not a repeat of Karatsuba's own
bugs. Karatsuba's three evaluation points (low×low, high×high, and a sum of two
non-negative halves) are all non-negative by construction for non-negative inputs, so Karatsuba's
reference implementation never has to think about sign at all. Toom-3's x = -1 point,
a0 - a1 + a2, has no such guarantee — it goes negative
whenever the middle part outweighs the two outer parts, which happens for perfectly ordinary inputs. The
checkbox above reproduces the mistake of recursing on Math.abs(x) and
Math.abs(y) but never reapplying the sign the two originally implied (the
rmul helper above without its sign * factor). The smallest clean divergent
example: 100 × 120. The correct algorithm gives 12,000; with the sign
dropped, 11,760 — because a splits to a0=0,
a1=0, a2=1 (so Av-1 = 1) while b splits
to b0=0, b1=2, b2=1 (so Bv-1 = -1):
one positive, one negative, a sign the buggy version silently discards. Swept across 300,000 randomized
pairs (both operands up to 6 digits): 97.8% disagree with the correct product —
not every pair, since the bug is invisible whenever both evaluation results at x = -1
happen to carry the same sign (both positive, or both negative, cancel out in the product either way),
but the overwhelming majority of pairs trigger it somewhere across the recursion.
O(nlog5⁄log3) ≈ O(n1.465) single-digit
multiplications for two n-digit numbers, against schoolbook's O(n²) and
Karatsuba's O(n1.585) — asymptotically the best of the three. But the
reference implementation above recurses all the way down to single digits, and five sub-multiplications
plus interpolation overhead per level is not free: measured over 2,000 randomized trials at each size,
2-digit pairs need 7.09 single-digit multiplications on average (schoolbook needs only
4), 4-digit pairs need 31.46 (schoolbook 16), 7-digit
pairs need 79.52 (schoolbook 49) — Toom-3 is worse than
schoolbook at every one of these sizes. A wider sweep (3,000 trials per size, using exact BigInt
arithmetic to check sizes too large for ordinary floating-point numbers) finds where that flips: at 12
digits schoolbook still wins narrowly (144 against a measured 157.8), but by 13 digits Toom-3 has pulled
ahead (169 against a measured 146.1), and the gap only widens — at 27 digits, 729 against
576.0; at 81 digits, 6,561 against 2,961.8. Each tripling of digit count multiplies schoolbook's exact
cost by precisely 9 (its cost is exactly n², no randomness involved) while Toom-3's
measured cost grows only ×5.1 to ×5.6 per tripling —
close to the ×5 the T(n) = 5T(n/3) recurrence predicts, and visibly
slower-growing than schoolbook's ×9, exactly the asymptotic win the exponent promises,
just one that only shows up once the recursion has enough levels to amortize its own overhead.
Space: O(n) for the digit representation of intermediate values, with
O(log n) recursion depth. Real bignum libraries don't recurse to single digits the way the
reference implementation above does for clarity — they measure their own crossover points
empirically and switch strategies as numbers grow: schoolbook multiplication below a few dozen digits,
Karatsuba above that, Toom-3 (and sometimes
higher-order Toom-k variants, splitting into more than three parts at the cost of
proportionally more evaluation points and messier interpolation formulas) above that, and
Fast Fourier Transform-based convolution once the
numbers are large enough that O(n log n) is worth its own larger constant factor — the
same four-tier ladder GMP and Python's arbitrary-precision int both climb in practice, each
rung covered by one of this site's last three Number Theory entries.
This site's guide, Choosing a Number Theory Algorithm, sets this page and its two siblings aside from the rest of the category for that reason — every other Number Theory entry treats a multiplication as a single cheap step, an assumption that stops holding at this scale. Toom-Cook is the middle rung: reach for it once Karatsuba's split-in-two has itself been outgrown, and before the numbers are large enough that FFT-based convolution's larger constant factor pays for itself.