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

)

)

≈

Θ

(

n

1.46

)

{\displaystyle \Theta (n^{\log(5)/\log(3)})\approx \Theta (n^{1.46})}

.

In general, Toom-

k

{\displaystyle k}

runs in

Θ

(

c

(

k

)

n

e

)

{\displaystyle \Theta (c(k)n^{e})}

, where

e

=

log

⁡

(

2

k

−

1

)

/

log

⁡

(

k

)

{\displaystyle e=\log(2k-1)/\log(k)}

,

n

e

{\displaystyle n^{e}}

is the time spent on sub-multiplications, and

c

{\displaystyle 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

)

)

≈

Θ

(

n

1.58

)

{\displaystyle \Theta (n^{\log(3)/\log(2)})\approx \Theta (n^{1.58})}

.