Toom-Cook Algorithm

Purpose: Multiply two large numbers (or polynomials) in $O (n^{l o g_{k} (2 k - 1)})$ by splitting each operand into $k$ parts. Karatsuba is the case $k = 2$ ; Toom-3 ( $k = 3$ ) gives $O (n^{1.465})$ .

The Idea: evaluate, multiply, interpolate

Treat each operand as a polynomial in the split radix $B = 2^{m}$ :

$A (x) = a_{0} + a_{1} x + \dots + a_{k - 1} x^{k - 1}, A = A (B) .$

The product $C = A B$ corresponds to $C (x) = A (x) B (x)$ , a polynomial of degree $2 k - 2$ , hence determined by $2 k - 1$ values. So:

Evaluate $A$ and $B$ at $2 k - 1$ small points, typically ${0, 1, - 1, 2, - 2, \dots, \infty}$ (where $\infty$ means “take the leading coefficient”).
Multiply pointwise — $2 k - 1$ recursive multiplications of size $n / k$ .
Interpolate to recover the coefficients of $C$ , by solving a small Vandermonde system with a fixed, precomputed sequence of additions, subtractions and small-constant divisions.
Recompose: $C = \sum c_{i} B^{i}$ , propagating carries.

Complexity

$T (n) = (2 k - 1) T (n / k) + O (n) \Rightarrow T (n) = Θ (n^{l o g_{k} (2 k - 1)}) .$

$k$	Name	Exponent
2	Karatsuba (Toom-2)	$lo g_{2} 3 \approx 1.585$
3	Toom-3	$lo g_{3} 5 \approx 1.465$
4	Toom-4	$lo g_{4} 7 \approx 1.404$
$k \to \infty$	—	$\to 1$ , but the linear overhead explodes

The catch: the interpolation step’s constant grows rapidly with $k$ . Toom-4 needs many more additions and divisions than Toom-3, so the crossover keeps moving. Real libraries stop around Toom-4 or Toom-8 and switch to FFT.

The multiplication ladder (GMP-style thresholds)

Operand size	Method
< ~30 limbs	schoolbook $O (n^{2})$
~30 – 300	Karatsuba
~300 – 1000	Toom-3
~1000 – 3000	Toom-4 / Toom-6.5 / Toom-8.5
> ~3000	Schönhage-Strassen / FFT

Toom-3 worked out

Split into 3 parts, evaluate at ${0, 1, - 1, 2, \infty}$ :

p_{0} p_{1} p_{- 1} p_{2} p_{\infty} = a_{0}, = a_{0} + a_{1} + a_{2}, = a_{0} - a_{1} + a_{2}, = a_{0} + 2 a_{1} + 4 a_{2}, = a_{2}, q_{0} q_{1} q_{- 1} q_{2} q_{\infty} = b_{0} = b_{0} + b_{1} + b_{2} = b_{0} - b_{1} + b_{2} = b_{0} + 2 b_{1} + 4 b_{2} = b_{2}

Five recursive products $r_{i} = p_{i} q_{i}$ , then a fixed sequence of ~10 additions and two exact divisions (by 2 and 3) recovers $c_{0} .. c_{4}$ . Every division is exact, so no precision is lost.

The connection to FFT

Toom-Cook is evaluate-multiply-interpolate at a handful of small integer points. The FFT is the same three steps at $n$ roots of unity, where evaluation and interpolation themselves become $O (n lo g n)$ instead of $O (n)$ -with-a-huge-constant. Seeing them as one family is the useful insight.

Variants / Use Cases

Karatsuba — the $k = 2$ case, the one worth implementing by hand
Big Integer Multiplication — the topic page
Schönhage-Strassen — where the ladder ends
Unbalanced Toom variants — for multiplying operands of very different sizes

whoashish's cp notes

Directory