Algorithme de Schönhage-Strassen

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique théorique
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[modifier | modifier le code]

  1. A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
  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 », , 470 p. (ISBN 0201000296), « 7. The Fast Fourier Transform ans its Applications : The Schönhage-Strassen integer-multiplication Algorithm », p. 270-275.