Toom–Cook multiplication

Toom–Cook multiplication

Toom–Cook, sometimes known as Toom-3, named after Andrei Toom and Stephen Cook, is a multiplication algorithm, a method of multiplying two 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 Θ(nlog(5)/log(3)), about Θ(n1.465). In general, Toom-"k" runs in Θ("c"("k") "ne"), where "e" = log(2"k"-1) / log("k"), "ne" 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 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)), which is about Θ("n"1.585). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ("n"2).

Although the exponent "e" can be set arbitrarily close to 1 by increasing "k", the function "c" unfortunately grows very rapidly. [Knuth, p. 296] [Crandall & Pomerance, p. 474] The growth rate for mixed-level Toom-Cook schemes was still an open research problem in 2005. [Crandall & Pomerance, p. 536] An implementation described by Donald Knuth achieves the time complexity Θ("n" 2√(2 log "n") log "n"). [Knuth, p. 302]

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.

Andrei Toom first described this algorithm in 1963, while Stephen Cook improved the algorithm and published it in his PhD thesis in 1966. [http://www.cs.toronto.edu/~sacook/ (thesis)]

Details

This section discusses exactly how to perform Toom-"k" for any given value of "k", and is a simplification of a description of Toom–Cook polynomial multiplication described by Marco Bodrato. [Marco Bodrato. Towards Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In "WAIFI'07 proceedings", volume 4547 of LNCS, pages 116-133. June 21-22, 2007. [http://bodrato.it/papers/#WAIFI2007 author website] ] The algorithm has five main steps: "Splitting", "Evaluation", "Pointwise multiplication", "Interpolation", and "Recomposition".

In a typical large integer implementation, each integer is represented as a sequence of digits in positional notation, with the base or radix set to some (typically large) value "b"; for this example we use "b" = 10000, so that each digit corresponds to a group of four decimal digits (in a computer implementation, "b" would typically be a power of 2 instead). Say the two integers being multiplied are:

As shown, these can also be negative. For large enough numbers, this is the most expensive step, the only step that is not linear in the sizes of "m" and "n".

Interpolation

This is the most complex step, the reverse of the evaluation step: given our "d" points on "r", we need to determine the coefficients of "r". In other words, we want to solve this matrix equation for the vector on the right-hand side:

: egin{align}left(egin{matrix}r(0) \ r(1) \ r(-1) \ r(-2) \ r(infty)end{matrix} ight) & {} =left(egin{matrix}0^0 & 0^1 & 0^2 & 0^3 & 0^4 \1^0 & 1^1 & 1^2 & 1^3 & 1^4 \(-1)^0 & (-1)^1 & (-1)^2 & (-1)^3 & (-1)^4 \(-2)^0 & (-2)^1 & (-2)^2 & (-2)^3 & (-2)^4 \0 & 0 & 0 & 0 & 1end{matrix} ight)left(egin{matrix}r_0 \ r_1 \ r_2 \ r_3 \ r_4end{matrix} ight) \ & {} =left(egin{matrix}1 & 0 & 0 & 0 & 0 \1 & 1 & 1 & 1 & 1 \1 & -1 & 1 & -1 & 1 \1 & -2 & 4 & -8 & 16 \0 & 0 & 0 & 0 & 1end{matrix} ight)left(egin{matrix}r_0 \ r_1 \ r_2 \ r_3 \ r_4end{matrix} ight)end{align}

This matrix is constructed the same way as the one in the evaluation step, except that it's "d"×"d". We could solve this equation with a technique like Gaussian elimination, but this is too expensive. Instead, we use the fact that, provided the evaluation points were chosen suitably, this matrix is invertible, and so:

: egin{align}left(egin{matrix}r_0 \ r_1 \ r_2 \ r_3 \ r_4end{matrix} ight) & {} =left(egin{matrix}1 & 0 & 0 & 0 & 0 \1 & 1 & 1 & 1 & 1 \1 & -1 & 1 & -1 & 1 \1 & -2 & 4 & -8 & 16 \0 & 0 & 0 & 0 & 1end{matrix} ight)^{-1}left(egin{matrix}r(0) \ r(1) \ r(-1) \ r(-2) \ r(infty)end{matrix} ight) \& {} =left(egin{matrix} 1 & 0 & 0 & 0 & 0 \ 1/2 & 1/3 & -1 & 1/6 & -2 \ -1 & 1/2 & 1/2 & 0 & -1 \-1/2 & 1/6 & 1/2 & -1/6 & 2 \ 0 & 0 & 0 & 0 & 1end{matrix} ight)left(egin{matrix}r(0) \ r(1) \ r(-1) \ r(-2) \ r(infty)end{matrix} ight)end{align}

All that remains is to compute this matrix-vector product. Although the matrix contains fractions, the resulting coefficients will be integers — so this can all be done with integer arithmetic, just additions, subtractions, and multiplication/division by small constants. A difficult design challenge in Toom–Cook is to find an efficient sequence of operations to compute this product; one sequence given by Bodrato for Toom-3 is the following, executed here over the running example:

We now know our product polynomial "r":

: egin{align}r(x) & {} = 3084841486175176 \ & {} quad + 6740415721237444x \ & {} quad + 3422416581971852x^2 \ & {} quad + 13128433387466x^3 \ & {} quad + 12193131840x^4end{align}

If we were using different "k""m", "k""n", or evaluation points, the matrix and so our interpolation strategy would change; but it does not depend on the inputs and so can be hard-coded for any given set of parameters.

Recomposition

Finally, we evaluate r(B) to obtain our final answer. This is straightforward since B is a power of "b" and so the multiplications by powers of B are all shifts by a whole number of digits in base "b":

And this is in fact the product of 1234567890123456789012 and 987654321987654321098.

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

Toom-1 ("k""m" = "k""n" = 1) requires 1 evaluation point, here chosen to be 0. It degenerates to long multiplication, with an interpolation matrix of the identity matrix:

: left(egin{matrix}1end{matrix} ight)^{-1} = left(egin{matrix}1end{matrix} ight)

Toom-1.5

Toom-1.5 ("k""m" = 2, "k""n" = 1) requires 2 evaluation points, here chosen to be 0 and ∞. Its interpolation matrix is then the identity matrix:

: left(egin{matrix}1 & 0 \ 0 & 1end{matrix} ight)^{-1} =left(egin{matrix}1 & 0 \ 0 & 1end{matrix} ight)

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:

: left(egin{matrix}1 & 0 & 0 \1 & 1 & 1 \0 & 0 & 1end{matrix} ight)^{-1} =left(egin{matrix}1 & 0 & 0 \-1 & 1 & -1 \0 & 0 & 1end{matrix} ight)

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:

: left(egin{matrix}1 & 0 & 0 & 0 \1 & 1 & 1 & 1 \1 & -1 & 1 & -1 \0 & 0 & 0 & 1end{matrix} ight)^{-1} =left(egin{matrix}1 & 0 & 0 & 0 \0 & 1/2 & -1/2 & -1 \-1 & 1/2 & 1/2 & 0 \0 & 0 & 0 & 1end{matrix} ight)

Notes

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.433.
* M. Bodrato. " [http://bodrato.it/toom-cook/ Toward Optimal Toom-Cook Multiplication...] ". In WAIFI'07, Springer, 2007.

External links

* [http://gmplib.org/manual/Toom-3_002dWay-Multiplication.html Toom-Cook 3-Way Multiplication from GMP Documentations]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Toom-Cook — Algorithme Toom Cook Toom Cook, aussi appelé Toom 3, est une technique de multiplication utilisée pour multiplier deux grands nombres. Ces grands nombres sont découpés en plus petits nombres sur lesquels on effectuera les calculs. Multiplier deux …   Wikipédia en Français

  • Algorithme Toom-Cook — L algorithme de Toom Cook, aussi appelé Toom 3, est un algorithme de multiplication dû à Andrei Toom (en) et Stephen Cook, utilisé pour multiplier deux grands nombres. Ces grands nombres sont découpés en plus petits nombres sur lesquels on… …   Wikipédia en Français

  • Algorithme de Toom-Cook — Algorithme Toom Cook Toom Cook, aussi appelé Toom 3, est une technique de multiplication utilisée pour multiplier deux grands nombres. Ces grands nombres sont découpés en plus petits nombres sur lesquels on effectuera les calculs. Multiplier deux …   Wikipédia en Français

  • Toom — may refer to:* Andrei Toom (born 1942), Russian mathematician * Toom–Cook multiplication or Toom 3, a mathematical algorithm * Toom (Netherlands), a hamlet * Toom (supermarket), a chain of supermarkets in Germany * Toum, a garlic sauce from… …   Wikipedia

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Multiplication — Multiply redirects here. For other uses, see Multiplication (disambiguation). For methods of computing products, including those of very large numbers, see Multiplication algorithm. Four bags of three marbles gives twelve marbles. There are also… …   Wikipedia

  • Multiplication de matrices — Produit matriciel Le produit matriciel désigne le produit de matrices, initialement appelé la « composition des tableaux »[1]. Cet article montre comment multiplier les matrices. Sommaire 1 Produit matriciel ordinaire 1.1 Exemple …   Wikipédia en Français

  • Multiplication des matrices — Produit matriciel Le produit matriciel désigne le produit de matrices, initialement appelé la « composition des tableaux »[1]. Cet article montre comment multiplier les matrices. Sommaire 1 Produit matriciel ordinaire 1.1 Exemple …   Wikipédia en Français

  • Multiplication matricielle — Produit matriciel Le produit matriciel désigne le produit de matrices, initialement appelé la « composition des tableaux »[1]. Cet article montre comment multiplier les matrices. Sommaire 1 Produit matriciel ordinaire 1.1 Exemple …   Wikipédia en Français

  • Ancient Egyptian multiplication — In mathematics, ancient Egyptian multiplication (also known as Egyptian multiplication, Ethiopian multiplication, Russian multiplication, or peasant multiplication), one of two multiplication methods used by scribes, was a systematic method for… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”