Introduction
L'algorithme de Fürer (Fürer's Algorithm) est un algorithme de multiplication rapide d'entiers proposé en 2007 par le mathématicien suisse Martin Fürer. Il constitue une évolution importante des méthodes de multiplication fondées sur la Transformée de Fourier Rapide (FFT) et représente l'une des plus grandes avancées théoriques dans le domaine de l'arithmétique multiprécision depuis l'algorithme de Schönhage-Strassen publié en 1971. Son objectif est de réduire encore davantage le temps nécessaire à la multiplication de très grands nombres, contenant plusieurs millions de chiffres, en diminuant le coût des transformées successives utilisées lors des calculs.
L'algorithme de Fürer n'est pas destiné aux calculs courants réalisés dans les langages de programmation traditionnels. Pour des nombres de petite ou de moyenne taille, les méthodes classiques, Karatsuba ou Toom-Cook demeurent plus efficaces en raison de leur simplicité et de leur faible coût fixe. En revanche, lorsque les opérandes deviennent gigantesques, l'algorithme de Fürer présente une meilleure complexité asymptotique que Schönhage-Strassen. Bien que cette amélioration soit essentiellement théorique pour de nombreuses applications pratiques, elle a ouvert la voie aux recherches ayant conduit quelques années plus tard à l'algorithme de Harvey-van der Hoeven.
Historique
Pendant plusieurs décennies, l'algorithme de Schönhage-Strassen a été considéré comme la méthode de référence pour la multiplication des très grands entiers. Sa complexité de O(n log n log log n) représentait déjà une amélioration spectaculaire par rapport aux méthodes précédentes.
En 2007, Martin Fürer démontra qu'il était possible de faire encore mieux en modifiant la manière dont les transformées rapides étaient réalisées. Son algorithme réduit progressivement le coût des opérations les plus coûteuses en utilisant des racines de l'unité spécialement choisies et des techniques récursives particulièrement efficaces.
Cette découverte constitua une avancée importante en algorithmique et relança les recherches sur la multiplication rapide d'entiers, lesquelles aboutirent finalement, en 2019, à l'algorithme de Harvey-van der Hoeven.
Principe
Comme les autres algorithmes modernes de multiplication rapide, l'algorithme de Fürer ne multiplie pas directement les chiffres des deux nombres.
Son fonctionnement peut être résumé ainsi :
- Décomposer les grands entiers en plusieurs blocs.
- Représenter ces blocs sous forme de polynômes.
- Transformer ces polynômes dans un domaine où leur multiplication devient plus simple.
- Multiplier les coefficients correspondants.
- Effectuer une transformée inverse.
- Reconstituer le nombre final.
La principale innovation de Fürer réside dans la manière d'effectuer les transformées rapides. Au lieu d'utiliser uniquement une FFT classique comme Schönhage-Strassen, il choisit des structures algébriques permettant de réduire progressivement le coût des calculs récursifs.
Les idées fondamentales
L'algorithme repose notamment sur plusieurs concepts mathématiques avancés :
- la représentation des entiers sous forme de polynômes ;
- les transformées rapides récursives ;
- l'utilisation de racines complexes soigneusement choisies ;
- la réduction du coût des multiplications internes ;
- une meilleure organisation des calculs récursifs.
Ces optimisations permettent de diminuer les facteurs multiplicatifs qui apparaissent dans les algorithmes FFT classiques.
Algorithme simplifié
Le fonctionnement général peut être représenté de façon simplifiée comme suit :
|
MODULE Fuerer(A,B) Découper les deux nombres Construire les polynômes Appliquer une transformée rapide optimisée Multiplier les coefficients Appliquer la transformée inverse Effectuer les retenues Reconstruire le résultat RETOURNER le produit |
Naturellement, une implémentation réelle est beaucoup plus complexe et nécessite plusieurs niveaux de récursion ainsi que de nombreuses optimisations mathématiques.
Complexité
La complexité des principaux algorithmes de multiplication peut être comparée de la façon suivante :
| Algorithme | Complexité asymptotique |
|---|---|
| Multiplication classique | O(n2) |
| Karatsuba | O(n^1,585) |
| Toom-Cook | O(n^1,465) |
| Schönhage-Strassen | O(n log n log log n) |
| Fürer | O(n log n · K^log* n) |
| Harvey-van der Hoeven | O(n log n) |
Dans cette formule :
- K représente une constante supérieure à 1 pouvant être choisie arbitrairement proche de 1.
- log* n (logarithme itéré) désigne le nombre de fois qu'il faut appliquer la fonction logarithme avant que le résultat devienne inférieur ou égal à 1.
Le logarithme itéré croît extrêmement lentement. Même pour des nombres astronomiquement grands, sa valeur demeure très faible, ce qui explique pourquoi l'algorithme de Fürer est souvent décrit comme ayant une complexité presque égale à O(n log n).
Pourquoi cette amélioration est-elle importante ?
À première vue, la différence entre :
| O(n log n log log n) |
et
| O(n log n · K^log* n) |
peut sembler négligeable.
Cependant, lorsqu'il s'agit de multiplier des nombres contenant plusieurs milliards de chiffres, ces facteurs supplémentaires représentent plusieurs milliards d'opérations. Les améliorations apportées par Fürer deviennent alors significatives et démontrent qu'il est possible de continuer à réduire la complexité de la multiplication d'entiers.
Sur le plan théorique, cet algorithme a surtout montré que l'on pouvait dépasser les performances de Schönhage-Strassen, ce qui a motivé de nombreuses recherches ultérieures.
Avantages
L'algorithme de Fürer possède plusieurs avantages :
- il améliore la complexité asymptotique de Schönhage-Strassen ;
- il constitue une avancée théorique majeure en algorithmique ;
- il est particulièrement adapté aux entiers extrêmement grands ;
- il a inspiré plusieurs travaux de recherche plus récents ;
- il représente une étape importante vers l'algorithme optimal de Harvey-van der Hoeven.
Inconvénients
Malgré ses qualités, cette méthode présente plusieurs limites :
- elle est extrêmement difficile à comprendre et à implémenter ;
- elle repose sur des concepts avancés d'algèbre et d'analyse numérique ;
- elle est généralement plus lente que Schönhage-Strassen pour les tailles de nombres rencontrées dans les applications courantes ;
- son intérêt est principalement théorique ;
- très peu de bibliothèques utilisent directement une implémentation complète de cet algorithme.
En pratique, les coûts fixes associés à sa mise en ouvre compensent souvent les gains théoriques lorsque les nombres ne sont pas suffisamment grands.
Applications
L'algorithme de Fürer est principalement étudié dans les domaines suivants :
- recherche en algorithmique ;
- théorie des nombres ;
- calcul multiprécision ;
- cryptographie avancée ;
- calcul formel ;
- démonstrations mathématiques assistées par ordinateur ;
- développement de nouvelles bibliothèques d'arithmétique.
Il est rarement utilisé directement dans les applications commerciales, mais ses idées ont influencé plusieurs algorithmes modernes.
Comparaison avec les autres méthodes
| Algorithme | Utilisation principale |
|---|---|
| Multiplication classique | Petits nombres |
| Multiplication russe | Enseignement et démonstrations |
| Karatsuba | Grands entiers |
| Toom-Cook | Très grands entiers |
| Schönhage-Strassen | Entiers gigantesques |
| Fürer | Recherche théorique sur les très grands entiers |
| Harvey-van der Hoeven | État de l'art théorique actuel |
Les bibliothèques modernes sélectionnent automatiquement l'algorithme le plus adapté selon la taille des opérandes. Dans la plupart des cas, elles utilisent d'abord la multiplication classique, puis Karatsuba, ensuite Toom-Cook et enfin des méthodes basées sur la FFT. L'algorithme de Fürer demeure principalement une référence théorique ayant servi de transition entre Schönhage-Strassen et Harvey-van der Hoeven.
Remarque
L'importance de l'algorithme de Fürer réside davantage dans son apport scientifique que dans son utilisation quotidienne. Il a démontré qu'il était possible de dépasser la borne asymptotique de Schönhage-Strassen grâce à une conception plus raffinée des transformées rapides. Les idées introduites par Martin Fürer ont profondément influencé les recherches sur la multiplication d'entiers et ont directement contribué aux travaux qui ont permis, quelques années plus tard, de concevoir le premier algorithme atteignant une complexité asymptotique de O(n log n), aujourd'hui représenté par l'algorithme de Harvey-van der Hoeven.