Algorithme de Schönhage-Strassen

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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]

  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 »,‎ 1974, 470 p. (ISBN 0201000296), « 7. The Fast Fourier Transform ans its Applications : The Schönhage-Strassen integer-multiplication Algorithm », p. 270-275.