En poursuivant votre navigation, vous acceptez l'utilisation de cookies destinés à des fins de mesure d'audience, à améliorer la performance de ce site et à vous proposer des services et contenus personnalisés. En savoir plus

X

La meilleure méthode pour multiplier les très grands nombres ?

Joris van der Hoeven (CNRS/Laboratoire d’informatique de l’École polytechnique) et David Harvey (School of Mathematics and Statistics/UNSW) viennent de publier une nouvelle méthode de multiplication des très grands nombres plus rapide que toutes les précédentes. Mais s’agit-il de la méthode ultime ?

La méthode classique de multiplication enseignée à l’école primaire consiste à multiplier chaque chiffre du premier nombre avec chaque chiffre du deuxième nombre. Si les nombres en question sont constitués de 3 chiffres chacun, le nombre de multiplications à effectuer est de 9. Mais si les nombres sont constitués d’un milliard de chiffres, c’est un milliard de milliards d’opérations qu’il faut enchaîner . Même un ordinateur capable de traiter un milliard d’opérations par seconde mettra plus de 30 ans à fournir le résultat, d’où la nécessité de trouver des méthodes plus performantes.

Dans un article publié en 1971, les mathématiciens Schönhage et Strassen proposèrent une méthode de multiplication des très grands nombres qui améliorait nettement la situation, puisque le temps de calcul passait de 30 ans à 30 secondes.  Dans le même article, ils annonçaient qu’il existait probablement une méthode encore plus rapide, mais qu’ils n’étaient pas parvenus à découvrir. Ils donnaient cependant des détails sur la forme sous laquelle elle devrait s’exprimer, et s’avançaient même à prédire qu’elle serait indépassable en termes de rapidité.

Près de 50 ans plus tard, cette méthode semble enfin avoir été trouvée grâce aux travaux de David Harvey et Joris van der Hoeven. Si elle présente bien la plupart des caractéristiques annoncées par Schönhage et Strassen, la démonstration qu’il n’existe pas de méthode encore plus rapide reste à faire.

Pour Joris van der Hoeven, le nouvel algorithme de multiplication qu’il a mis au point avec David Harvey aura des répercussions dans de nombreux domaines : « la vitesse de multiplication est la vitesse fondamentale dans beaucoup d’autres calculs, qu’il s’agisse des décimales de Pi, de l’intégration des équations différentielles ou de l’extraction des racines carrées. »

Au moins d'un point de vue théorique, cet algorithme permettra également de calculer plus vite les transformées de Fourier rapides, un algorithme largement utilisé dans tous les domaines de la physique, que ce soit dans le traitement du signal ou les outils de modélisation.

L’article présentant en détail cette nouvelle méthode est à retrouver sur la plateforme HAL et actuellement en phase de relecture par des experts.

 

Bibliographie : Integer multiplication in time O(n log n). David Harvey, Joris van der Hoeven