Une nouvelle méthode pour multiplier les très grands nombres

Publié par Adrien le 20/05/2019 à 08:00
Source: CNRS Journal
2
Restez toujours informé: suivez-nous sur Google Actualités (icone ☆)

Deux chercheurs ont développé une nouvelle méthode pour multiplier les très grands nombres. Une avancée potentiellement historique pour l'informatique.

Adaptation des proportions d'une recette, calcul de pourcentages, résolution de problèmes de mathématiques, programmes informatiques... La multiplication est cruciale dans bien des domaines. Rien d'étonnant donc à ce qu'elle soit l'une des quatre opérations algébriques rudimentaires enseignées à l'école - avec l'addition, la soustraction (La soustraction est l'une des opérations basiques de l'arithmétique. La soustraction...) et la division. Or voilà que lors de travaux récents, Joris van der Hoeven, du Laboratoire d'informatique (L´informatique - contraction d´information et automatique - est le domaine...) de l'École polytechnique, à Palaiseau (Essonne), et son collègue australien David Harvey, de l'Université (Une université est un établissement d'enseignement supérieur dont l'objectif est la...) de Nouvelle-Galles du Sud, sont parvenus à développer une méthode permettant de multiplier plus rapidement les nombres entiers (donc sans virgule). De quoi "aider à augmenter la vitesse de calcul des ordinateurs", se réjouit Joris van der Hoeven.


Salle du serveur Grid'5000 à Nancy. Le nouvel algorithme pourrait augmenter la vitesse de calcul des ordinateurs. C. Frésillon / LORIA / CNRS Photothèque

L'incroyable lenteur de la méthode classique

Pour comprendre, revenons sur la méthode de multiplication classique apprise à l'école. Elle consiste à superposer les deux nombres à multiplier, à multiplier chaque chiffre du premier nombre par chaque chiffre du second et à additionner les résultats.

Ainsi, pour multiplier deux entiers formés chacun de 3 chiffres, il faut 3 x 3 multiplications à un chiffre, soit 9 opérations, plus une addition des 9 résultats. Pour deux nombres à 5 chiffres chacun, 5 x 5, soit 25 multiplications, plus une addition des 25 résultats. Plus généralement, pour un nombre à n chiffres, cela nécessite n x n, ou n^2 multiplications.

Ainsi, plus les nombres multipliés sont grands, plus le nombre d'opérations nécessaires est important.

"Pour deux nombres d'un milliard de chiffres chacun, il faut un milliard fois un milliard de multiplications, soit un milliard de milliards (ou 10^18) d'étapes. Donc si on suppose qu'il faut une seconde pour faire un milliard d'opérations, comme c'est le cas pour un ordinateur moyen actuel, cela requiert au final un milliard de secondes, soit... près de 32 années !", précise Joris van der Hoeven. D'où l'intérêt de développer des techniques plus rapides.

Un algorithme inédit

Par le passé, plusieurs algorithmes de multiplication plus rapides que la technique classique ont déjà été conçus. Notamment, en 1971 les mathématiciens allemands Arnold Schönhage et Volker Strassen sont arrivés à un procédé qui réduit le nombre d'opérations nécessaires àn x (logFermerLe logarithme (En mathématiques, une fonction logarithme est une fonction définie sur à valeurs dans ,...) est une fonction mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide...) qui "transforme" les multiplications en additions (par exemple, log(100)=2, log(1000)=3 et log(1 000 000)=6).(n)) x log(log(n)). "Cette avancée a permis de réduire le temps de multiplication de deux nombres d'un milliard de chiffres chacun à une trentaine de secondes sur un ordinateur portable d'aujourd'hui, contre, pour rappel, plus de 30 ans", souligne Joris van der Hoeven. D'ailleurs, l'algorithme d'Arnold Schönhage et de Volker Strassen est désormais utilisé par la plupart des logiciels permettant de calculer avec des grands nombres.


Dans les années 1970, l'algorithme des mathématiciens allemands Volker Strassen (à gauche) et Arnold Schönhage (à droite) a réduit le temps de multiplication de deux nombres d'un milliard de chiffres chacun à une trentaine de secondes contre plus de 30 ans auparavant ! Author Konrad Jacobs / Source Archives of the Mathematisches Forschungsinstitut Oberwolfach

Schönhage et Strassen ont aussi prédit l'existence d'un algorithme encore plus rapide, qui permettrait de multiplier les nombres à n chiffres en seulement n x (log (n)) opérations. "Notre récent article donne le premier exemple connu d'algorithme permettant cela", indique Joris van der Hoeven. Plus précisément, le nouvel algorithme réduit le nombre d'opérations à réaliser - "des multiplications, mais aussi, et surtout, des additions et des soustractions", souligne le chercheur (Un chercheur (fem. chercheuse) désigne une personne dont le métier consiste à faire de la...) -, à Cx(nx(logn)), où C est une constante qui dépend de la vitesse de la machine effectuant les calculs. Par exemple si C vaut 1, la multiplication de deux nombres à 10 chiffres nécessiterait 10 x log (10), soit 10 opérations ; contre 10 x 10, soit 100 opérations avec la technique classique. Et la multiplication de deux nombres à 100 chiffres, 200 opérations plutôt que 10 000.

"Si cette nouvelle technique - en cours de vérification par des experts - s'avère correcte, elle constituerait une avancée majeure pour la recherche fondamentale, dans le domaine de la théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en...) informatique", note Fredrik Johansson, chercheur à l'Institut de mathématiques de Bordeaux.

Valable seulement pour les très grands nombres

Problème: pour l'instant la nouvelle méthode n'est valable que pour de très grands nombres, "avec plus de 20 milliards de milliards de milliards de chiffres", détaille Joris van der Hoeven. Soit des nombres astronomiques, difficile même à concevoir ! À titre de comparaison, l'âge de l'Univers n'est "que" de 14 milliards d'années... On l'aura compris, pour l'instant la nouvelle méthode n'est d'aucune utilité pour les multiplications simples du quotidien... et ne nous aidera donc pas pour, par exemple, remplir la déclaration de revenus !

"Nous avons conçu notre démonstration de manière à ce qu'elle soit la plus courte et la plus simple possible ; ce qui impliquait de se limiter à des nombres très grands, explique Joris Van Der Hoeven.Cela dit, à l'avenir nous comptons bien tenter d'identifier des variantes de l'algorithme pouvant s'appliquer à des nombres plus petits. "

De quoi accélérer la recherche mathématique ?

Le nouvel algorithme devrait améliorer la vitesse de calcul des ordinateurs, dans certains domaines. "Par exemple en recherche en mathématique, pour calculer les innombrables décimales du nombre Pi ((3,14159...), une constante impliquée dans de nombreuses formules de maths, d'ingénierie et de physique (La physique (du grec φυσις, la nature) est étymologiquement la...)", indique Joris Van Der Hoeven. À noter: en mars dernier Google a annoncé avoir établi un nouveau record, avec le calcul de 31 000 milliards de décimales après la virgule.

"Des variantes de notre algorithme pourraient aussi être implantées dans des logiciels utilisant l'algorithme dit de la “transformation de Fourier rapide” (ou FFT), utilisé couramment pour traiter et interpréter des signaux numérisés dans divers domaines: simulation informatique, mécanique des fluides, traitement d'images, etc. ", ajoute l'informaticien (On nommait dans les années 1960-1980 informaticien ou informaticienne une personne...).

Sera-t-il possible un jour de découvrir un algorithme encore plus rapide ? "Probablement que non: en 1971, Schönhage et Strassen ont prédit que n* log (n) est le meilleur résultat possible", répond Joris van der Hoeven, qui a copublié pas moins de 6 articles sur ce sujet. "Cette fois, à moins d'une très grosse surprise, nous avons sûrement mis un point final à cette recherche."
Page générée en 0.349 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise