La multiplication des très grands nombres réinventée... et bientôt dans nos ordinateurs ?

26 mai 2019 à 14h30
5
Mathématiques tableau calculs chiffres

La recherche en mathématique avance. Deux chercheurs, Joris Van Der Hoeven, du Laboratoire informatique de l'École polytechnique à Palaiseau, et David Harvey, de l'Université Nouvelle-Galles du Sud en Australie, ont découvert une méthode de multiplication des grands entiers plus rapide qu'aucune autre. Or, qui dit amélioration des méthodes de multiplication, dit possibilités d'avancées dans le domaine de l'informatique.

La multiplication des grands nombres entiers est devenu un sujet de recherche plébiscité depuis le développement de l'informatique, car son perfectionnement suppose l'accélération, et donc l'amélioration, de nombreux algorithmes. Depuis les années 1960, la science ne cesse de progresser dans ce domaine. Les découvertes d'aujourd'hui s'inscrivent dans cette dynamique.

La multiplication, la plus fastidieuse des opérations ?

La multiplication fait partie des opérations courantes. Apprise dès l'école primaire, elle est utile dans la vie de tous les jours. Pour autant, qui pose encore ses multiplications ? Ces deux chercheurs ont remis en évidence la complexité et surtout la lenteur du processus, qui demande à effectuer plusieurs multiplications puis plusieurs additions avant d'arriver au résultat final. De fait, plus les nombres à calculer sont importants, plus l'opération est complexe et donc... plus elle est lente.

Cela peut s'avérer problématique pour la vivacité de nos ordinateurs, comme nous l'explique Joris van der Hoeven : « Pour deux nombres d'un milliard de chiffres chacun, il faut un milliard fois un milliard de multiplications, soit un milliard de milliards (ou 1018) 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 ! »

ordinateur bureau pixabay.jpg_cropped_823x823

Un nouvel algorithme

Les deux scientifiques ont réussi à créer un algorithme qui réduit pour la première fois le nombre d'opérations à Cx(nx(log n). Dans cette formule, C est un nombre constant, qui est uniquement dépendant de la vitesse de l'ordinateur sur lequel le calcul est effectué. Le logarithme log permet quant à lui de transformer la multiplication en addition, c'est-à-dire qu'au lieu de multiplier 10 000 on va ajouter 5 (pour faire simple, cela revient ici à compter les zéros). Ce système devrait donc accélérer et optimiser les calculs des grands entiers. Le chercheur de l'École polytechnique souligne que, dans certains cas, l'algorithme, en diminuant le temps calcul des ordinateurs, pourrait s'avérer très utile : « 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 ».

Joris Van Der Hoeven indique que « des variantes de l'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 ». En effet, nombre d'algorithmes actuels se basent sur cet outil mathématique capital qu'est la transformation de Fourier rapide (ou FFT pour Fast Fourier Transform), qui « associe à une fonction dont la variable est le temps (ou la position spatiale) une fonction dépendant d'une fréquence (ou d'une quantité dite conjuguée de la position) »

Ces théories doivent encore être vérifiées et validées par un comité d'experts, comme le signale Fredrik Johansson, chercheur à l'Institut de mathématiques de Bordeaux, mais si elles le sont, cela «  constituerait une avancée majeure pour la recherche fondamentale, dans le domaine de la théorie de la complexité informatique ». Et, demain, qui sait, ces progrès scientifiques pourraient peut être trouver leur place dans nos ordinateurs...

Source : CNRS
Soyez toujours courtois dans vos commentaires.
Respectez le réglement de la communauté.
5
0
mo256
Bonjour<br /> Si la formule Cx(nx(log n) décrit le nombre d’opérations (comme c’est écrit dans l’article), je ne vois pas le rapport avec la vitesse de l’ordinateur qui elle intervient dans la vitesse de calcul mais pas dans le nombre d’opérations. Il y a donc une petite erreur dans l’article je pense.
Jacky67
Il n’y a que ça qui te choque toi ???<br /> La formule en elle-même, telle qu’écrite ici ne te dérange pas ?<br /> Le fait qu’on ne dise pas ce que représentent le “x” et le “n” non plus ?<br /> La phrase expliquant qu’on transforme une multiplication en addition non plus ?<br /> Et le fait qu’il y ait soit disant 5 zéros dans “10 000”, ou que log(10000) soit égal à 5 non plus ?
chickenwing
Faut que tu contactes le cnrs d’urgence tu viens de faire une découverte majeure
XnRay
Il y a en effet quelques erreurs dans l’article qui visait à vulgariser le sujet afin de le rendre compréhensible par tous avant de démontrer une rigueur scientifique irréprochable :<br /> Dans la formule citée, C est une constante dépendante en effet de l’algorithme et non de la vitesse de calcul. Sa valeur précise n’est pas très utile ici, il suffit juste de savoir qu’elle ne dépend pas de n.<br /> n est le nombre de chiffres dans les opérandes à multiplier. Dans l’exemple cité dans l’article, n vaut 1 milliard.<br /> x n’est pas une variable ici, mais un raccourci typographique pour symboliser l’opérateur de multiplication.<br /> Le logarithme décimal (log) de 10 000 est en effet 4, et celui de 100 000 est 5. L’idée ici était de montrer qu’avec le nouvel algorithme, une multiplication impliquant un nombre composé de 10 000 chiffres peut se calculer avec 4 multiplications intermédiaires au lieu de 10 000, ce qui est beaucoup plus simple.<br /> Il manque effectivement une parenthèse fermante en fin de formule.<br /> Ceci étant dit, merci quand même à Marion LHostis pour cet article très intéressant et compréhensible. J’ai hâte de voir si ce nouvel algorithme va effectivement pouvoir être intégré dans de prochaines applications.
ares-team
Ils n’ont rien inventé…<br /> C’est ainsi que calcule les Asiatiques depuis toujours.
mo256
Merci XnRay pour ta réponse tout en mesure.<br /> Je ne m’explique pas pourquoi ma remarque a généré des réponses aussi extrêmes ou méprisantes.<br /> Et bien sûr merci à la vulgarisatrice ou au vulgarisateur
Voir tous les messages sur le forum

Actualités du moment

#WTF Quand l'Autopilot Tesla suggère de rouler à contre-sens
Google développe une IA pour prédire les risques de cancer du poumon
Amazon investit dans deux start-up facilitant l’apprentissage des enfants
La Chine dévoile un prototype de train à sustentation magnétique circulant à 600 km/h
Kung Fury 2 mettra en scène Arnold Schwarzenegger et Michael Fassbender
IBM :
Une IA créée par Google prouve plus de 1200 théorèmes mathématiques
Apex Legends n'en finit plus de chuter
Le stockage gratuit de Samsung Cloud passe de 15 à 5 Go
Haut de page