Toom-Cook Algorithm: Generalizing Karatsuba

This article provides an overview of how the Toom-Cook multiplication algorithm generalizes Karatsuba multiplication by partitioning large integers into an arbitrary number of limbs. By treating multi-precision binary numbers as polynomials, Toom-Cook reduces the asymptotic time complexity of large integer multiplication through polynomial evaluation, recursive point-wise multiplication, and linear interpolation before reconstructing the final binary result.

From Karatsuba to Toom-Cook

Standard Karatsuba multiplication splits each large integer into two equal halves (\(k = 2\)), reducing four sub-multiplications down to three. This yields an asymptotic time complexity of \(\mathcal{O}(n^{\log_2 3}) \approx \mathcal{O}(n^{1.585})\).

The Toom-Cook algorithm (often denoted as Toom-\(k\)) generalizes this principle to an arbitrary integer \(k > 1\). Instead of splitting numbers into two parts, Toom-\(k\) partitions each integer into \(k\) equal-sized blocks or “limbs.” While standard schoolbook multiplication of two \(k\)-limb integers requires \(k^2\) smaller multiplications, Toom-\(k\) achieves the same result using only \(2k - 1\) smaller multiplications. Karatsuba is simply the specific case where \(k = 2\).

Partitioning Binary Integers into Limbs

In modern computer architectures, multi-precision integers are stored in binary. To multiply two large integers \(U\) and \(V\), Toom-\(k\) chooses a base \(B = 2^m\), where \(m\) is typically a multiple of the machine’s word size (such as 32 or 64 bits).

Each integer is sliced into \(k\) limbs of \(m\) bits each:

\[U = \sum_{i=0}^{k-1} u_i B^i = u_{k-1} B^{k-1} + \dots + u_1 B + u_0\]

\[V = \sum_{i=0}^{k-1} v_i B^i = v_{k-1} B^{k-1} + \dots + v_1 B + v_0\]

By replacing the base \(B\) with an indeterminate variable \(x\), the integers are mapped directly to degree-\((k-1)\) polynomials:

\[P(x) = u_{k-1} x^{k-1} + \dots + u_1 x + u_0\]

\[Q(x) = v_{k-1} x^{k-1} + \dots + v_1 x + v_0\]

The product of the two original integers is the product polynomial \(W(x) = P(x) \cdot Q(x)\) evaluated at \(x = B\).

The Five Steps of Toom-\(k\)

The algorithm computes the product \(W(x)\) through five distinct steps:

1. Splitting

The binary inputs are divided into \(k\) limbs, creating the coefficients for \(P(x)\) and \(Q(x)\). If the bit-length of the input is not evenly divisible by \(k\), it is zero-padded.

2. Evaluation

The product polynomial \(W(x) = P(x)Q(x)\) has degree \(2k - 2\), which means it possesses \(2k - 1\) unknown coefficients. According to polynomial interpolation theorems, a polynomial of degree \(d\) is uniquely determined by its values at \(d + 1\) distinct points.

Toom-\(k\) evaluates both \(P(x)\) and \(Q(x)\) at \(2k - 1\) chosen small integer or fractional points (such as \(0, 1, -1, 2, -2, \dots, \infty\)). Evaluating at points like \(0\) and \(\infty\) requires virtually no computation (yielding the lowest and highest coefficients directly), while points like powers of two simplify to fast binary shift and addition operations.

3. Pointwise Multiplication

The algorithm computes \(W(\alpha) = P(\alpha) \cdot Q(\alpha)\) for each of the \(2k - 1\) evaluation points \(\alpha\). This step accounts for the bulk of the computation and is performed recursively using smaller instances of multiplication.

4. Interpolation

Given the \(2k - 1\) values of \(W(\alpha)\), a system of linear equations is solved to recover the coefficients \(w_i\) of the product polynomial:

\[W(x) = w_{2k-2} x^{2k-2} + \dots + w_1 x + w_0\]

Because the evaluation points are fixed constants determined in advance by the algorithm designer, the matrix inversion required for interpolation can be hardcoded into a sequence of simple additions, subtractions, and exact divisions by small constants.

5. Recomposition and Carry Propagation

Once the coefficients \(w_i\) are found, the algorithm computes \(W(B)\) to obtain the final integer:

\[W(B) = \sum_{i=0}^{2k-2} w_i B^i\]

Since \(B = 2^m\), multiplying by \(B^i\) corresponds to shifting the limbs left by \(i \cdot m\) bits. The limbs are added together, and any values exceeding the limb size \(2^m\) are resolved via carry propagation from the least significant limb to the most significant limb.

Complexity and Practical Application

The runtime complexity of Toom-\(k\) is governed by the \(2k - 1\) recursive multiplications of size \(n/k\):

\[\mathcal{O}\left(n^{\log_k(2k - 1)}\right)\]

As \(k\) increases, the asymptotic growth rate drops:

As \(k \to \infty\), the complexity approaches \(\mathcal{O}(n \cdot 2^{\sqrt{2\log_2 n}})\), bridging the gap between basic divide-and-conquer methods and the Fast Fourier Transform (FFT) based Schönhage–Strassen and Harvey–Hoeven algorithms. In practical big-integer libraries such as GNU MP (GMP), Toom-3 and Toom-4 are actively used for numbers spanning thousands of bits before switching to FFT-based approaches.