Toom-Cook multiplication
From Free net encyclopedia
Deco (Talk | contribs)
Link multiplication algorithm in intro and remove paragraph on [[Schönhage-Strassen algorithm]], which is discussed in that article and largely irrelevant here
Next diff →
Current revision
Toom-Cook, sometimes known as Toom-3, is a multiplication algorithm, a method of multiplying two large integers.
Ordinarily, long integer multiplication will take Θ(n2) operations, where n is the number of digits in the given integers. However, modern arbitrary-precision arithmetic implementations require faster multiplication algorithms to be of practical use. Toom-Cook can be implemented to run in Θ(n1+e), for any e > 0. As e diminishes, the algorithmic complexity (not time-complexity) increases, and the law of diminishing returns will render Toom-Cook algorithms where e nears 0 rather impractical.
Andrei Toom first described this algorithm in 1963, while Stephen Cook improved the algorithm and published it in his PhD thesis in 1966. [1] (thesis)
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 used interchangably, Toom-3 is only a single instance of the Toom-Cook algorithm, where k = 3.
Toom-Cook is slower than long multiplication with small numbers, because a lot of complexity (eg. recursive calls and advanced digit-handling) is involved. Bignum software library writers often add a threshold mechanism to decide which algorithms to use based on input size. Long multiplication may be used for small numbers, then Toom-Cook multiplication for larger ones.
The well-known Karatsuba multiplication 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 Θ(nlog2 (3)), which is about Θ(n1.585). Even this can reduce computation time substantially over conventional quadratic-time multiplication, when n is large. Toom-3 reduces 9 multiplications to 5, and runs in Θ(nlog2 (7) / log2 (3)), about Θ(n1.465). In general, Toom-N multiplication runs in Θ(nlog2 (2N-1) / log2 (N)).
