Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Karatsuba
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.