algorithme de Karatsuba

Pour multiplier 1234 par 5678, on peut couper chaque nombre en deux blocs de deux chiffres : 12 et 34, puis 56 et 78. La méthode classique forme quatre produits entre ces blocs. Karatsuba réutilise une combinaison de différences pour obtenir le terme du milieu avec un seul produit supplémentaire. On ne calcule donc que 12 × 56, 34 × 78 et (12 − 34) × (56 − 78). Les additions et les décalages de position restent nécessaires, mais le nombre de multiplications diminue, surtout lorsque les nombres comportent beaucoup de chiffres.

L'algorithme de Karatsuba est une méthode récursive de multiplication d'entiers. On écrit le premier entier sous la forme a × 10^k + b et le second sous la forme c × 10^k + d, où k sépare deux blocs de chiffres et a, b, c, d désignent ces blocs. La multiplication développée comporte quatre produits, mais le terme croisé ad + bc peut être obtenu à partir de trois produits : ac, bd et (a − b)(c − d). En effet, ac + bd − (a − b)(c − d) = ad + bc.

Le résultat s'assemble en replaçant chaque bloc à son rang : ac × 10^2k + (ad + bc) × 10^k + bd. Les trois multiplications sont elles-mêmes traitées de la même manière jusqu'à atteindre des blocs assez courts pour une multiplication directe. Pour deux nombres à n chiffres, la récurrence correspondante conduit à une complexité en O(n^{log₂ 3}), soit environ O(n^1,585), contre O(n²) pour la méthode classique. Le gain concerne donc principalement les grands entiers et dépend du coût des additions, soustractions et appels récursifs.

Pour deux entiers écrits a × 10^k + b et c × 10^k + d, calculez les trois produits ac, bd et (a − b)(c − d). Le terme croisé vaut alors ac + bd − (a − b)(c − d), puis le produit total vaut ac × 10^2k + [ac + bd − (a − b)(c − d)] × 10^k + bd. Répétez la règle sur les sous-produits jusqu'au seuil choisi, puis utilisez une multiplication directe.

La méthode s'applique à la multiplication d'entiers représentés dans une base de numération, notamment en base 10. Il faut pouvoir séparer chaque opérande en deux blocs de même rang, effectuer les additions et soustractions de blocs, puis recombiner les résultats avec les puissances de la base. Les différences peuvent être négatives : elles doivent donc être représentées et multipliées correctement.

Un petit produit comme 12 × 56 ne justifie généralement pas la récursion : le coût des additions et de l'organisation peut dépasser le gain d'une multiplication supprimée. Dans ce cas, une multiplication directe constitue le contre-cas pratique. Pour des nombres décimaux ou des blocs de longueur inégale, il faut d'abord choisir une représentation cohérente et ajuster le découpage ; la formule ne dispense pas de cette gestion.

On calcule 1234 × 5678 en séparant les deux nombres après leurs deux derniers chiffres. Les données sont a = 12, b = 34, c = 56, d = 78 et k = 2.

Le produit haut vaut ac = 12 × 56 = 672, le produit bas vaut bd = 34 × 78 = 2652 et le troisième produit vaut (a − b)(c − d) = (12 − 34) × (56 − 78) = (−22) × (−22) = 484.
Le terme croisé vaut ac + bd − (a − b)(c − d) = 672 + 2652 − 484 = 2840.
Le résultat assemblé vaut 672 × 10⁴ + 2840 × 10² + 2652 = 7 006 652.

Le contrôle direct donne 1234 × 5678 = 7 006 652. La décomposition est donc cohérente, puisque 672 × 10 000 = 6 720 000, 2840 × 100 = 284 000 et 2652 complètent exactement cette somme.

Dans une bibliothèque d'arithmétique multiprécision, Karatsuba peut prendre le relais de la multiplication ordinaire lorsque les opérandes dépassent un seuil de longueur. Le seuil se règle par mesure, car il dépend du coût réel des appels récursifs, des additions et de la représentation utilisée.

Pour quelques chiffres seulement, la multiplication classique reste l'alternative préférable : son nombre d'opérations est faible et son organisation est plus simple. Pour des entiers encore plus longs, une méthode de multiplication rapide différente peut devenir préférable si son coût mesuré est inférieur.

Karatsuba ne supprime pas toute opération intermédiaire et ne transforme pas une multiplication en addition. Le critère testable est le nombre de multiplications récursives : trois sous-produits sont calculés au lieu de quatre, puis des additions, soustractions et décalages recomposent le résultat.

Il ne faut pas non plus confondre la méthode classique avec une autre méthode de multiplication rapide. Pour une paire de petits entiers, la méthode classique peut être plus rapide en pratique ; l'intérêt asymptotique de Karatsuba apparaît lorsque la taille des opérandes augmente.

Le gain n'est pas garanti pour toute taille. Sous le seuil d'utilisation, les trois appels récursifs et les opérations de combinaison peuvent coûter davantage qu'une multiplication directe ; il faut alors arrêter la récursion.

La notation O(n^1,585) est une approximation de l'exposant log₂ 3, pas une durée universelle. Elle décrit la croissance du coût pour de grands nombres à n chiffres. Les constantes, la base de numération et l'implémentation peuvent modifier le seuil où le gain devient observable.

Une soustraction de blocs peut produire un résultat négatif, comme 12 − 34 = −22 dans l'exemple. Traiter ce signe comme une différence non signée fausse le troisième produit ; il faut conserver le signe avant la recombinaison.

Le prolongement naturel consiste à étudier la récurrence du coût : trois sous-problèmes de taille environ n/2 remplacent quatre multiplications de cette taille. Cette lecture explique l'exposant log₂ 3 et permet de comparer Karatsuba à la méthode classique sans réduire la comparaison à un seul exemple numérique.