- Multiplier de grands nombres est difficile. En 1971, deux professeurs allemands ont prédit un algorithme qui le rendrait plus facile, mais personne ne l’a jamais prouvé.
- Jusqu’à présent.
- Des mathématiciens australiens et français affirment que leur algorithme peut rendre la multiplication et d’autres types d’arithmétique beaucoup plus efficaces.
Depuis l’école primaire, les multiplications complexes sont un casse-tête. Mais un professeur adjoint de l’Université de New South Wales Sydney, en Australie, a mis au point une nouvelle méthode pour multiplier des nombres géants ensemble, plus efficace que la « multiplication longue » que l’on enseigne à tant de personnes dès leur plus jeune âge.
« Plus techniquement, nous avons prouvé une conjecture de 1971 de Schönhage et Strassen sur la complexité de la multiplication des entiers », déclare le professeur associé David Harvey dans la vidéo ci-dessous.
L’algorithme de Schönhage-Strassen, développé par deux mathématiciens allemands, était en fait la méthode de multiplication la plus rapide de 1971 à 2007. Bien qu’une méthode plus rapide ait été développée en 2007, elle est rarement utilisée aujourd’hui.
Schönhage et Strassen ont prédit qu’un algorithme multipliant des nombres à n chiffres en utilisant n * log(n) opérations de base devrait exister, dit Harvey. Son article est la première preuve connue qu’il existe.
Harvey choisit l’exemple de 314 multiplié par 159-une grande équation, certes, mais des équations beaucoup plus grandes sont utilisées tous les jours dans des scénarios de la vie réelle. Pour résoudre le problème, on apprend à la plupart des gens à multiplier chaque nombre individuel ensemble, puis à additionner les sommes :
9 est multiplié par 4, 1 et 3 ; puis 5 est multiplié par 4, 1 et 3, et ainsi de suite. Le résultat se termine par 9 produits chiffre par chiffre.
Cette méthode est appelée n2 ou n au carré, car il faut multiplier n par n un certain nombre de fois. Elle permet d’obtenir la bonne réponse, mais Schönhage et Strassen ont conçu une méthode plus rapide. Elle a pu aller au-delà de n2 et vers quelque chose de plus petit, mais un défi se présentait toujours sous la forme de n * log(n).
Pour certains, voir un mot au milieu d’un problème de mathématiques pourrait suffire à leur faire écarquiller les yeux comme en cours d’algèbre. Pour rappel : log est l’abréviation de logarithme, qui aide les gens à déchiffrer les exposants qui rendent les nombres carrés ou cubes ou même quelque chose de plus élevé. Donc 2⁵ est égal à 32, mais exprimé en logarithme, cela donnerait log₂(32)=5. Bien que cela puisse sembler être une mise en bouche, les logarithmes sont cruciaux lorsque les nombres deviennent beaucoup plus grands.
La méthode Schönhage-Strassen est très rapide, dit Harvey. Si un ordinateur devait utiliser la méthode des carrés enseignée à l’école sur un problème où deux nombres ont un milliard de chiffres chacun, cela prendrait des mois. Un ordinateur utilisant la méthode Schönhage-Strassen pourrait le faire en 30 secondes.
Mais si les nombres continuent à augmenter dans les trillions et au-delà, l’algorithme développé par Harvey et son collaborateur Joris van der Hoeven à l’École Polytechnique en France pourrait trouver des solutions plus rapidement que l’algorithme Schönhage-Strassen de 1971.
« Cela signifie que vous pouvez faire toutes sortes d’arithmétique plus efficacement, par exemple la division et les racines carrées », dit-il. « Vous pourriez également calculer les chiffres de pi plus efficacement qu’auparavant. Il a même des applications aux problèmes impliquant d’énormes nombres premiers.
« Cela fait presque 50 ans que l’on chasse un tel algorithme, poursuit-il. Il n’était pas acquis que quelqu’un finirait par réussir. Il aurait pu s’avérer que Schönhage et Strassen avaient tort, et qu’un tel algorithme n’est pas possible.
« Mais maintenant nous sommes mieux informés », dit-il.