En effet, fin mars, David Harvey et Joris van der Hoeven ont pu montrer que la multiplication de grands entiers est « quasi linéaire ». Cette question tenait depuis 1971 ! On sait désormais que l’on peut multiplier deux entiers de n chiffres en un nombre d’opérations élémentaires proportionnel à n ln(n), avec ln le logarithme népérien. Mais peut-être est-il possible de faire mieux encore : on n’a jamais su prouver que la multiplication n’était pas « linéaire » ! Un article sur le fonctionnement du nouvel algorithme sera proposé dans notre prochain numéro.
Maths pour tousBrève
Multiplier en temps quasi-linéaire : percée | Tangente
Multiplier en temps quasi-linéaire
L'opération consistant à multiplier ensemble deux entiers a été introduite il y a plusieurs milliers d'années. En 2019, enfin, on a réussi à perfectionner cet algorithme !
NouveauÉcouter l'articlesur Tangente Audio6:15Ouvrir dans Tangente Audio
