Algorithme de Schönhage-Strassen

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. 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

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Schönhage-Strassen de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Schönhage-Strassen — Algorithme de Schönhage Strassen 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é… …   Wikipédia en Français

  • Algorithme De Multiplication — Les techniques de multiplication permettent de calculer le résultat d une multiplication. Graphiquement, il s agit de transformer un rectangle multiplicateur × multiplicande en une ligne, en conservant le nombre d éléments. Exemples: Sommaire 1… …   Wikipédia en Français

  • Algorithme de Fürer — L algorithme de Fürer est un algorithme de multiplication de très grands entiers. L algorithme a été publié par Martin Fürer de Penn State en 2007[1]. Cet algorithme possède asymptotiquement la plus faible complexité parmi les algorithmes de… …   Wikipédia en Français

  • Algorithme de multiplication — Les techniques de multiplication permettent de calculer le résultat d une multiplication. Graphiquement, il s agit de transformer un rectangle multiplicateur × multiplicande en une ligne, en conservant le nombre d éléments. Exemples: Sommaire 1… …   Wikipédia en Français

  • Algorithme de Karmarkar — Traduction terminée Karmarkar s algorithm → …   Wikipédia en Français

  • Algorithme De Strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme de strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme de Strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969[1]. La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme De Coppersmith-Winograd — L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en fait l algorithme le plus efficace… …   Wikipédia en Français

  • Algorithme de Coppersmith–Winograd — Algorithme de Coppersmith Winograd L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”