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 $n$ bits en $O(n\cdot \log n\cdot \log \log n)$ 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[modifier | modifier le code]

↑ 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 », 1974, 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.

Portail de l'informatique théorique

[1] A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.

[Aho-2] 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 », 1974, 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.

[1]

[2]