Algorithme de Schönhage-Strassen
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
L’algorithme de Schönhage-Strassen est un algorithme de multiplication de grands entiers par transformée de Fourier rapide publié en 1971 par Arnold Schönhage et Volker Strassen[1].
Dans le modèle de complexité courant des machines de Turing à plusieurs bandes, il permet de multiplier deux entiers de bits en opérations[2]. Jusqu'en 2007 et la publication de l'algorithme de Fürer, cela en faisait la méthode asymptotiquement la plus rapide connue pour la multiplication d'entiers.
Références
- ↑ A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
- ↑ Cf. à ce sujet Alfred V. Aho, J. E. Hopcroft et Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, coll. « Series in Computer Science and Information Processing », , 470 p. (ISBN 978-0-201-00029-0), « 7. The Fast Fourier Transform ans its Applications : The Schönhage-Strassen integer-multiplication Algorithm », p. 270-275.
v · m Multiplication | |||||
|---|---|---|---|---|---|
| |||||
| Propriétés |
| ||||
| Exemples |
| ||||
| Algorithmes de multiplication |
| ||||
| Algorithmes de vérification |
| ||||
Portail de l'informatique théorique
