Actualités

Un algorithme vraiment efficace pour multiplier deux entiers ?

Le 14 avril 2019

Les chercheurs David Harvey et Joris van der Hoeven ont annoncé le 18 mars 2019 un algorithme pour multiplier efficacement les entiers.

La multiplication des entiers est une opération très élémentaire pour un ordinateur. Cependant, la question de la faire la plus efficacement possible constitue un domaine de recherche actif. On évalue l’efficacité par le nombre d’opérations, qui est exprimé en fonction du nombre $n$ de chiffres des nombres à multiplier.

L’algorithme que l’on apprend à l’école élémentaire nécessite environ $n^2$ étapes ($n$ produits pour multiplier le premier nombre par chaque chiffre du second et il y a $n$ chiffres dans le second, d’où $n^2$ multiplications de deux nombres à un chiffres et environ $2n$ additions avec autant de retenues au pire, ce qui n’ajoute rien de significatif).

En 1971, Arnold Schönhage et Volker Strassen ont inventé l’algorithme qui porte leur nom. Révolutionnaire, il consiste à faire un grand détour par la transformée de Fourier rapide, et permet de faire le calcul en environ $n\cdot\log n\cdot\log\log n$ opérations, ce qui est vraiment beaucoup plus rapide que l’algorithme naïf. C’est resté l’algorithme le plus efficace jusqu’à celui de Martin Fürer en 2007, qui fait passer la complexité à $n\cdot\log n\cdot2^{O(\log^*n)}$.

Avec l’algorithme de Harvey et van der Hoeven, le nombre d’opérations élémentaires à effectuer est de l’ordre de $n\log n$. Ce qui est remarquable, c’est que c’est (conjecturalement) le meilleur ordre de grandeur possible. La réponse apportée est donc, en principe, pratiquement optimale (même si on pourrait travailler pour améliorer « les constantes »).

Et en pratique ? En l’état, cela n’a aucun intérêt. En effet, pour pouvoir appliquer l’algorithme, il faut que le nombre de chiffres des facteurs soit supérieur à $2^{1729^{12}}$, c’est-à-dire quelque chose comme $10^{2\cdot10^{38}}$ – attention, ce nombre gigantesque désigne le nombre de chiffres à partir duquel l’algorithme s’applique. Si l’on compare à l’âge de l’univers ($10^{17}\;\mathrm{s}$) ou au nombre d’atomes dans l’univers entier (quelque $10^{80}$ atomes), on voit que l’on ne pourrait même pas écrire un tel nombre...

Il faut attendre la confirmation de la validité de l’algorithme par les experts de la revue à laquelle il sera soumis. Sous cette réserve, et malgré l’absence d’application pratique à l’algorithme dans sa version présente, il s’agit d’une très belle avancée conceptuelle sur un problème compréhensible dès l’école primaire.

En savoir plus : la page du projet “Integer multiplication in time $O(n\log n)$”

Partager cette actualité