Algorithme Toom-Cook

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

v · Naïf  · Strassen  · Coppersmith-Winograd
Produit d'entiers Naïf  · Karatsuba  · Toom-Cook  · Schönhage-Strassen  · Fürer

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme Toom-Cook de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • 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-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 De Karatsuba — L algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres avec une complexité en au lieu de O(n2) pour la méthode naïve. Note : . Sommaire 1 Énoncé …   Wikipédia en Français

  • Algorithme de karatsuba — L algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres avec une complexité en au lieu de O(n2) pour la méthode naïve. Note : . Sommaire 1 Énoncé …   Wikipédia en Français

  • Algorithme De Multiplication — Les techniques de multiplication permettent de calculer le résultat d une multiplication. Graphiquement, il s agit de transformer un rectangle multiplicateur × multiplicande en une ligne, en conservant le nombre d éléments. Exemples: Sommaire 1… …   Wikipédia en Français

  • Algorithme de multiplication — Les techniques de multiplication permettent de calculer le résultat d une multiplication. Graphiquement, il s agit de transformer un rectangle multiplicateur × multiplicande en une ligne, en conservant le nombre d éléments. Exemples: Sommaire 1… …   Wikipédia en Français

  • Algorithme De Strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme de strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme De Coppersmith-Winograd — L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en fait l algorithme le plus efficace… …   Wikipédia en Français

  • Algorithme de Coppersmith–Winograd — Algorithme de Coppersmith Winograd L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en… …   Wikipédia en Français

Share the article and excerpts

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