Toom–Cook multiplication

Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers.

Given two large integers, a and b, Toom–Cook splits up a and b into k smaller parts each of length l, and performs operations on the parts. As k grows, one may combine many of the multiplication sub-operations, thus reducing the overall computational complexity of the algorithm. The multiplication sub-operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms "Toom-3" and "Toom–Cook" are sometimes incorrectly used interchangeably, Toom-3 is only a single instance of the Toom–Cook algorithm, where k = 3.

Toom-3 reduces nine multiplications to five, and runs in $Θ (n^{\log (5) / \log (3)}) \approx Θ (n^{1.46})$ . In general, Toom- $k$ runs in $Θ (c (k) n^{e})$ , where $e = \log (2 k - 1) / \log (k)$ , $n^{e}$ is the time spent on sub-multiplications, and $c$ is the time spent on additions and multiplication by small constants (Knuth, p. 296). The Karatsuba algorithm is equivalent to Toom-2, where the number is split into two smaller ones. It reduces four multiplications to three and so operates at $Θ (n^{\log (3) / \log (2)}) \approx Θ (n^{1.58})$ .

Although the exponent $e$ can be set arbitrarily close to 1 by increasing $k$ , the constant term in the function grows very rapidly.^[1]^[2] The growth rate for mixed-level Toom–Cook schemes was still an open research problem in 2005.^[3] An implementation described by Donald Knuth achieves the time complexity $Θ (n 2^{\sqrt{2 \log n}} \log n)$ .^[4]

Because of its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity $Θ (n \log n \log \log n)$ ) becomes practical.

Toom first described this algorithm in 1963, and Cook published an improved (asymptotically equivalent) algorithm in his PhD thesis in 1966.^[5]

Details

Toom–Cook multiplication is a fast integer multiplication algorithm that reduces the number of large multiplication operations by splitting integers into smaller components and treating those components as polynomial coefficients.

The algorithm consists of five main steps:

Splitting
Evaluation
Pointwise multiplication
Interpolation
Recomposition

This section describes Toom-3 multiplication, a particular form of Toom–Cook multiplication in which each integer is divided into three parts.

Splitting

Let m and n be two integers that we want to multiply.

Choose a splitting base B, typically a power of the underlying number base. Express both integers as:

m = m_{2} B^{2} + m_{1} B + m_{0}

n = n_{2} B^{2} + n_{1} B + n_{0}

where m_i and n_i represent the individual chunks of the integers.

For example, an integer can be divided into three chunks:

m = 123456789012

m = 123456 B^{2} + 78901 B + 2

The chunks are then treated as coefficients of two quadratic polynomials:

p (x) = m_{2} x^{2} + m_{1} x + m_{0}

q (x) = n_{2} x^{2} + n_{1} x + n_{0}

These polynomials have the property:

p (B) = m

q (B) = n

Therefore, the original multiplication can be expressed as:

m n = p (B) q (B)

Evaluation

The product of two quadratic polynomials is a polynomial of degree four. Therefore, five evaluation points are sufficient to reconstruct the resulting polynomial.

Toom-3 uses the following evaluation points:

x \in {0, 1, - 1, - 2, \infty}

The two polynomials are evaluated at each point.

For p(x):

\begin{matrix} p (0) & = m_{0} \\ p (1) & = m_{0} + m_{1} + m_{2} \\ p (- 1) & = m_{0} - m_{1} + m_{2} \\ p (- 2) & = m_{0} - 2 m_{1} + 4 m_{2} \\ p (\infty) & = m_{2} \end{matrix}

Similarly, for q(x):

\begin{matrix} q (0) & = n_{0} \\ q (1) & = n_{0} + n_{1} + n_{2} \\ q (- 1) & = n_{0} - n_{1} + n_{2} \\ q (- 2) & = n_{0} - 2 n_{1} + 4 n_{2} \\ q (\infty) & = n_{2} \end{matrix}

Evaluation at infinity refers to the leading coefficient of the polynomial.

Pointwise multiplication

Once the polynomial evaluations have been calculated, multiply the corresponding values together.

Define the resulting products as:

\begin{matrix} r (0) & = p (0) q (0) \\ r (1) & = p (1) q (1) \\ r (- 1) & = p (- 1) q (- 1) \\ r (- 2) & = p (- 2) q (- 2) \\ r (\infty) & = p (\infty) q (\infty) \end{matrix}

Each multiplication involves smaller integers than the original operands.

For sufficiently large integers, these multiplications can themselves be performed recursively using Toom-Cook.

Interpolation

After pointwise multiplication, five values of the resulting polynomial are known.

The product polynomial has the form:

r (x) = r_{4} x^{4} + r_{3} x^{3} + r_{2} x^{2} + r_{1} x + r_{0}

The objective of interpolation is to recover the five unknown coefficients.

First, the constant and leading coefficients are obtained directly:

r_{0} = r (0)

r_{4} = r (\infty)

Next, calculate the following intermediate values:

s_{1} = r (1) - r_{0} - r_{4}

s_{- 1} = r (- 1) - r_{0} - r_{4}

Then calculate:

r_{2} = \frac{s_{1} + s_{- 1}}{2}

t = \frac{s_{1} - s_{- 1}}{2}

u = \frac{r (- 2) - r_{0} - 16 r_{4}}{2}

The remaining coefficients are:

r_{3} = \frac{u - 2 r_{2} - t}{3}

r_{1} = t - r_{3}

All five coefficients of the product polynomial have now been recovered.

Recomposition

The final step is to substitute the original splitting base B into the reconstructed polynomial.

Recall that:

m = p (B)

n = q (B)

Therefore, the final product is:

m n = r (B)

Expanding this expression gives:

m n = r_{4} B^{4} + r_{3} B^{3} + r_{2} B^{2} + r_{1} B + r_{0}

This reconstructs the original integer product.

Computational Complexity

Toom-3 divides each operand into three approximately equal parts and performs five recursive multiplications.

Its recurrence relation is:

T (n) = 5 T (n / 3) + O (n)

Using the Master Theorem:

T (n) = O (n^{\log_{3} 5})

Since:

\log_{3} 5 \approx 1.465

the asymptotic time complexity is:

\begin{matrix} T (n) & = O (n^{\log_{3} 5}) \\ = O (n^{1.465}) \end{matrix}

For comparison:

Algorithm	Time complexity
Schoolbook multiplication	$O (n^{2})$
Karatsuba multiplication	$O (n^{\log_{2} 3})$
Toom-3 multiplication	$O (n^{\log_{3} 5})$

Summary

Toom-3 multiplication reduces the number of recursive multiplication operations by representing integers as polynomials and using polynomial interpolation.

The five main stages are:

Splitting the integers into three parts.
Evaluating the corresponding polynomials at five points.
Multiplying the evaluated values.
Interpolating the resulting polynomial coefficients.
Reconstructing the original integer product.

The main advantage of Toom-Cook multiplication is that it exchanges expensive multiplication operations for comparatively inexpensive additions, subtractions and divisions by small constants.

Asymmetric splitting

The interpolation step depends on the degree of the product polynomial, which is the sum of the degrees of the factor polynomials, but not on the individual degrees. While basic Toom-3 divides each factor into 3 parts (quadratic polynomials), if the factors differ in size, it can be beneficial to split one into 2 parts (a linear polynomial) and the other into 4 parts (a cubic) with coefficients of more balanced size. Then the same interpolation step can produce a quartic product polynomial

For Toom-3, this is the only interesting alternative split (the degenerate case of splitting either factor into only 1 part offers no time saving), but higher-degree Toom-Cook allows additional possibilities.

In addition to the equal-split cases, it's possible to have half-integer cases which are always asymmetric; the total number of pieces is odd, and the degree of the product polynomial is even. For example, Toom-2.5 splits one factor into 2 parts and the other into 3, while Toom-3.5 can split the factors as 2+5 or 3+4.

Interpolation matrices for various k

Here we give common interpolation matrices for a few different common small values of k_m and k_n.

Toom-1

Applying formally the definition, we may consider Toom-1 (k_m = k_n = 1). This does not yield a multiplication algorithm, but a recursive algorithm that never halts, as it trivially reduces each input instance to a recursive call with the same instance. The algorithm requires 1 evaluation point, whose value is irrelevant, as it is used only to "evaluate" constant polynomials. Thus, the interpolation matrix is the identity matrix:

{(\begin{matrix} 1 \end{matrix})}^{- 1} = (\begin{matrix} 1 \end{matrix}) .

Toom-1.5

Toom-1.5 (k_m = 2, k_n = 1) is still degenerate: it recursively reduces one input by halving its size, but leaves the other input unchanged, hence we can make it into a multiplication algorithm only if we supply a 1 × n multiplication algorithm as a base case (whereas the true Toom–Cook algorithm reduces to constant-size base cases). It requires 2 evaluation points, here chosen to be 0 and ∞. Its interpolation matrix is then the identity matrix:

{(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix})}^{- 1} = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) .

The algorithm is essentially equivalent to a form of long multiplication: both coefficients of one factor are multiplied by the sole coefficient of the other factor.

Toom-2

Toom-2 (k_m = 2, k_n = 2) requires 3 evaluation points, here chosen to be 0, 1, and ∞. It is the same as Karatsuba multiplication, with an interpolation matrix of:

{(\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})}^{- 1} = (\begin{matrix} 1 & 0 & 0 \\ - 1 & 1 & - 1 \\ 0 & 0 & 1 \end{matrix}) .

Toom-2.5

Toom-2.5 (k_m = 3, k_n = 2) requires 4 evaluation points, here chosen to be 0, 1, −1, and ∞. It then has an interpolation matrix of:

{(\begin{matrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & - 1 & 1 & - 1 \\ 0 & 0 & 0 & 1 \end{matrix})}^{- 1} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} & - \frac{1}{2} & - 1 \\ - 1 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 0 & 1 \end{matrix}) .

Notes

↑ Knuth, p. 296
↑ Crandall & Pomerance, p. 474
↑ Crandall & Pomerance, p. 536
↑ Knuth, p. 302
↑ Positive Results, chapter III of Stephen A. Cook: On the Minimum Computation Time of Functions.

References

D. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley, 1997. Section 4.3.3.A: Digital methods, pg.294.
R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Second Edition, Springer, 2005. Section 9.5.1: Karatsuba and Toom–Cook methods, pg.473.
Bodrato, Marco (2007). "Towards optimal Toom–Cook multiplication for univariate and multivariate polynomials in characteristic 2 and 0". In Carlet, Claude; Sunar, Berk (eds.). Arithmetic of Finite Fields, First International Workshop, WAIFI 2007, Madrid, Spain, June 21–22, 2007, Proceedings. Lecture Notes in Computer Science. Vol. 4547. Springer. pp. 116–133. doi:10.1007/978-3-540-73074-3_10. ISBN 978-3-540-73073-6.
Bodrato, Marco (August 8, 2011). "Optimal Toom-Cook Polynomial Multiplication / Toom Cook convolution, implementation for polynomials". Retrieved 22 September 2023.

External links

Toom–Cook 3-way multiplication from GMP documentation: "Toom 3-Way Multiplication". GNU MP multiple precision arithmetic library (version 6.3.0) manual. Free Software Foundation, Inc. 30 July 2023 [Copyright 1991, 1993-2016, 2018-2020].

[Knuth,_p._296-1] Knuth, p. 296

[2] Crandall & Pomerance, p. 474

[3] Crandall & Pomerance, p. 536

[4] Knuth, p. 302

[5] Positive Results, chapter III of Stephen A. Cook: On the Minimum Computation Time of Functions.

[1]

[2]

[3]

[4]

[5]

v t e Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms