Algorithme de Fürer

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 multiplication (et donc meilleur que l'algorithme de Schönhage-Strassen), néanmoins le régime asymptotique est atteint pour des nombres très grands.

Avant l'algorithme de Fürer, l'algorithme de Schönage-Strassen, datant de 1971, permettait de multiplier deux entiers en temps O(nlog nlog log n)[2]. Arnold Schönhage et Volker Strassen ont aussi conjecturé que la complexité minimale du produit rapide est O(nlogn), où n est le nombre de bits utilisés dans l'écriture binaire des deux entiers en entrée. L'algorithme de Fürer possède une complexité en n \log n 2^{O(\log^* n)}, où log  * n représente le logarithme itéré. La différence entre les termes log log n et 2^{\log^* n} dans les complexités est asymptotiquement à l'avantage de l'algorithme de Fürer mais le régime asymptotique n'apparaît que pour des nombres très grands[3].

Références

  1. ↑ [PDF] M. Fürer (2007). Faster Integer Multiplication in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, Californie, États-Unis.
  2. ↑ A. Schönhage et V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), pp. 281–292.
  3. ↑ À partir de nombres de l'ordre de 2^{2^{64}}.
v · Naïf  · Strassen  · Coppersmith-Winograd
Produit d'entiers Naïf  · Karatsuba  · Toom-Cook  · Schönhage-Strassen  · Fürer

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Fürer de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • 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 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 à… …   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 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

  • 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 Karatsuba — L algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres avec une complexité en au lieu de O(n2) pour la méthode naïve. Note : . Sommaire 1 Énoncé …   Wikipédia en Français

  • Algorithme de karatsuba — L algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres avec une complexité en au lieu de O(n2) pour la méthode naïve. Note : . Sommaire 1 Énoncé …   Wikipédia en Français

Share the article and excerpts

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