Algorithme Toom-Cook

L'algorithme Toom-Cook, parfois appelé Toom-3, est un algorithme de multiplication d'entiers dû à Andrei Toom (en) et Stephen Cook, utilisé pour multiplier deux grands nombres.

Ces grands nombres sont découpés en k morceaux de longueur l sur lesquels les multiplications sont faites récursivement à la manière d’un diviser pour régner. C’est une généralisation de l’algorithme de Karatsuba qui coïncide au cas où k = 2.

Par abus de langage, Toom-3 et Toom-Cook sont souvent utilisés de manière interchangeable. Or, Toom-3 est le cas où k = 3, où il y est fait 5 multiplications, ce qui, par application du master theorem donne une complexité en Θ(n^{log(5)/log(3)}) ≈ Θ(n^1.465).

L'algorithme de Toom-Cook peut se décomposer en cinq phases :

1. Le découpage
2. L'évaluation
3. Les multiplications point par point
4. L’interpolation
5. La reconstruction

Dans la suite, nous expliquerons le déroulement de l'algorithme de Toom-k pour n’importe quelle valeur de k. C'est une simplification de la description de l'algorithme donnée par Marco Bodrato^[1].

Étant donné deux nombres m et n en base b, on commence par choisir une nouvelle base B = bⁱ afin que le nombre de chiffres en base B de m et n soit au plus k (par exemple 3 pour Toom-3). Un choix usuel est :

i = max { ⌊ ⌊ log b ⁡ m ⌋ k ⌋ , ⌊ ⌊ log b ⁡ n ⌋ k ⌋ } + 1. {\displaystyle i=\max \left\{\left\lfloor {\frac {\lfloor \log _{b}m\rfloor }{k}}\right\rfloor ,\left\lfloor {\frac {\lfloor \log _{b}n\rfloor }{k}}\right\rfloor \right\}+1.}

Ainsi on peut définir les polynômes dont ces chiffres correspondent à leurs coefficient, c'est-à-dire :

P ( x ) = ∑ i = 0 k − 1 m i x i , {\displaystyle P(x)=\sum _{i=0}^{k-1}m_{i}x^{i},}

Q ( x ) = ∑ i = 0 k − 1 n i x i . {\displaystyle Q(x)=\sum _{i=0}^{k-1}n_{i}x^{i}.}

On remarque que P(B) = m et Q(B) = n, ainsi si on effectue le produit des polynômes pour avoir R(x) = P(x) · Q(x) alors l’évaluation de ce produit en B coïncide avec le produit recherché: R(B) = m·n.

Maintenant que nous avons défini les polynômes P et Q, calculer leur produit se fait par la méthode d’évaluation-interpolation. Pour cela on va évaluer le résultat du polynôme produit R en plusieurs points que l'on utilisera ensuite afin de l'interpoler et donc d'en trouver les coefficients.

Comme P et Q sont de degrés (k − 1), alors leur produit est de degré (2 · k − 2). Par exemple dans le cas de Toom-3, le produit de P et Q est de degré 4, il nous faut donc 5 points pour en calculer l’interpolation. Le choix des points importe peu, il suffit de garantir que l'interpolation est possible (ce qui sera rappelé dans la section Interpolation). Par exemple pour Toom-3, les points traditionnellement choisis sont 0 , 1 , − 1 , 2 , ∞ {\displaystyle 0,1,-1,2,\infty } .

Ainsi ces évaluations sur P nous donne :

P ( 0 ) = m 0 , {\displaystyle P(0)=m_{0},}

P ( 1 ) = m 2 + m 1 + m 0 , {\displaystyle P(1)=m_{2}+m_{1}+m_{0},}

P ( − 1 ) = m 2 − m 1 + m 0 , {\displaystyle P(-1)=m_{2}-m_{1}+m_{0},}

P ( 2 ) = 4 ⋅ m 2 + 2 ⋅ m 1 + m 0 , {\displaystyle P(2)=4\cdot m_{2}+2\cdot m_{1}+m_{0},}

P ( ∞ ) = m 2 . {\displaystyle P(\infty )=m_{2}.}

On procède de manière similaire pour Q.

Une fois qu'on a nos différentes évaluations, il est alors possible de calculer R ( a i ) = P ( a i ) ⋅ Q ( a i ) {\displaystyle R(a_{i})=P(a_{i})\cdot Q(a_{i})} pour chaque point d'évaluation a_i. Dans le cas de Toom-3, on rappelle que ces points sont ( a i ) 0 ≤ i ≤ 4 = ( 0 , 1 , − 1 , 2 , ∞ ) {\displaystyle (a_{i})_{0\leq i\leq 4}=(0,1,-1,2,\infty )} . Comme on multiplie deux nombres de taille l, on peut réappliquer récursivement notre algorithme pour calculer ces sous-produits.

Une fois qu'on a nos valeurs r_i pour i compris entre 0 et 2k - 2, on peut alors réécrire les relations entre P, Q et R de manière matricielle. Pour plus de clarté on explicitera le cas k = 3:

( R ( 0 ) R ( 1 ) R ( − 1 ) R ( 2 ) R ( ∞ ) ) = ( 1 0 0 0 0 1 1 1 1 1 1 − 1 1 − 1 1 1 2 4 8 16 0 0 0 0 1 ) ( r 0 r 1 r 2 r 3 r 4 ) . {\displaystyle {\begin{pmatrix}R(0)\\R(1)\\R(-1)\\R(2)\\R(\infty )\end{pmatrix}}={\begin{pmatrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&2&4&8&16\\0&0&0&0&1\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{pmatrix}}.}

Cette matrice de passage correspondant à une matrice de Vandermonde, il suffisait alors de prendre des points deux à deux distincts pour qu'elle soit inversible. Ce qui se traduit alors par :

( r 0 r 1 r 2 r 3 r 4 ) = ( 1 0 0 0 0 1 1 1 1 1 1 − 1 1 − 1 1 1 2 4 8 16 0 0 0 0 1 ) − 1 ( R ( 0 ) R ( 1 ) R ( − 1 ) R ( 2 ) R ( ∞ ) ) . {\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{pmatrix}}={\begin{pmatrix}1&0&0&0&0\\1&1&1&1&1\\1&-1&1&-1&1\\1&2&4&8&16\\0&0&0&0&1\end{pmatrix}}^{-1}{\begin{pmatrix}R(0)\\R(1)\\R(-1)\\R(2)\\R(\infty )\end{pmatrix}}.}

En calculant cet inverse, on obtient alors :

( r 0 r 1 r 2 r 3 r 4 ) = ( 1 0 0 0 0 − 1 2 1 − 1 3 − 1 6 2 − 1 1 2 1 2 0 − 1 1 2 − 1 2 − 1 6 1 6 − 2 0 0 0 0 1 ) ( R ( 0 ) R ( 1 ) R ( − 1 ) R ( 2 ) R ( ∞ ) ) . ( 1 ) {\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{pmatrix}}={\begin{pmatrix}1&0&0&0&0\\-{\frac {1}{2}}&1&-{\frac {1}{3}}&-{\frac {1}{6}}&2\\-1&{\frac {1}{2}}&{\frac {1}{2}}&0&-1\\{\frac {1}{2}}&-{\frac {1}{2}}&-{\frac {1}{6}}&{\frac {1}{6}}&-2\\0&0&0&0&1\end{pmatrix}}{\begin{pmatrix}R(0)\\R(1)\\R(-1)\\R(2)\\R(\infty )\end{pmatrix}}.\qquad (1)}

Finalement, il ne nous reste plus qu'à évaluer la valeur de R ( B ) = ∑ i = 0 2 k − 2 r i B i {\displaystyle R(B)=\sum _{i=0}^{2k-2}r_{i}B^{i}} afin d'obtenir le résultat du produit. Comme B est une puissance de notre base de travail b, cela se fait simplement à l'aide d'additions avec retenue.

Pour illustrer l’algorithme, on observera le déroulé de Toom-3 sur le produit de deux nombres à 60 décimales :

m = 834544525917432883830350648457459637471433260128185184920699

et

n = 198998441043619592623230746397999173308818723846794281749622

Le découpage : on commence par les découper en trois morceaux de 20 chiffres (c'est-à-dire qu'en base 10, on a pris i = 20) :

m₂ = 83454452591743288383

m₁ = 03506484574596374714

m₀ = 33260128185184920699

et

n₂ = 19899844104361959262

n₁ = 32307463979991733088

n₀ = 18723846794281749622.

L’évaluation : on utilise ensuite ces coefficients pour calculer les valeurs de P ( 0 ) , P ( 1 ) , P ( − 1 ) , P ( 2 ) , P ( ∞ ) , Q ( 0 ) , Q ( 1 ) , Q ( − 1 ) , Q ( 2 ) {\displaystyle P(0),P(1),P(-1),P(2),P(\infty ),Q(0),Q(1),Q(-1),Q(2)} et Q ( ∞ ) {\displaystyle Q(\infty )} .

P(0) = 33260128185184920699

P(1) = 83454452591743288383 + 03506484574596374714 + 33260128185184920699

= 120221065351524583796

P(-1) = 83454452591743288383 - 03506484574596374714 + 33260128185184920699

= 113208096202331834368

P(2) = 4 × 83454452591743288383 + 2 × 03506484574596374714 + 33260128185184920699

= 374090907701350823659

P(∞) = 83454452591743288383

Q(0) = 18723846794281749622

Q(1) = 19899844104361959262 + 32307463979991733088 + 18723846794281749622

= 70931154878635441972

Q(-1) = 19899844104361959262 - 32307463979991733088 + 18723846794281749622

= 6316226918651975796

Q(2) = 4 × 19899844104361959262 + 2 × 32307463979991733088 + 18723846794281749622

= 162938151171713052846

Q(∞) = 19899844104361959262.

Remarque : À cette étape, il peut arriver que certaines évaluations (comme celle de P(-1)) soient négatives. Cela est normal et n'impacte en rien la correction ni le déroulement de l'algorithme.

Les multiplications point à point : une fois ces valeurs calculées, il suffit de les multiplier entre elles pour avoir les valeurs de R ( 0 ) , R ( 1 ) , R ( − 1 ) , R ( 2 ) {\displaystyle R(0),R(1),R(-1),R(2)} et R ( ∞ ) {\displaystyle R(\infty )}  :

R(0) = 33260128185184920699 × 18723846794281749622 = 622757544497574744270962786413043225778

R(1) = 120221065351524583796 × 70931154878635441972 = 8527419006123543277501478811621809485712

R(-1) = 113208096202331834368 × 6316226918651975796 = 715048024642510845238638992592216956928

R(2) = 374090907701350823659 × 162938151171713052846 = 60953680871006055212654676877543494083514

R(∞) = 83454452591743288383 × 19899844104361959262 = 1660730596390557308480735631788563853346.

L'interpolation : en utilisant la matrice d'interpolation de l'équation (1) on retrouve les coefficients de r : ( r 0 r 1 r 2 r 3 r 4 ) = ( 1 0 0 0 0 − 1 2 1 − 1 3 − 1 6 2 − 1 1 2 1 2 0 − 1 1 2 − 1 2 − 1 6 1 6 − 2 0 0 0 0 1 ) ( 622757544497574744270962786413043225778 8527419006123543277501478811621809485712 715048024642510845238638992592216956928 60953680871006055212654676877543494083514 1660730596390557308480735631788563853346 ) = ( 622757544497574744270962786413043225778 1140205273274024371805476204871094246620 2337745374494895008618360483905406142196 2765980217466491844325943704643702017772 1660730596390557308480735631788563853346 ) {\displaystyle {\begin{pmatrix}r_{0}\\r_{1}\\r_{2}\\r_{3}\\r_{4}\end{pmatrix}}={\begin{pmatrix}1&0&0&0&0\\-{\frac {1}{2}}&1&-{\frac {1}{3}}&-{\frac {1}{6}}&2\\-1&{\frac {1}{2}}&{\frac {1}{2}}&0&-1\\{\frac {1}{2}}&-{\frac {1}{2}}&-{\frac {1}{6}}&{\frac {1}{6}}&-2\\0&0&0&0&1\end{pmatrix}}{\begin{pmatrix}622757544497574744270962786413043225778\\8527419006123543277501478811621809485712\\715048024642510845238638992592216956928\\60953680871006055212654676877543494083514\\1660730596390557308480735631788563853346\end{pmatrix}}={\begin{pmatrix}622757544497574744270962786413043225778\\1140205273274024371805476204871094246620\\2337745374494895008618360483905406142196\\2765980217466491844325943704643702017772\\1660730596390557308480735631788563853346\end{pmatrix}}}

La reconstruction : afin de retrouver le résultat final, il ne nous reste plus qu'à calculer la somme r = ∑ i = 0 4 r i ( 10 20 ) i {\displaystyle r=\sum _{i=0}^{4}r_{i}(10^{20})^{i}} .

r = 1660730596390557308480735631788563853346 × 10⁸⁰ + 2765980217466491844325943704643702017772 × 10⁶⁰ + 2337745374494895008618360483905406142196 × 10⁴⁰ + 1140205273274024371805476204871094246620 × 10²⁰ + 622757544497574744270962786413043225778.

Ce qui donne bien :

r = 166073059639055730850839543396322877178949321158388650967858297625366381463859141170378031606999406270962786413043225778,

qui est le résultat du produit de m par n.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Toom–Cook multiplication » (voir la liste des auteurs).

• (ru) Andrei Toom, « О сложности схемы из функциональных элементов, реализующей умножение целых чисел »^{(Archive.org • Wikiwix • Google • Que faire ?)}, Доклады Академии Наук СССР, T. 150, n^o 3, 1963, p. 496-498, (en) « The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers »^{(Archive.org • Wikiwix • Google • Que faire ?)}, p. 714-716
• (en) Donald Knuth, The Art of Computer Programming, Vol. 2, 3^e éd. , Addison-Wesley, 1997
• (en) Richard Crandall, Carl Pomerance, Prime Numbers - A Computational Perspective, 2^e éd. , Springer, 2005
• (en) Toom 3-Way Multiplication, documentation de GMP
• (en) Marco Bodrato, « Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0 », WAIFI,‎ 2007 (DOI 10.1007/978-3-540-73074-3_10)

• Arithmétique et théorie des nombres
• Portail de l'informatique théorique