Algorithme Toom-Cook

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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 nombres revient à multiplier deux polynômes

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

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

ce qui donne un troisième polynôme

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

En l'évaluant en cinq points

$\begin{bmatrix} P(\infty) \\ P( 2) \\ P(-1) \\ P( 1) \\ P( 0) \end{bmatrix} = \begin{bmatrix} 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{bmatrix} * \begin{bmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \end{bmatrix}$

ses coefficients peuvent être déterminés

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

$\begin{bmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \end{bmatrix} = \begin{bmatrix} 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{bmatrix}^{-1} * \begin{bmatrix} A(\infty)*B(\infty) \\ A( 2)*B( 2) \\ A(-1)*B(-1) \\ A( 1)*B( 1) \\ A( 0)*B( 0) \end{bmatrix} = \begin{bmatrix} 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{bmatrix}^{-1} * \begin{bmatrix} a_2*b_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_0*b_0 \end{bmatrix}$

La complexité est donc

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

[modifier] Voir aussi

Algorithme de Karatsuba

[modifier] Références

Тоом Андрей Леонович, О сложности схемы из функциональных элементов, реализующей умножение целых чисел, Доклады Академии Наук СССР, T.150, N°3, pagg.496-498 [1]
D. Knuth. The Art of Computer Programming, Volume 2. Troisième édition, Addison-Wesley, 1997.
R. Crandall & C. Pomerance. Prime Numbers - A Computational Perspective. Seconde édition, Springer, 2005.