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 log 2 (3)) \approx O (n 1,585)$ au lieu de $O (n 2)$ pour la méthode naïve. Il a été développé par Anatolii Alexevich Karatsuba en 1960 et publié en 1962 [1].

Principe

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 2$ produits de deux chiffres. Le temps de calcul est en O(n²).

En 1960, Karatsuba remarque que pour tout $k$ , le calcul naïf d'un produit :

(a\times 10^{k}+b)(c\times 10^{k}+d)=ac\times 10^{2k}+(ad+bc)\times 10^{k}+bd

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 :

(a\times 10^{k}+b)(c\times 10^{k}+d)=ac\times 10^{2k}+(ac+bd-(a-b)(c-d))\times 10^{k}+bd

Pour de grands nombres et en prenant $k={\frac {n}{2}}$ , 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é.

Exemple

Exécutons l'algorithme pour calculer le produit 1237 × 2587.

Pour calculer, 1237 × 2587, on écrit 1237 × 2587 = a₀ 10⁴ + (a₀ + a₂ - a₁) 10² + a₂ où a₀ = 12 × 25, a₁ = (12 – 37) × (25 – 87) = 25 × 62 et a₂ = 37 × 87.
- Pour calculer 12 × 25, on écrit 12 × 25 = a₀' 10² + (a₀' + a₂' - a₁') 10 + a₂' où a₀ = 1 × 2, a₁' = (1 – 2) × (2 – 5) = -1 × -3 et a₂' = 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 $a 1$ = 25 × 62 = 1550.
- De la même façon, on obtient $a 2$ = 37 × 87 = 3219.
- d'où 1237 × 2587 = 300 × 100² + (300 + 3219 – 1550) × 100 + 3219 = 3000000 + 196900 + 3219 = 3200119.

Le calcul complet ne demande que 9 produits de deux chiffres au lieu de 4×4 = 16 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.

Complexité

Si l'on note $K (n)$ le nombre de multiplications nécessaires pour calculer le produit de 2 nombres à $n$ chiffres avec cette méthode, on obtient la relation de récurrence suivante :

K(n)\leq 3K(\lceil n/2\rceil )

où $⌈ n /2⌉$ est la partie entière par excès de $n /2$ (l'entier suivant immédiatement $n /2$ ). On peut résoudre cette relation de récurrence (à la main ou avec le master theorem), ce qui donne une complexité en $O (n log 2 (3)) \approx O (n 1,585)$ . Ceci est plus rapide que l'algorithme standard ; pour donner un exemple, pour n = 1000, $n log 2 (3)$ est de l'ordre de 50 000 alors que n² = 1 000 000.

Quant au nombre d'additions nécessaire, il est de 4n dans la version présentée ci-dessus ; on ne mentionne pas ce coût dans la complexité car il est négligeable asymptotiquement par rapport au coût des multiplications.

Variantes

Il existe aussi une variante classique qui calcule $ad + bc$ à partir de $(a + b)(c + d)$ au lieu de $(a - b)(c - d)$ , mais cette variante est considérée comme étant moins efficace (à cause notamment des retenues dans le calcul de $a + b$ ) [2].
Il existe une variante de l'algorithme qui ne nécessite que 3,5 n additions au lieu de 4n [3].
Dans sa version récursive, l'algorithme nécessite de stocker des résultats intermédiaires, et il est utile de se poser la question de la quantité d'espace mémoire nécessaire. La version présentée ci-dessus nécessite 2n mots de stockage ; il est possible de réduire cette quantité pour que n mots suffisent, et il est même possible d'arriver à tout stocker en n'ayant besoin que de $O (log n)$ mots [3].
L'algorithme Toom-Cook est une amélioration de cette méthode, en découpant les nombres en r blocs (au lieu de 2). Le temps de calcul en $O (n 2)$ par la méthode naïve passe alors en $O (n 1+ ε)$ où $ε$ est un réel positif arbitraire.

Histoire

Dans les années 1950, Andreï Kolmogorov travailla sur la complexité des opérations arithmétiques. Vers 1956, il formula la conjecture qu'une multiplication de deux nombres de n chiffres ne pouvait être réalisée en moins de $O (n 2)$ opérations, sans doute car aucun algorithme plus rapide que la multiplication standard n'avait été trouvé[4]. Il discuta notamment de cette conjecture lors d'une réunion de la Société Mathématique de Moscou en 1956[4].

À l'automne 1960, Kolmogorov organisa un séminaire sur "les problèmes mathématiques de la cybernétique", auquel assista Karatsuba, où il parla de sa conjecture. Une semaine plus tard, Karatsuba avait trouvé son algorithme, qui prouvait que la conjecture était fausse[4] ; il en parla à Kolmogorov à la fin du séminaire suivant, qui en fut "très agité" car cela contredisait sa conjecture. La semaine suivante, Kolmogorov montra l'algorithme aux participants du séminaire, qui fut ensuite terminé[4].

En 1962 Kolmogorov écrivit un article, sans doute avec Yuri Ofman (en), sur la méthode et le soumit à publication avec le nom de Karatsuba et d'Ofman à Doklady Akad. Nauk SSSR ; Karatsuba n'apprit l'existence de l'article que plus tard, lors de sa réédition[4].

Références

(ru) Anatolii A. Karatsuba et Yuri P. Ofman, « Умножение многозначных чисел на автоматах », Doklady Akademii Nauk SSSR, vol. 146,‎ 1962, p. 293–294 (lire en ligne) traduit en anglais dans (en) « Multiplication of Multidigit Numbers on Automata », Physics-Doklady, vol. 7,‎ 1963, p. 595–596 (présentation en ligne)
Richard Brent, Paul Zimmerman, Modern Computer Arithmetic, Cambridge University Press, 2010, page 6.
Richard Brent, Paul Zimmerman, page 40.
Karatsuba, A. A. (1995). The complexity of computations. Proceedings of the Steklov Institute of Mathematics-Interperiodica Translation, vol 211, p. 169-183.

Bibliographie

A. Karatsuba and Yu Ofman, Multiplication of Many-Digital Numbers by Automatic Computers. Doklady Akad. Nauk SSSR Vol. 145 (1962), p. 293–294. Translation in Physics-Doklady 7 (1963), p. 595–596.
Karatsuba A. A. Berechnungen und die Kompliziertheit von Beziehungen (German) // Elektron. Inform.-verarb. Kybernetik, 11, 603–606 (1975).
Karatsuba A. A. The complexity of computations // Proc. Steklov Inst. Math., 211, 169–183 (1995); translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995).
Knuth D. E. The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp., Reading (1969).
Karatsuba Multiplication on Fast Algorithms and the FEE
Richard Brent, Paul Zimmerman, Modern Computer Arithmetic, Cambridge University Press, 2010.

Portail de l'informatique théorique
Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (ru) Anatolii A. Karatsuba et Yuri P. Ofman, « Умножение многозначных чисел на автоматах », Doklady Akademii Nauk SSSR, vol. 146,‎ 1962, p. 293–294 (lire en ligne) traduit en anglais dans (en) « Multiplication of Multidigit Numbers on Automata », Physics-Doklady, vol. 7,‎ 1963, p. 595–596 (présentation en ligne)

[mca2-2] Richard Brent, Paul Zimmerman, Modern Computer Arithmetic, Cambridge University Press, 2010, page 6.

[mca-3] Richard Brent, Paul Zimmerman, page 40.

[karatsuba95-4] Karatsuba, A. A. (1995). The complexity of computations. Proceedings of the Steklov Institute of Mathematics-Interperiodica Translation, vol 211, p. 169-183.