Des mathématiciens ont mis au point un algorithme pour multiplier deux nombres entiers beaucoup plus rapidement qu’avec une opération classique. De quoi drastiquement accélérer la vitesse de calcul des ordinateurs… en théorie.
au sommaire
Commençons d'abord par la mauvaise nouvelle : cette découverte mathématique ne vous permettra pas de faire plus rapidement vos comptes bancaires ou de calculer en un clin d'œilœil le nombre d'œufs à acheter pour faire vos crêpes d'anniversaire. L'algorithme mis au point par David Harvey, de l'Université de Nouvelle-Galles du Sud, en Australie, et Joris van der Hoeven, de l'École Polytechnique, ne s'applique pour l'instant qu'aux très grands nombres. S'il est inaccessible aux êtres humains, en revanche, il pourrait s'avérer d'une grande utilité pour optimiser la vitesse de calcul des ordinateurs et pour la programmation.
Rappelons d'abord comment effectuer une multiplication entre deux nombres : il faut superposer les deux nombres et calculer pour chaque chiffre le produit de la multiplication avec les chiffres du nombre au-dessous. Pour un entier à 3 chiffres, cela nous donne au total 3 x 3 opérations à effectuer. De manière générale, pour un entier n, on doit faire n2 opérations (que l'on peut aussi noter n^2).
Une hypothèse de 1971 qui restait à démontrer
En 1962, le mathématicienmathématicien Anatoly Karatsuba avait déjà réussi à abaisser ce seuil à n1,58 et, en 1971, Arnold Schönhage et Volker Strassen ont développé un algorithme réduisant encore la solution à n (log(n)) log(log(n)), où log est la fonction logarithme. « Avec cette formule, une multiplication entre deux nombres à plusieurs milliards de chiffres prend à peine 26 secondes, contre 6 mois avec la méthode traditionnelle », assure David Harvey dans le magazine New Scientist. C'est d'ailleurs l'algorithme de multiplication le plus utilisé à l'heure actuelle dans le monde, compatible avec la logique algébrique de la plupart des ordinateursordinateurs. Les deux mathématiciens allemands avaient dès cette époque émis l'hypothèse que la formule pouvait encore être simplifiée en n(log(n)) opérations.
Mieux évaluer le temps de calcul des ordinateurs
C'est ce que viennent de prouver Harvey et van der Hoeven dans leur démonstration publiée le 18 mars dernier. Ainsi, pour n = 2, une multiplication normale nécessite 4 opérations, contre environ 2,41 avec leur méthode. Pour n = 1.000, le nombre d'opérations est réduit de 10.000 à 200 ! Mais il y a un hic : ce nouvel algorithme n'est pour l'instant valable que pour des nombres d'une taille supérieure à \({\displaystyle 2^{1729^{12}}}\)(ou 2^(1.729^12)), soit des entiers à plusieurs milliards de milliards de milliards de chiffres.
« Notre démonstration est à des fins purement théoriques », reconnaissent les deux auteurs qui ne se sont pas penchés sur un moyen d'appliquer leur formule à des nombres plus petits. Pour autant, cette méthode pourrait, par exemple, permettre aux développeurs d'estimer le temps de calcul nécessaire à l'exécution leurs propres algorithmes. En tout cas, il pourrait s'agir du bout de l'histoire : « Je serai très étonné que l'on trouve un nouvel algorithme capable de battre n(log(n)), indique David Harvey. Mais sait-on jamais, des chose étranges arrivent ». À vos claviersclaviers.
Ce qu’il faut
retenir
- Des chercheurs ont mis au point un algorithme qui simplifie considérablement la multiplication entre deux nombre entiers.
- Cette méthode ne s’applique pour l’instant qu’aux très grands nombres.
- Elle pourrait servir à prédire la vitesse de calcul des algorithmes.
