🔗 Toom–Cook multiplication

🔗 Mathematics

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 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 9 multiplications to 5, and runs in Θ(n^{log(5)/log(3)}) ≈ Θ(n^1.46). In general, Toom-k runs in Θ(c(k) n^e), where e = log(2k − 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. The Karatsuba algorithm is a special case of Toom–Cook, where the number is split into two smaller ones. It reduces 4 multiplications to 3 and so operates at Θ(n^{log(3)/log(2)}) ≈ Θ(n^1.58). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ(n²).

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

Due to 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.