Sections

La multiplication réinventée

Dossier
Paru le 10.04.2019
2019, bonne année de science

La multiplication réinventée

15.05.2019, par
Deux chercheurs ont développé une nouvelle méthode pour multiplier les très grands nombres. Une avancée potentiellement historique pour l’informatique. Cet article fait partie du TOP 5 des contenus les plus lus sur notre site en 2019

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 et la division. Or voilà que lors de travaux récents, Joris van der Hoeven, du Laboratoire d’informatique de l’École polytechnique1, à Palaiseau (Essonne), et son collègue australien David Harvey, de l’Université 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.
 

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.
 

Le nouvel algorithme permet de multiplier deux nombres à 100 chiffres en seulement 200 opérations au lieu des 10 000.

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 n2 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 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 ! », 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 est une fonction mathématique 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))2. « 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 de 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 !
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 !

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 –, à Cx(nx(log n)), 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é informatique », note Fredrik Johansson, chercheur à l’Institut de mathématiques de Bordeaux3.
 

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 », 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.

Salle du serveur Grid'5000 à Nancy. Le nouvel algorithme pourrait augmenter la vitesse de calcul des ordinateurs.
Salle du serveur Grid'5000 à Nancy. Le nouvel algorithme pourrait augmenter la vitesse de calcul des ordinateurs.

« 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)4, 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.
 
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. » ♦
 

Notes
  • 1. Unité CNRS/École polytechnique de Palaiseau.
  • 2. A. Schönhage et V. Strassen, «Schnelle Multiplikation grosser Zahlen», Computing, Vol.7, 281-292pp., Springer Verlag, septembre 1971.
  • 3. Unité CNRS/Université de Bordeaux/Bordeaux INP.
  • 4. Pour fast Fourier transform.
Aller plus loin

Auteur

Kheira Bettayeb

Journaliste scientifique freelance depuis dix ans, Kheira Bettayeb est spécialiste des domaines suivants : médecine, biologie, neurosciences, zoologie, astronomie, physique et nouvelles technologies. Elle travaille notamment pour la presse magazine nationale.

Commentaires

0 commentaire
Pour laisser votre avis sur cet article
Connectez-vous, rejoignez la communauté
du journal CNRS