L’un des domaines de recherche des mathématiques est le perfectionnement et l’amélioration des algorithmes et méthodes de calcul dans le but d’améliorer l’efficacité et la rapidité des systèmes qui ont quotidiennement affaire à de très grands nombres. Récemment, deux mathématiciens ont mis au point un nouvel algorithme permettant d’augmenter considérablement la rapidité de calcul dans la multiplication de grands nombres. Une avancée qui pourrait bénéficier aux ordinateurs actuels et futurs.
Deux mathématiciens australiens et français ont mis au point un nouveau moyen de multiplier les nombres, tout en résolvant un casse-tête algorithmique qui a rendu perplexes les plus grands esprits mathématiques depuis près d’un demi-siècle. Pour la plupart d’entre nous, nous multiplions des nombres relativement petits en nous rappelant nos tables de multiplication — une aide incroyablement pratique, inventée pour la première fois par les Babyloniens il y a environ 4000 ans.
Mais que faire si les nombres deviennent plus grands ? Si les nombres deviennent difficiles à manier — et en supposant que nous n’ayons ni calculatrice ni ordinateur — la plupart d’entre nous se tourneraient alors vers la multiplication longue : autre astuce utile que nous apprenons à l’école, et une technique fiable pour multiplier fondamentalement plusieurs nombres.
Il n’y a qu’un seul problème avec la multiplication longue : la méthode est lente. La raison de cette lenteur est que, pour chaque chiffre de chaque nombre du problème, vous devez effectuer une opération de multiplication distincte, avant d’ajouter tous les produits.
Bien que cela ne soit pas un problème limitant du quotidien pour la plupart des gens, c’est un problème pour les ordinateurs, car leurs propres limites dans l’exécution des calculs sont imposées par les limites des mathématiques abstraites que nous pouvons comprendre nous-mêmes.
Fondamentalement, la multiplication longue est un algorithme, mais ce n’est tout simplement pas un outil particulièrement efficace, car le processus est inévitablement fastidieux. Comme l’explique le mathématicien David Harvey de l’UNSW en Australie dans la vidéo ci-dessous, dans une multiplication où les deux nombres ont 3 chiffres (n = 3), le nombre d’opérations de multiplication distinctes impliquées est en réalité de 9, ce qui correspond à n² :
Une décennie plus tard, deux mathématiciens allemands ont réalisé une autre percée : l’algorithme de Schönhage-Strassen, qui supposait que d’autres améliorations de l’algorithme initial étaient possibles.
« Ils ont prédit l’existence d’un algorithme qui multiplie les nombres à n chiffres en utilisant essentiellement n * log (n) opérations de base » explique Harvey. « Notre article donne le premier exemple connu d’algorithme permettant d’atteindre cet objectif ».
Sur le même sujet : Pour la toute première fois, une femme remporte le prestigieux prix Abel de mathématiques
Selon les chercheurs, multiplier deux nombres ensemble d’un milliard de chiffres chacun par un processus de multiplication longue prendrait plusieurs mois à calculer. En utilisant l’algorithme de Schönhage-Strassen, cela prendrait moins de 30 secondes. Et avec leur nouveau concept, l’opération serait encore plus rapide et pourrait même représenter l’algorithme de multiplication mathématiquement le plus performant. L’algorithme a été publié sur le serveur ouvert HAL.
« En ce sens, notre travail devrait être la solution finale et définitive du problème, bien que nous ne sachions pas encore comment le prouver de manière rigoureuse » déclare Harvey. « Les gens sont à la recherche d’un tel algorithme depuis près de 50 ans. Ce n’était pas évident de prévoir que quelqu’un réussirait finalement ».
Il est à noter que le nouvel algorithme ne serait utile que pour multiplier de très grands nombres. Quelle taille exactement ? « Nous n’en avons aucune idée » expliquent les chercheurs, bien qu’un exemple cité dans l’article corresponde à 10’214’857’091’104’455’251’940’635’045’059’417’341’952.
« J’étais très étonné que cela ait été fait » confie le chercheur en informatique Martin Fürer, de la Penn State University. Fürer lui-même a essayé de réorganiser l’algorithme de Schönhage-Strassen il y a plus de dix ans, mais a finalement interrompu son travail. « Cela me semblait tout à fait désespéré ».