Introduction
La multiplication de Toom-Cook, parfois appelée algorithme de Toom, est une famille d'algorithmes de multiplication rapide destinée aux très grands nombres entiers. Elle constitue une évolution directe de la multiplication de Karatsuba en appliquant le même principe général de «diviser pour régner» (Divide and Conquer), mais en découpant les nombres en trois parties ou plus plutôt qu'en seulement deux. Cette approche permet de réduire encore davantage le nombre de multiplications nécessaires, ce qui améliore les performances lorsque les nombres manipulés deviennent très grands.
L'algorithme a été proposé indépendamment par le mathématicien russe Andreï Toom en 1963, puis généralisé quelques années plus tard par Stephen Cook. Depuis, il est devenu une référence dans les bibliothèques de calcul sur grands entiers. De nombreux logiciels de calcul scientifique, de cryptographie ou de calcul symbolique utilisent automatiquement la multiplication de Toom-Cook lorsque les nombres dépassent une certaine taille. Pour des nombres plus petits, les implémentations reviennent généralement à la multiplication classique ou à la multiplication de Karatsuba, ces dernières présentant un coût fixe inférieur.
Principe
L'idée fondamentale consiste à découper les deux nombres en plusieurs blocs, puis à considérer ces blocs comme les coefficients d'un polynôme.
Par exemple, dans la variante Toom-3, chaque nombre est découpé en trois parties :
|
X = a2·B2 + a1·B + a0 Y = b2·B2 + b1·B + b0 |
où :
- B représente une puissance de la base numérique utilisée (généralement une puissance de 2 ou de 10).
- a0, a1 et a2 sont les différentes parties du premier nombre.
- b0, b1 et b2 représentent celles du second nombre.
Plutôt que de multiplier directement chacune des parties entre elles, l'algorithme construit deux polynômes, les évalue en plusieurs points particuliers, multiplie les résultats obtenus puis reconstruit le produit final grâce à une opération d'interpolation.
Cette approche permet d'effectuer moins de multiplications que la méthode classique, au prix d'un nombre plus important d'additions, de soustractions et de divisions par de petites constantes.
Les principales étapes
L'algorithme de Toom-Cook peut être résumé en cinq grandes étapes :
- Découper chacun des deux nombres en plusieurs blocs.
- Construire les deux polynômes représentant ces blocs.
- Évaluer ces polynômes en plusieurs valeurs particulières.
- Multiplier les résultats obtenus pour chacun des points.
- Reconstituer le polynôme final par interpolation avant de reconstruire le produit.
Cette méthode peut sembler plus complexe que la multiplication classique, mais elle réduit considérablement le nombre de multiplications coûteuses.
Exemple simplifié (Toom-3)
Supposons les deux nombres suivants :
|
123456 789012 |
Ils sont découpés en trois groupes de deux chiffres :
|
123456 ↓ 12 | 34 | 56 789012 ↓ 78 | 90 | 12 |
Les deux nombres deviennent alors deux polynômes :
|
P(x)=12x2+34x+56 Q(x)=78x2+90x+12 |
Ces polynômes sont ensuite évalués pour différentes valeurs de x, par exemple :
|
x = 0 x = 1 x = -1 x = 2 x = ∞ |
Les valeurs obtenues sont multipliées entre elles.
Enfin, une phase d'interpolation permet de retrouver les coefficients du polynôme représentant le produit final, lequel est ensuite converti de nouveau en un entier.
Algorithme simplifié
Voici une représentation simplifiée du fonctionnement général :
|
MODULE ToomCook(x,y) SI les nombres sont petits ALORS RETOURNER x × y FIN SI Découper x en plusieurs blocs Découper y en plusieurs blocs Construire deux polynômes Évaluer les polynômes sur plusieurs points Multiplier chaque résultat Interpoler les résultats Reconstruire le produit RETOURNER le résultat |
En pratique, les étapes d'évaluation et d'interpolation représentent la plus grande partie de la complexité de l'algorithme.
Les variantes
La multiplication de Toom-Cook n'est pas un algorithme unique, mais une famille complète d'algorithmes.
Les variantes les plus connues sont :
| Variante | Découpage |
|---|---|
| Toom-2 | 2 parties (équivalent à Karatsuba) |
| Toom-3 | 3 parties |
| Toom-4 | 4 parties |
| Toom-6 | 6 parties |
| Toom-8 | 8 parties |
Plus le nombre de parties augmente, plus le nombre de multiplications diminue. En contrepartie, les calculs d'interpolation deviennent de plus en plus complexes.
Complexité
La multiplication classique possède une complexité de :
| O(n2) |
La multiplication de Karatsuba possède une complexité de :
| O(n^1.585) |
La variante Toom-3 atteint environ :
| O(n^1.465) |
Les variantes comportant davantage de blocs permettent encore de réduire légèrement cet exposant, mais au prix d'une complexité algorithmique beaucoup plus importante.
Avantages
La multiplication de Toom-Cook présente de nombreux avantages :
- elle est plus rapide que la multiplication de Karatsuba pour les très grands nombres ;
- elle réduit davantage le nombre de multiplications coûteuses ;
- elle s'adapte facilement à différentes tailles de nombres grâce à ses nombreuses variantes ;
- elle est largement utilisée dans les bibliothèques de calcul sur grands entiers ;
- elle constitue une étape intermédiaire entre Karatsuba et les algorithmes utilisant la transformée de Fourier.
Inconvénients
Cette méthode présente également certaines limites :
- elle est beaucoup plus difficile à programmer ;
- les calculs d'interpolation sont relativement complexes ;
- elle nécessite davantage de mémoire temporaire ;
- elle est souvent moins performante que Karatsuba pour les nombres de petite taille ;
- les implémentations doivent choisir dynamiquement à partir de quelle taille de nombres il devient avantageux de l'utiliser.
Pour cette raison, les bibliothèques modernes changent automatiquement d'algorithme selon la taille des opérandes.
Applications
La multiplication de Toom-Cook est utilisée dans de nombreux domaines nécessitant des calculs sur des très grands entiers :
- les bibliothèques BigInteger ;
- les logiciels de calcul symbolique ;
- les logiciels de calcul scientifique ;
- les systèmes de calcul formel ;
- les bibliothèques de cryptographie (RSA, Diffie-Hellman, ECC) ;
- les compilateurs manipulant des constantes de très grande taille ;
- les logiciels d'arithmétique multiprécision ;
- les bibliothèques spécialisées comme GNU Multiple Precision (GMP), MPIR, OpenSSL, Java BigInteger ou encore les implémentations des grands entiers de Python.
Lorsque les nombres deviennent encore plus gigantesques (plusieurs dizaines ou centaines de milliers de chiffres), les bibliothèques modernes abandonnent généralement Toom-Cook au profit d'algorithmes encore plus performants, tels que Schönhage-Strassen, Fürer ou les méthodes fondées sur la Transformée de Fourier Rapide (FFT). Néanmoins, la multiplication de Toom-Cook demeure aujourd'hui l'un des algorithmes les plus importants dans le domaine du calcul multiprécision et constitue une étape essentielle dans l'évolution historique des techniques de multiplication rapide.