Introduction
La multiplication de Karatsuba est un algorithme de multiplication rapide inventé en 1960 par le mathématicien soviétique Anatoli Karatsuba. Cette méthode a marqué une étape importante dans l'histoire de l'informatique théorique, puisqu'elle fut le premier algorithme démontrant qu'il était possible de multiplier deux grands nombres plus rapidement que la méthode classique enseignée à l'école. Avant cette découverte, on croyait généralement que la multiplication nécessitait obligatoirement un nombre d'opérations proportionnel au carré de la taille des nombres à multiplier. Karatsuba démontra qu'il était possible de réduire ce coût en utilisant une approche fondée sur le principe «diviser pour régner» (Divide and Conquer).
L'algorithme de Karatsuba est particulièrement efficace pour la multiplication de très grands entiers, comme ceux utilisés en cryptographie, dans les bibliothèques de calcul scientifique ou dans les logiciels manipulant des nombres comportant plusieurs centaines, voire plusieurs milliers de chiffres. Pour les petits nombres, les compilateurs et les processeurs utilisent généralement la multiplication classique, celle-ci étant plus simple et présentant un coût fixe plus faible. En revanche, lorsque les nombres deviennent suffisamment grands, la multiplication de Karatsuba devient plus performante.
Principe
Le principe consiste à découper chacun des deux nombres en deux parties, puis à effectuer seulement trois multiplications au lieu des quatre normalement nécessaires avec la méthode classique.
Supposons deux nombres :
|
X = a × 10m + b Y = c × 10m + d |
où :
- a représente la moitié supérieure du premier nombre.
- b représente la moitié inférieure du premier nombre.
- c représente la moitié supérieure du second nombre.
- d représente la moitié inférieure du second nombre.
- m représente le nombre de chiffres composant chaque moitié.
La multiplication classique développe l'expression suivante :
|
X × Y = a×c×102m + (a×d + b×c)×10m + b×d |
Cette méthode nécessite quatre multiplications :
- a × c
- a × d
- b × c
- b × d
Karatsuba observe qu'il est possible de calculer :
| (a+b)(c+d) |
et d'en déduire :
|
ad + bc = (a+b)(c+d) - ac - bd |
On obtient alors uniquement trois multiplications :
|
ac bd (a+b)(c+d) |
Le produit final devient :
|
X × Y = ac×102m + ((a+b)(c+d)-ac-bd)×10m + bd |
Cette réduction paraît minime, mais elle devient extrêmement avantageuse lorsque l'algorithme est appliqué récursivement sur de très grands nombres.
Algorithme
Voici une représentation simplifiée de l'algorithme :
|
MODULE Karatsuba(x, y) SI x ou y possède peu de chiffres ALORS RETOURNER x × y FIN SI m ← moitié du nombre de chiffres a ← partie haute de x b ← partie basse de x c ← partie haute de y d ← partie basse de y ac ← Karatsuba(a,c) bd ← Karatsuba(b,d) e ← Karatsuba(a+b,c+d) RETOURNER ac × 102m + (e-ac-bd) × 10m + bd |
L'algorithme est récursif : chaque multiplication est elle-même remplacée par une nouvelle multiplication de Karatsuba jusqu'à ce que les nombres deviennent suffisamment petits pour être multipliés directement.
Exemple
Calculons :
| 1234 × 5678 |
On découpe les nombres :
|
1234 = 12 | 34 5678 = 56 | 78 |
On effectue alors seulement trois multiplications :
|
12 × 56 = 672 34 × 78 = 2652 (12+34) × (56+78) 46 × 134 = 6164 |
Le terme intermédiaire vaut alors :
|
6164 - 672 - 2652 = 2840 |
Le résultat final devient :
|
672 × 10000 + 2840 × 100 + 2652 = 7006652 |
Ce résultat correspond exactement au produit :
| 1234 × 5678 = 7006652 |
Complexité
La multiplication classique possède une complexité temporelle de :
| O(n2) |
Karatsuba réduit cette complexité à :
| O(n^1.585) |
Cette amélioration devient particulièrement intéressante lorsque les nombres contiennent plusieurs centaines ou plusieurs milliers de chiffres.
Avantages
La multiplication de Karatsuba présente plusieurs avantages :
- Elle nécessite moins de multiplications que la méthode classique.
- Elle devient beaucoup plus rapide lorsque les nombres sont très grands.
- Elle constitue la base de nombreux algorithmes modernes de multiplication.
- Elle est utilisée dans plusieurs bibliothèques spécialisées en calcul sur grands entiers.
- Son principe récursif est relativement simple à comprendre.
Inconvénients
Malgré ses qualités, cette méthode possède également quelques limites :
- Elle est plus complexe à programmer qu'une multiplication classique.
- Pour les petits nombres, elle est généralement plus lente en raison du coût de la récursivité.
- Elle nécessite davantage de mémoire temporaire.
- Les processeurs modernes possèdent déjà des instructions de multiplication très rapides, ce qui réduit son intérêt pour les entiers de petite taille.
- Au-delà d'une certaine taille de nombres, d'autres algorithmes comme Toom-Cook, Schönhage-Strassen ou les algorithmes utilisant la Transformée de Fourier Rapide (FFT) deviennent encore plus performants.
Applications
La multiplication de Karatsuba est aujourd'hui utilisée dans de nombreux domaines où les très grands nombres sont fréquents :
- les bibliothèques de grands entiers (BigInteger),
- les logiciels de calcul symbolique,
- la cryptographie (RSA, Diffie-Hellman, ECC),
- les logiciels de calcul scientifique,
- les systèmes de calcul formel,
- certains compilateurs et machines virtuelles,
- les logiciels de calcul haute précision,
- les bibliothèques mathématiques comme GMP, OpenSSL, Java BigInteger ou encore Python (int) pour les très grands entiers.
Bien que des algorithmes plus récents soient aujourd'hui encore plus performants pour les nombres gigantesques, la multiplication de Karatsuba demeure l'une des techniques fondamentales de l'algorithmique moderne. Elle représente souvent la première amélioration significative étudiée après la multiplication classique et constitue une excellente introduction aux algorithmes de multiplication rapide.