Algorithme de Fürer

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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 une des plus faibles 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.

Histoire[modifier | modifier le code]

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.

Complexité[modifier | modifier le code]

L'algorithme de Fürer possède une complexité en , où désigne le logarithme itéré. La différence entre les termes et est asymptotiquement à l'avantage de l'algorithme de Fürer mais le régime asymptotique n'est atteint que pour des très grands nombres[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. Ces algorithmes sont parfois regroupés sous le terme d'algorithme de Harvey-van der Hoeven-Lecerf.

En 2019, Harvey et van der Hoeven atteignent une complexité algorithmique de pour la multiplication, battant la complexité de l'algorithme de Fürer. Le régime asymptotique est toutefois atteint pour des nombres d'une taille supérieure à [5].

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.
  5. David Harvey et Joris van der Hoeven, Integer multiplication in time O(n log n)