algorithme de Karatsuba

ALGEBRE
ANALYSE

L’algorithme de Karatsuba (1960) est une méthode de multiplication rapide.

Les méthodes de multiplication rapide ont été rendues possibles et nécessaires avec l’apparition des ordinateurs. La méthode de Karatsuba permet la multiplication de deux nombres de n chiffres avec une complexité en O(n^log2(3)) au lieu de O(n²) pour la méthode naïve qui multiplie chaque chiffre du multiplicande par chaque chiffre du multiplicateur.
L’idée de la méthode de Karatsuba est que :
(a × 10^k + b)(c × 10^k + d) = ac × 10^2k + (ad + bc) × 10^k + bd,
nécessite le calcul des quatre produits ac, ad, bc et bd,

mais écrit sous la forme :
ac × 10^2k + (ac + bd – (a – b)(c – d)) × 10^k + bd

il n’y a que 3 produits ac, bd, et (a-b)(c-d).
Appliquée à des grands nompbres, la méthode réduit de façon importante le nombre de multiplications.

Elle s’applique évidemment dans toutes les bases et pas seulmement en base 10.