Algorithme de Fürer

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és 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

Avant l'algorithme de Fürer, l'algorithme de Schönage-Strassen, datant de 1971, permettait de multiplier deux entiers en temps ${\displaystyle 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 ${\displaystyle O(n\log n)}$, où n est le nombre de bits utilisés dans l'écriture binaire des deux entiers en entrée.

Complexité

L'algorithme de Fürer possède une complexité en ${\displaystyle O(n\log n\ 2^{O(\log ^{*}n)})}$, où ${\displaystyle \log ^{*}n}$ désigne le logarithme itéré. La différence entre les termes ${\displaystyle \log \log n}$ et ${\displaystyle 2^{\log ^{*}n}}$ 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 ${\displaystyle O(n\log n\ 16^{\log ^{*}n})}$ opérations et donne un algorithme qui ne nécessite que ${\displaystyle O(n\log n\ 8^{\log ^{*}n})}$ opérations, ainsi qu'un troisième algorithme en temps ${\displaystyle O(n\log n\ 4^{\log ^{*}n})}$ 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 ${\displaystyle O(n\log n)}$ 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 à ${\displaystyle 2^{1729^{12}}}$^[5].

Références

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 ${\displaystyle 2^{2^{64}}}$.
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)

• Arithmétique et théorie des nombres
• Portail de l'informatique théorique