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 [2]. Arnold Schönhage et Volker Strassen ont aussi conjecturé que la complexité minimale du produit rapide est , 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 , où représente le logarithme itéré. La différence entre les termes et 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].

Un article écrit en 2014 par Harvey, van der Hoeven et Lecerf[4] permet de montrer que l'algorithme de Fürer optimisé nécessite opérations, et donne un algorithme qui ne nécessite que opérations, ainsi qu'un troisième algorithme en temps mais dont la validité repose sur une conjecture portant sur les nombres de Mersenne.

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 .
  4. David Harvey, Joris van der Hoeven et Grégoire Lecerf, Even faster integer multiplication.