Une nouvelle méthode pour multiplier les très grands nombres
Publié par Adrien le 20/05/2019 à 08:00
Source: CNRS Journal
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 (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .) 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 (L'addition est une opération élémentaire, permettant notamment de décrire la réunion de quantités ou l'adjonction de grandeurs extensives de même nature, comme les longueurs, les aires, ou les volumes. En...), la soustraction (La soustraction est l'une des opérations basiques de l'arithmétique. La soustraction combine deux ou plusieurs grandeurs du même type, appelées opérandes, pour donner un seul nombre, appelé la...) et la division (La division est une loi de composition qui à deux nombres associe le produit du premier par l'inverse du second. Si un nombre est non nul, la fonction "division par ce nombre" est la réciproque de la...). 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 d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des...) 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 production du savoir (recherche), sa conservation et sa transmission (études supérieures). Aux...) de Nouvelle-Galles du Sud (Le sud est un point cardinal, opposé au nord.), 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 (Un chiffre est un symbole utilisé pour représenter les nombres.) du premier nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde...) pour faire un milliard d'opérations, comme c'est le cas pour un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un...) 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é (Le passé est d'abord un concept lié au temps : il est constitué de l'ensemble des configurations successives du monde et s'oppose au futur sur une échelle des temps...), 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 , continue et transformant un produit en somme. Le logarithme de base a où a est un réel strictement positif différent de 1...) est une fonction mathématique (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres,...) 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 (Un ordinateur portable, laptop (en Suisse) ou encore PC portable est un ordinateur personnel qui, grâce à un poids et un encombrement limités, peut être...) 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 recherche. Il est difficile de bien cerner le métier de chercheur tant les domaines de recherche sont...) -, à 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. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un problème peut être...) informatique", note Fredrik Johansson, chercheur à l'Institut (Un institut est une organisation permanente créée dans un certain but. C'est habituellement une institution de recherche. Par exemple, le...) de mathématiques de Bordeaux.

Valable seulement pour les très grands nombres

Problème: pour l'instant (L'instant désigne le plus petit élément constitutif du temps. L'instant n'est pas intervalle de temps. Il ne peut donc être...) 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 (L'Univers est l'ensemble de tout ce qui existe et les lois qui le régissent.) 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 « science de la nature ». Dans un sens général et ancien, la physique désigne la connaissance de la...)", indique Joris Van Der Hoeven. À noter: en mars dernier Google (Google, Inc. est une société fondée le 7 septembre 1998 dans la Silicon Valley en Californie par Larry Page et Sergey Brin, auteurs du moteur de recherche Google. Depuis 2001,...) 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 exerçant un métier dans l'informatique. La...).

Sera-t-il possible un jour (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons du Soleil éclairent le ciel. Son début (par rapport à minuit heure locale) et...) 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.251 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique