Introduction
Les méthodes de multiplication basées sur la transformée de Fourier rapide, plus connues sous l'acronyme FFT (Fast Fourier Transform), constituent l'une des techniques les plus performantes pour multiplier des nombres entiers comportant des milliers, voire des millions de chiffres. Contrairement aux algorithmes classiques, manipulant directement les chiffres des nombres, ces méthodes transforment le problème de la multiplication en un problème de convolution de polynômes. Cette transformation permet de réduire considérablement le nombre d'opérations nécessaires lorsque les opérandes deviennent extrêmement grands.
Les algorithmes fondés sur la FFT sont principalement utilisés dans les bibliothèques d'arithmétique multiprécision, les logiciels de calcul scientifique, la cryptographie, les systèmes de calcul formel ainsi que dans certains compilateurs spécialisés. Pour les nombres de petite ou de moyenne taille, les méthodes classiques, Karatsuba ou Toom-Cook demeurent généralement plus rapides. En revanche, lorsque les nombres dépassent plusieurs dizaines de milliers de chiffres, les algorithmes utilisant la FFT deviennent nettement plus efficaces.
Principe
L'idée fondamentale consiste à représenter un grand entier sous la forme d'un polynôme.
Par exemple, le nombre :
| 12345678 |
peut être représenté comme :
| 1×10^7 + 2×10^6 + 3×10^5 + ... |
ou encore sous la forme d'un polynôme :
| P(x) = a0 + a1x + a2x2 + ... |
où chaque coefficient correspond à un groupe de chiffres.
La multiplication de deux grands nombres revient alors à multiplier deux polynômes.
Or, la multiplication directe de deux polynômes est relativement coûteuse. La FFT permet de rendre cette opération beaucoup plus rapide grâce aux étapes suivantes :
- Transformer les deux polynômes dans le domaine fréquentiel.
- Multiplier simplement les valeurs correspondantes.
- Effectuer une transformée inverse.
- Reconstituer le nombre final.
Cette approche réduit énormément le nombre d'opérations lorsque les nombres deviennent très volumineux.
La convolution
Le coeur de cette méthode repose sur la convolution.
Si l'on possède deux polynômes :
- A(x)
- B(x)
leur multiplication consiste à calculer chacun des coefficients du polynôme résultat.
La méthode classique effectue de nombreuses multiplications croisées :
- a0×b0
- a0×b1
- a1×b0
- a2×b3
- ...
La FFT transforme cette convolution complexe en une simple multiplication terme à terme dans un autre espace mathématique.
C'est précisément cette propriété qui rend cette technique extrêmement rapide.
La transformée de Fourier rapide
La Transformée de Fourier Rapide (FFT) est un algorithme permettant de calculer très efficacement une transformée de Fourier discrète (DFT).
La DFT convertit une suite de valeurs dans un domaine fréquentiel.
La FFT réalise exactement le même calcul mais avec beaucoup moins d'opérations.
La complexité passe de :
| O(n2) |
à :
| O(n log n) |
Cette amélioration est considérable lorsque n devient très grand.
Étapes de l'algorithme
Une multiplication basée sur la FFT peut être résumée par les étapes suivantes :
- Découper les deux nombres
- Construire deux polynômes
- Calculer la FFT du premier polynôme
- Calculer la FFT du second polynôme
- Multiplier chaque coefficient
- Calculer la transformée inverse (IFFT)
- Effectuer les retenues
- Reconstruire le résultat final
Les retenues ne sont calculées qu'à la toute fin de l'algorithme.
Algorithme simplifié
|
MODULE MultiplicationFFT(A,B) Construire les polynômes FFT(A) FFT(B) BOUCLE POUR chaque coefficient C[i] ← A[i] × B[i] FIN BOUCLE POUR IFFT(C) Calculer les retenues RETOURNER le résultat |
Naturellement, une implémentation réelle est beaucoup plus complexe que cette représentation simplifiée.
Exemple conceptuel
Supposons les deux nombres :
|
1234 5678 |
Ils sont découpés en coefficients :
|
[1 2 3 4] [5 6 7 8] |
La FFT transforme ces deux suites de coefficients.
Les valeurs correspondantes sont multipliées.
Une transformée inverse permet ensuite de retrouver les coefficients du produit.
Enfin, les retenues sont propagées afin de produire :
| 7006652 |
Le calcul obtenu est exactement identique à celui d'une multiplication classique.
Complexité
La multiplication classique possède une complexité :
| O(n2) |
Karatsuba :
| O(n^1.585) |
Toom-Cook :
| O(n^1.465) |
Les méthodes utilisant la FFT obtiennent généralement une complexité proche de :
| O(n log n) |
Il s'agit d'une amélioration spectaculaire lorsque les nombres comportent plusieurs centaines de milliers ou plusieurs millions de chiffres.
Avantages
Les méthodes fondées sur la FFT présentent de nombreux avantages :
- elles sont extrêmement rapides pour les très grands nombres ;
- leur complexité est proche de la meilleure connue en pratique ;
- elles sont utilisées dans la majorité des bibliothèques multiprécision modernes ;
- elles permettent de manipuler des nombres contenant plusieurs millions de chiffres ;
- elles servent également dans de nombreux autres domaines scientifiques.
Inconvénients
Malgré leurs excellentes performances, ces méthodes présentent plusieurs inconvénients :
- leur implémentation est très complexe ;
- elles nécessitent une excellente maîtrise des nombres complexes ou des corps finis ;
- elles utilisent davantage de mémoire que Karatsuba ou Toom-Cook ;
- elles sont souvent plus lentes que les méthodes classiques pour les petits nombres ;
- elles peuvent être sensibles aux erreurs d'arrondi lorsque la FFT repose sur des nombres à virgule flottante.
Pour cette raison, plusieurs implémentations modernes utilisent plutôt une Transformée Numérique (NTT - Number Theoretic Transform), qui fonctionne entièrement avec des entiers et élimine les problèmes de précision liés aux nombres réels.
Applications
Les méthodes de multiplication utilisant la FFT sont employées dans de nombreux domaines :
- bibliothèques de grands entiers (BigInteger) ;
- logiciels de calcul symbolique ;
- calcul scientifique haute précision ;
- cryptographie ;
- calcul distribué ;
- logiciels d'algèbre informatique ;
- théorie des nombres ;
- recherche en mathématiques ;
- simulation numérique.
Elles sont notamment présentes dans des bibliothèques telles que GNU Multiple Precision (GMP), MPIR, FLINT, NTL et dans plusieurs moteurs de calcul utilisés par les logiciels de mathématiques.
Les variantes
La multiplication basée sur la FFT regroupe en réalité plusieurs familles d'algorithmes :
| Algorithme | Description |
|---|---|
| Cooley-Tukey FFT | Algorithme FFT classique utilisé dans de nombreux domaines scientifiques. |
| Schönhage-Strassen | Première méthode pratique de multiplication de très grands entiers utilisant une transformée de Fourier dans des anneaux modulaires. |
| Fürer's Algorithm | Améliore encore les performances asymptotiques pour des nombres gigantesques. |
| Harvey-van der Hoeven | Algorithme publié en 2019 atteignant une complexité asymptotique de O(n log n), considérée comme optimale pour la multiplication entière. |
| NTT (Number Theoretic Transform) | Variante de la FFT utilisant uniquement des entiers modulaires afin d'éviter les erreurs d'arrondi. |
Remarque
Bien que les méthodes basées sur la FFT soient aujourd'hui les plus performantes pour les multiplications de très grands entiers, elles ne remplacent pas systématiquement les autres algorithmes. Les bibliothèques modernes choisissent automatiquement la méthode la plus appropriée en fonction de la taille des opérandes. Ainsi, une multiplication commence généralement par utiliser la méthode classique, puis passe à Karatsuba, ensuite à Toom-Cook, et enfin aux algorithmes fondés sur la FFT lorsque les nombres deviennent suffisamment grands. Cette stratégie hybride permet d'obtenir les meilleures performances dans toutes les situations.