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 effectuera les calculs. C'est un raffinement de l'algorithme de Karatsuba.

Multiplier deux nombres revient à multiplier deux polynômes

$A(x) = \begin{pmatrix} x^2 & x^1 & x^0 \end{pmatrix} \begin{pmatrix} a_2 & a_1 & a_0 \end{pmatrix}^T$

et

$B(x) = \begin{pmatrix} x^2 & x^1 & x^0 \end{pmatrix} \begin{pmatrix} b_2 & b_1 & b_0 \end{pmatrix}^T$

ce qui donne un troisième polynôme

$P(x) = A(x)B(x) = \begin{pmatrix} x^4 & x^3 & x^2 & x^1 & x^0 \end{pmatrix} \begin{pmatrix} p_4 & p_3 & p_2 & p_1 & p_0 \end{pmatrix}^T$

En l'évaluant en cinq points

$\begin{pmatrix} P(\infty) \\ P( 2) \\ P(-1) \\ P( 1) \\ P( 0) \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \end{pmatrix}$

ses coefficients peuvent être déterminés

$\begin{pmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}^{-1} \begin{pmatrix} P(\infty) \\ P( 2) \\ P(-1) \\ P( 1) \\ P( 0) \end{pmatrix}$

Ce calcul nécessite cinq multiplications trois fois plus simples et quelques additions

$\begin{align}\begin{pmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \end{pmatrix}&=\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}^{-1} \begin{pmatrix} A(\infty)B(\infty) \\ A( 2)B( 2) \\ A(-1)B(-1) \\ A( 1)B( 1) \\ A( 0)B( 0) \end{pmatrix}\\&=\begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}^{-1} \begin{pmatrix} a_2b_2 \\ (4a_2+2a_1+a_0)(4b_2+2b_1+b_0) \\ (a_2-a_1+a_0)(b_2-b_1+b_0) \\ (a_2+a_1+a_0)(b_2+b_1+b_0) \\ a_0b_0 \end{pmatrix}~.\end{align}$

La complexité est donc

$O(n^{\log _3 (5)}) \simeq O(n^{1.465})$.

Références

• (ru) Andrei Toom, О сложности схемы из функциональных элементов, реализующей умножение целых чисел, Доклады Академии Наук СССР, T. 150, N°3, 1963, p. 496-498, (en) The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers, p. 714-716
• (en) Donald Knuth, The Art of Computer Programming, Vol. 2, 3^e éd. , Addison-Wesley, 1997
• (en) Richard Crandall (en), Carl Pomerance, Prime Numbers - A Computational Perspective, 2^e éd. , Springer, 2005
• (en) Toom 3-Way Multiplication, documentation de GMP