Un algorithme pour multiplier deux grands nombres plus rapidement. © robertmandel138, Fotolia

Sciences

Oubliez vos tables de multiplication : voici une nouvelle méthode bien plus efficace

ActualitéClassé sous :Mathématiques , multiplication , algorithme de Schönhage Strassen

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.

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 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).

Les chercheurs ont réussi à démonter l’algorithme simplifié de Schönhage-Strassen, permettant de multiplier deux nombres avec beaucoup moins d’opérations. © Сергей Лабутин, Fotolia

Une hypothèse de 1971 qui restait à démontrer

En 1962, le mathé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 ordinateurs. 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 claviers.

  • 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.
Abonnez-vous à la lettre d'information La quotidienne : nos dernières actualités du jour.

!

Merci pour votre inscription.
Heureux de vous compter parmi nos lecteurs !

Cela vous intéressera aussi