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. Il a été publié en 2007 par le mathématicien suisse Martin Fürer de l'université d'État de Pennsylvanie[1]. Cet algorithme possède asymptotiquement la plus faible complexité parmi les algorithmes de multiplication et est donc meilleur que l'algorithme de Schönhage-Strassen. Son régime asymptotique n'est atteint que pour de très grands entiers.

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ù désigne 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 Proceedings of the 39th annual ACM Symposium on Theory of Computing (STOC), 11-13 juin 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.