Introduction
La multiplication Harvey-van der Hoeven est l'un des algorithmes de multiplication d'entiers les plus avancés connus à ce jour. Présenté en 2019 par les mathématiciens David Harvey (Université de Nouvelle-Galles du Sud) et Joris van der Hoeven (Centre national de la recherche scientifique - CNRS), cet algorithme est le premier à atteindre de manière démontrée la complexité asymptotique optimale pour la multiplication de très grands nombres entiers. Cette découverte constitue une avancée majeure en algorithmique, puisqu'elle résout un problème ouvert qui préoccupait les chercheurs depuis près d'un demi-siècle.
Cet algorithme n'a pas été conçu pour remplacer les méthodes classiques utilisées dans les programmes quotidiens. Son intérêt apparaît uniquement lorsque les nombres manipulés contiennent des millions, voire des milliards de chiffres. Dans ces conditions extrêmes, les méthodes traditionnelles deviennent progressivement moins efficaces, tandis que l'algorithme de Harvey-van der Hoeven conserve une croissance presque linéaire de son temps d'exécution. Bien qu'il soit encore relativement récent et complexe à implémenter, il représente aujourd'hui l'état de l'art en matière de multiplication d'entiers.
Historique
Pendant de nombreuses années, la multiplication classique, enseignée dans les écoles, est demeurée la seule méthode utilisée pour multiplier des nombres. Son coût étant proportionnel au carré du nombre de chiffres, les chercheurs ont rapidement cherché des techniques plus efficaces.
L'évolution des principaux algorithmes peut être résumée ainsi :
| Année | Algorithme | Complexité approximative |
|---|---|---|
| Antiquité | Multiplication classique | O(n2) |
| 1960 | Karatsuba | O(n^1,585) |
| 1963 | Toom-Cook | O(n^1,465) |
| 1971 | Schönhage-Strassen | O(n log n log log n) |
| 2007 | Fürer | proche de O(n log n) |
| 2019 | Harvey-van der Hoeven | O(n log n) |
Cette progression montre que les chercheurs ont progressivement réduit le nombre d'opérations nécessaires pour multiplier des très grands entiers.
Principe
Comme les méthodes modernes précédentes, l'algorithme Harvey-van der Hoeven ne multiplie pas directement les chiffres composant les deux nombres.
Son fonctionnement repose sur plusieurs idées :
- représenter les entiers sous forme de polynômes ;
- transformer ces polynômes dans un autre domaine mathématique ;
- effectuer une multiplication terme à terme ;
- reconstruire ensuite le résultat initial.
Cette approche est similaire aux méthodes fondées sur la Transformée de Fourier Rapide (FFT), mais elle utilise des techniques beaucoup plus élaborées permettant d'éliminer certains facteurs de complexité qui subsistaient dans les algorithmes précédents.
Autrement dit, Harvey-van der Hoeven ne remet pas en cause le principe général des méthodes FFT ; il les perfectionne afin d'atteindre la meilleure complexité théorique possible.
Les idées fondamentales
L'algorithme repose notamment sur :
- une décomposition récursive des grands entiers ;
- l'utilisation de transformées rapides particulièrement optimisées ;
- une organisation très efficace des calculs intermédiaires ;
- une réduction des coûts liés aux transformées successives ;
- une meilleure gestion des multiplications de polynômes.
Ces optimisations permettent de supprimer le facteur supplémentaire log log n qui apparaissait encore dans l'algorithme de Schönhage-Strassen.
Algorithme simplifié
Une représentation très simplifiée est la suivante :
|
MODULE HarveyVanDerHoeven(A,B) Découper les nombres Construire les polynômes Appliquer les transformées rapides Multiplier les coefficients Appliquer la transformée inverse Effectuer les retenues Reconstruire le résultat RETOURNER le produit |
Dans la réalité, l'algorithme comprend plusieurs dizaines d'étapes supplémentaires faisant intervenir des objets mathématiques avancés. Cette représentation ne montre que le principe général.
Complexité
La principale innovation de cette méthode réside dans sa complexité.
Les principales méthodes de multiplication peuvent être comparées ainsi :
| Algorithme | Complexité |
|---|---|
| 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 | proche de O(n log n) |
| Harvey-van der Hoeven | O(n log n) |
La fonction O(n log n) est aujourd'hui considérée comme la meilleure complexité asymptotique que l'on puisse raisonnablement atteindre pour la multiplication d'entiers.
Pourquoi est-ce important ?
La différence entre deux algorithmes peut sembler faible lorsqu'on observe uniquement leur formule mathématique.
Cependant, lorsqu'un calcul porte sur plusieurs centaines de millions de chiffres, quelques opérations supplémentaires répétées des millions de fois peuvent représenter plusieurs heures de calcul.
Les grands centres de recherche, les laboratoires scientifiques et les logiciels spécialisés effectuant des calculs extrêmement volumineux bénéficient directement de ces améliorations.
Applications
Bien que très récent, cet algorithme intéresse déjà plusieurs domaines :
- calcul multiprécision ;
- théorie des nombres ;
- calcul symbolique ;
- cryptographie expérimentale ;
- recherche en algorithmique ;
- calcul scientifique haute précision ;
- démonstrations mathématiques assistées par ordinateur ;
- logiciels manipulant des nombres gigantesques.
Pour les applications ordinaires, les nombres sont beaucoup trop petits pour que cette méthode présente un avantage.
Avantages
La multiplication Harvey-van der Hoeven possède plusieurs qualités :
- elle atteint la meilleure complexité asymptotique actuellement démontrée ;
- elle améliore encore les méthodes FFT classiques ;
- elle permet de traiter des nombres contenant plusieurs millions ou milliards de chiffres ;
- elle représente l'état actuel de la recherche en multiplication d'entiers ;
- elle constitue une avancée théorique majeure en informatique et en mathématiques.
Inconvénients
En contrepartie, cette méthode présente plusieurs limites :
- son implémentation est extrêmement complexe ;
- elle nécessite des connaissances avancées en théorie des nombres et en analyse algorithmique ;
- elle est beaucoup plus difficile à comprendre que Karatsuba ou Toom-Cook ;
- elle est inutile pour les nombres de petite taille ;
- très peu de bibliothèques logicielles l'implémentent actuellement sous une forme complète en raison de sa complexité.
Comparaison avec les autres méthodes
| Algorithme | Domaine d'utilisation |
|---|---|
| Multiplication classique | Petits nombres |
| Multiplication russe | Calculs simples et démonstrations pédagogiques |
| Karatsuba | Grands entiers |
| Toom-Cook | Très grands entiers |
| Schönhage-Strassen | Entiers gigantesques |
| Harvey-van der Hoeven | Entiers extrêmement gigantesques (recherche et calcul multiprécision) |
Les bibliothèques modernes choisissent généralement automatiquement l'algorithme le plus adapté en fonction de la taille des nombres. Une multiplication commence souvent par la méthode classique, passe ensuite à Karatsuba, puis à Toom-Cook, ensuite à Schönhage-Strassen ou à une variante fondée sur la FFT, et enfin, dans les cas les plus extrêmes, peut bénéficier des avancées apportées par les travaux de Harvey et van der Hoeven.
Remarque
L'algorithme de Harvey-van der Hoeven est avant tout une percée théorique. En démontrant qu'il est possible de multiplier des entiers avec une complexité de O(n log n), il a répondu à une question ouverte depuis plusieurs décennies. Son influence dépasse largement le cadre de la multiplication elle-même : les techniques développées pour cet algorithme inspirent déjà de nouveaux travaux en calcul symbolique, en théorie algorithmique et dans l'optimisation des bibliothèques de calcul multiprécision. À mesure que les implémentations évolueront, certaines de ses idées pourraient être intégrées dans les futures générations de bibliothèques mathématiques utilisées par les langages de programmation et les logiciels scientifiques.