Algorithme de Fürer

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

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(n \log n \log\log n)[2]. Arnold Schönhage et Volker Strassen ont aussi conjecturé que la complexité minimale du produit rapide est O(n \log n), 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[modifier | modifier le code]

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