- Accueil
- Presse
- Communiqués et Dossiers de Presse
- Une Méthode Plus Rapide Pour Multiplier de Très Grands Nombres
Une méthode plus rapide pour multiplier de très grands nombres
09.04.19
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 !
Integer multiplication in time O(n log n). David Harvey, Joris van der Hoeven.
Disponible sur HAL : https://hal.archives-ouvertes.fr/hal-02070778
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 !
Integer multiplication in time O(n log n). David Harvey, Joris van der Hoeven.
Disponible sur HAL : https://hal.archives-ouvertes.fr/hal-02070778
À propos de l’École polytechnique
Largement internationalisée (41% de ses étudiants, 40% de son corps d’enseignants), l’École polytechnique associe recherche, enseignement et innovation au meilleur niveau scientifique et technologique. Sa formation promeut une culture d’excellence à forte dominante en sciences, ouverte sur une grande tradition humaniste. À travers son offre de formation – bachelor, cycle ingénieur polytechnicien, master, programmes gradués, programme doctoral, doctorat, formation continue – l’École polytechnique forme des décideurs à forte culture scientifique pluridisciplinaire en les exposant à la fois au monde de la recherche et à celui de l’entreprise. Avec ses 23 laboratoires, dont 22 sont unités mixtes de recherche avec le CNRS, le centre de recherche de l’X travaille aux frontières de la connaissance sur les grands enjeux interdisciplinaires scientifiques, technologiques et sociétaux. L’École polytechnique est membre fondateur de l’Institut Polytechnique de Paris.
À lire aussi
Fondation
Innovation, Recherche, La Fondation • 14.11.24
La Fondation de l’École polytechnique lance sa troisième campagne de levée de fonds avec un engagement fort « Servir la science » et un objectif de collecte de 200 millions d’euros
École polytechnique
Recherche, Prix et Distinctions • 04.11.24
Le climatologue Nicolas Bellouin remporte le Prix Edward Appleton 2024 de l'Institute of Physics
École polytechnique
