Algorithme Toom-Cook

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Cyrillic letter Dzhe.svg Cette page contient des caractères cyrilliques. En cas de problème, consultez Aide:Unicode ou testez votre navigateur.

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[modifier | modifier le code]