-

La multiplication des nombres entiers est un problème qui occupe les mathématiciens depuis l'Antiquité. La méthode « babylonienne », que l'on apprend à l'école, revient à multiplier chaque chiffre du premier nombre avec chaque chiffre du deuxième nombre. Pour deux nombres d'un milliard de chiffres chacun, cela nécessite un milliard de milliards d’opérations, ou une trentaine d'années pour un ordinateur qui effectue un milliard d'opérations par seconde. En 1971, les mathématiciens Schönhage et Strassen ont inventé une méthode plus rapide, permettant de réduire le temps de calcul à une trentaine de secondes sur un ordinateur portable d'aujourd'hui. Dans le même travail, ils présageaient l'existence d'un algorithme encore plus rapide. Dans un nouvel article, à disposition de la communauté scientifique sur la plateforme HAL, Joris van der Hoeven, chercheur du CNRS au Laboratoire d'informatique de l'École polytechnique (CNRS/École polytechnique) et David Harvey de l’Université de Nouvelle-Galles du Sud (Australie) viennent de relever le défi en trouvant une nouvelle méthode permettant de multiplier plus vite de grands nombres entiers. Un dernier problème soulevé par Schönhage et Strassen reste ouvert : démontrer qu’il est impossible de faire encore plus rapide. Un nouveau défi pour l’informatique théorique !  

Bibliographie

Integer multiplication in time O(n log n). David Harvey, Joris van der Hoeven.
Disponible sur HAL : https://hal.archives-ouvertes.fr/hal-02070778  

Sommes-nous réels ? Sur ce blog [I]

Après plus de 1100 réponses , je présente ici les résultats du sondage.

Je suis un peu "déçu" du faible score sur l'item "Culture générale" et agréablement surpris par le résultat associé à "l'ouverture d'esprit".

Avec la fluctuation d'échantillonnage, on peut considérer que les proportions sont données à + ou - 3% .