Algorithme de Karatsuba

En informatique, l'algorithme de Karatsuba est un algorithme pour multiplier rapidement deux nombres de n chiffres avec une complexité temporelle en O(n) ≈ O(n) au lieu de O(n) pour la méthode naïve. Il a été développé par Anatolii Alexevich Karatsuba en 1960 et publié en 1962 . Pour multiplier deux nombres de n chiffres, la méthode naïve multiplie chaque chiffre du multiplicateur par chaque chiffre du multiplicande. Cela exige donc n produits de deux chiffres. Le temps de calcul est en O(n2). En 1960, Karatsuba remarque que pour tout , le calcul naïf d'un produit : qui semble nécessiter les quatre produits ac, ad, bc et bd, peut en fait être effectué seulement avec les trois produits ac, bd et (a – b)(c – d) en regroupant les calculs sous la forme suivante : Pour de grands nombres et en prenant , la méthode peut être appliquée de manière récursive pour les calculs de ac, bd et (a – b)(c – d) en scindant à nouveau a, b, c et d en deux et ainsi de suite. C'est un algorithme de type diviser pour régner. La multiplication par la base de numération (10 dans l'exemple précédent, mais 2 pour les machines) correspond à un décalage de chiffre, et les additions sont peu coûteuses en temps ; ainsi, le fait d'être capable de calculer les grandeurs nécessaires en 3 produits au lieu de 4 mène à une amélioration de complexité. Exécutons l'algorithme pour calculer le produit 1237 × 2587. Pour calculer, 1237 × 2587, on écrit 1237 × 2587 = a0 104 + (a0 + a2 - a1) 102 + a2 où a0 = 12 × 25, a1 = (12 – 37) × (25 – 87) = 25 × 62 et a2 = 37 × 87. Pour calculer 12 × 25, on écrit 12 × 25 = a0' 102 + (a0' + a2' - a1') 10 + a2' où a0' = 1 × 2, a1' = (1 – 2) × (2 – 5) = -1 × -3 et a2' = 2 × 5. Les calculs 1 × 2 = 2, 2 × 5 = 10 et -1 × -3 = 3 se réalisent en temps constant. On obtient 12 × 25 = 2 × 100 + (2 + 10 – 3) × 10 + 10 = 300. De la même façon, on obtient a1 = 25 × 62 = 1550. De la même façon, on obtient a2 = 37 × 87 = 3219. d'où 1237 × 2587 = 300 × 1002 + (300 + 3219 – 1550) × 100 + 3219 = 3000000 + 196900 + 3219 = 3200119.