La multiplication réinventée

Joris van der Hoeven (École polytechnique) et David Harvey (Université de Nouvelle-Galles du Sud) ont conçu un nouvel algorithme de multiplication fondamentalement plus rapide que les méthodes existantes. La méthode classique requiert n² opérations pour multiplier deux nombres à n chiffres ; l'algorithme de Schönhage-Strassen (1971) l'a réduit à n·log(n)·log(log(n)). Le nouvel algorithme atteint enfin la complexité théorique prédite : n·log(n) opérations, améliorant ainsi le calcul de nombres ayant des milliards de milliards de chiffres.

Pour illustrer : multiplier deux nombres à 100 chiffres passe de 10 000 opérations (méthode classique) à environ 200 (nouvel algorithme). Cependant, cette avancée majeure ne s'applique actuellement qu'à des nombres astronomiques (plus de 20 milliards de milliards de milliards de chiffres), inutilisables pour le quotidien. L'algorithme reste en cours de vérification par les pairs, mais devrait bénéficier à la recherche mathématique fondamentale et à des domaines comme le calcul des décimales de Pi.