Algorithme de Karatsuba

Un article de Wikipédia, l'encyclopédie libre.

L'algorithme de Karatsuba est une méthode permettant de multiplier rapidement deux nombres avec une complexité en O( $n ln(3) / ln(2)$ ). Note : $ln(3) / ln(2)$ est environ égal à 1,58.

[modifier] Énoncé

Pour multiplier deux nombres de n chiffres, la méthode usuelle demande de multiplier chaque chiffre du multiplicateur par chaque chiffre du multiplicande. Cela exige donc n² produits de deux chiffres. On dit que le temps de calcul est en O(n²).

En 1962, Karatsuba, remarquant que le calcul de (a × 10^k + b)(c × 10^k + d) qui, sous forme développée ac × 10^2k + (ad + bc) × 10^k + bd, 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 :

(a × 10^k + b)(c × 10^k + d) = ac × 10^2k + (ac + bd – (a – b)(c – d)) × 10^k + bd

Ainsi, pour calculer 26 × 34, on calcule

2 × 3 = 6

6 × 4 = 24

(2 – 6) × (3 – 4) = 4

Le résultat final est alors 6 × 100 + (6 + 24 – 4) × 10 + 24 = 600 + 260 + 24 = 884. La multiplication par la base de numération (10 dans l'exemple précédent mais en binaire pour les machines) qui correspond à un décalage de chiffre, et les additions sont peu coûteuses en temps. Pour de grands nombres, la méthode peut être itérée 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.

[modifier] Exemple

Ainsi, 12378456 × 25874215 sera calculé comme suit :

1237 × 2587

8456 × 4215

(1237 – 8456) × (2587 – 4215) = 7219 × 1628

Le produit 1237 × 2587 sera lui-même calculé comme suit :

12 × 25

37 × 87

(12 – 37) × (25 – 87) = 25 × 62

Le produit 12 × 25 sera calculé au moyen de :

1 × 2 = 2

2 × 5 = 10

(1 – 2) × (2 – 5) = 1 × 3 = 3

pour obtenir 12 × 25 = 2 × 100 + (2 + 10 – 3) × 10 + 10 = 300. On obtiendra de même :

12 × 25 = 300

37 × 87 = 3219

25 × 62 = 1550

d'où 1237 × 2587 = 300 × 100² + (300 + 3219 – 1550) × 100 + 3219 = 3000000 + 196900 + 3219 = 3200119. On procèdera de même pour les produits 8456 × 4215 et 7219 × 1628, obtenant finalement :

1237 × 2587 = 3200119

8456 × 4215 = 35642040

7219 × 1628 = 11752532

D'où, enfin : 12378456 × 25874215 = 3200119 × 10000² + (3200119 + 35642040 – 11752532) × 10000 + 35652040

= 320011900000000 + 270896270000 + 35642040

= 320282831912040

Le calcul complet ne demande que 27 produits de deux chiffres au lieu de 64 par la méthode usuelle. Bien entendu, cette méthode, fastidieuse à la main, révèle toute sa puissance pour une machine devant effectuer le produit de grands nombres. On obtient alors un algorithme dit de multiplication rapide de deux nombres de n chiffres en $n ln(3) / ln(2)$ opérations élémentaires (tels que produit ou somme de deux chiffres) au lieu de n². Pour n = 1000, $n ln(3) / ln(2)$ est de l'ordre de 50 000 alors que n² = 1 000 000.

Toom et Cook améliorèrent cette méthode en découpant les nombres en r blocs (au lieu de 2). Le temps de calcul en O(n²) par la méthode usuelle passe alors en O(n^1+ε) où ε est un réel positif arbitraire.

[modifier] Voir aussi

Récupérée de « http://fr.wikipedia.org../../../a/l/g/Algorithme_de_Karatsuba_3075.html »

Catégorie : Algorithme numérique

Algorithme de Karatsuba

Un article de Wikipédia, l'encyclopédie libre.

[modifier] Énoncé

[modifier] Exemple

[modifier] Voir aussi

Views

Navigation

Contribuer

Rechercher

Autres langues