Les mathématiciens ont découvert le moyen idéal pour multiplier les nombres

En divisant les grands nombres en petits nombres, les chercheurs ont dépassé la limite fondamentale de vitesse mathématique

Il y a quatre mille ans, les habitants de Babylonie ont inventé la multiplication. Et en mars de cette année, les mathématiciens l'ont amélioré.

Le 18 mars 2019, deux chercheurs ont décrit la méthode connue la plus rapide pour multiplier deux très grands nombres. Le travail marque l'aboutissement d'une recherche de longue date pour la procédure la plus efficace pour effectuer l'une des opérations de base des mathématiques.

«Tout le monde pense que la méthode de multiplication qu'ils enseignaient à l'école est la meilleure, mais en fait, une recherche active est en cours dans ce domaine», explique Joris van der Hoeven , mathématicien au Centre national de la recherche scientifique, l'un des co-auteurs de l'ouvrage.

La complexité de nombreux problèmes de calcul, du comptage de nouveaux chiffres du nombre π à la recherche de grands nombres premiers, se réduit au taux de multiplication. Van der Hoeven décrit leur résultat comme une affectation d'une sorte de limite de vitesse mathématique pour résoudre de nombreux autres problèmes.

"En physique, il existe des constantes importantes telles que la vitesse de la lumière qui vous permettent de décrire toutes sortes de phénomènes", a déclaré van der Hoeven. "Si vous voulez savoir à quelle vitesse les ordinateurs peuvent résoudre certains problèmes mathématiques, alors la multiplication des entiers se présente sous la forme d'un bloc de construction de base, par rapport auquel vous pouvez exprimer une telle vitesse."

Presque tout le monde apprend à multiplier les nombres de la même manière. Nous écrivons les nombres dans une colonne, multiplions le nombre supérieur par chaque chiffre du bas (en tenant compte des chiffres) et ajoutons le résultat. Lorsque vous multipliez deux nombres à deux chiffres, vous devez effectuer quatre multiplications plus petites pour obtenir le résultat final.

La méthode scolaire de « transfert » nécessite n ² étapes, où n est le nombre de chiffres dans chacun des nombres multipliés. Les calculs avec des nombres à trois chiffres nécessitent neuf multiplications et avec des nombres à un chiffre, 10 000.

La méthode de transfert fonctionne bien avec des nombres composés de plusieurs chiffres, mais elle commence à glisser lors de la multiplication de nombres composés de millions ou de milliards de chiffres (ce que font les ordinateurs lors du calcul précis de π ou lors de la recherche de grands nombres premiers dans le monde entier ). Pour multiplier deux nombres avec un milliard de chiffres, vous devrez produire un milliard au carré, ou 10 ¹⁸ , multiplications - cela prendra environ 30 ans pour un ordinateur moderne.

Pendant plusieurs millénaires, on a cru que les chiffres ne pouvaient pas être multipliés plus rapidement. Puis en 1960, le mathématicien soviétique et russe Anatoly Alekseevich Karatsuba, âgé de 23 ans, a assisté à un séminaire dirigé par Andrei Nikolayevich Kolmogorov , un mathématicien soviétique, l'un des plus grands mathématiciens du XXe siècle. Kolmogorov a déclaré qu'il n'y a pas de méthode généralisée de multiplication nécessitant moins de n ² opérations. Karatsuba a décidé qu'il existait une telle méthode - et après une semaine de recherches, il l'a découverte.


Anatoly Alekseevich Karatsuba

La multiplication de Karatsuba consiste à décomposer les chiffres du nombre et à répéter leur combinaison d'une manière nouvelle, ce qui permet au lieu d'un grand nombre de multiplications d'effectuer moins d'additions et de soustractions. La méthode fait gagner du temps, car l'addition ne prend que 2n étapes au lieu de n ² .


La méthode de multiplication 25x63 traditionnelle nécessite quatre multiplications à un chiffre et plusieurs ajouts


La multiplication de Karatsuba 25x63 nécessite trois multiplications par un seul numéro et plusieurs additions et soustractions.
a) casser les chiffres
b) multiplier les dizaines
c) multiplier les unités
d) additionner les chiffres
e) multiplier ces montants
f) considérer e - b - c
g) recueillir le total de b, c et f

À mesure que le nombre de caractères augmente, la méthode Karatsuba peut être utilisée récursivement.


La méthode traditionnelle de multiplication de 2531x1467 nécessite 16 multiplications par un seul chiffre.


La multiplication de Karatsuba 2531x1467 nécessite 9 multiplications.

"L'ajout à l'école a lieu un an plus tôt, car il est beaucoup plus simple, il fonctionne en temps linéaire, avec la vitesse de lecture des nombres de gauche à droite", a déclaré Martin Fuhrer , mathématicien de la Pennsylvania State University, qui a créé l'algorithme de multiplication le plus rapide en 2007.

Lorsqu'il s'agit de grands nombres, la multiplication de Karatsuba peut être répétée récursivement, divisant les nombres originaux en presque autant de parties qu'il y a de signes en eux. Et avec chaque partition, vous changez la multiplication, qui nécessite de nombreuses étapes, en addition et soustraction, qui nécessitent beaucoup moins d'étapes.

"Plusieurs multiplications peuvent être transformées en ajouts, étant donné que les ordinateurs pourront le faire plus rapidement", a déclaré David Harvey , mathématicien à l'Université de Nouvelle-Galles du Sud et co-auteur du nouveau travail.

La méthode de Karatsuba a permis de multiplier les nombres en utilisant seulement n ^1,58 multiplications par un seul chiffre. Puis, en 1971, Arnold Schönhage et Volker Strassen ont publié une méthode pour multiplier les grands nombres par n × log n × log (log n) petites multiplications. Pour multiplier deux nombres à partir d'un milliard de caractères, chaque méthode Karatsuba nécessitera 165 billions de pas.


Joris van der Hoeven, mathématicien au Centre national de la recherche scientifique

La méthode Schönhage-Strassen est utilisée par les ordinateurs pour multiplier les grands nombres et a conduit à deux autres conséquences importantes. Tout d'abord, il a introduit une technique du domaine du traitement du signal appelée Fast Fourier Transform . Depuis lors, cette technique est à la base de tous les algorithmes de multiplication rapide.

Deuxièmement, dans le même travail, Schönhage et Strassen ont suggéré la possibilité d'un algorithme encore plus rapide - une méthode ne nécessitant que n × log n multiplications par un signe - et qu'un tel algorithme serait le plus rapide possible. Cette hypothèse était basée sur le sentiment que pour une opération aussi fondamentale que la multiplication, la restriction des opérations devrait être écrite d'une manière plus élégante que n × log n × log (log n).

"La plupart des gens ont convenu que la multiplication est une opération de base si importante que d'un point de vue purement esthétique, elle a besoin d'une belle restriction de complexité", a déclaré le Führer. "Par expérience, nous savons que les mathématiques des choses de base finissent toujours par être élégantes."

La restriction maladroite de Schönhage et Strassen, n × log n × log (log n), a duré 36 ans. En 2007, le Führer a battu ce record, et tout s'est passé. Au cours de la dernière décennie, les mathématiciens ont trouvé des algorithmes de multiplication de plus en plus rapides, chacun progressant progressivement jusqu'à la marque n × log n, sans y parvenir tout à fait. Puis en mars de cette année, Harvey et van der Hoeven l'ont atteint.

Leur méthode est une amélioration de l'excellent travail accompli avant eux. Il décompose les nombres en signes, utilise une version améliorée de la transformée de Fourier rapide et profite d'autres percées réalisées au cours des 40 dernières années. "Nous utilisons la transformée de Fourier rapide beaucoup plus grossièrement, nous l'utilisons plusieurs fois, pas seulement une, et nous remplaçons encore plus de multiplications par l'addition et la soustraction", a déclaré van der Hoeven.

L'algorithme de Harvey et van der Hooven prouve que la multiplication peut se faire en n × log n étapes. Cependant, il ne prouve pas l'absence d'une méthode plus rapide. Il sera beaucoup plus difficile d'établir que leur approche est aussi rapide que possible. Fin février, une équipe d'informaticiens de l'Université d'Aarhus a publié un article affirmant que si l'un des théorèmes non prouvés s'avérait vrai, cette méthode serait en effet le moyen le plus rapide de se multiplier.

Et bien qu'en théorie ce nouvel algorithme soit très important, en pratique il ne changera pas grand-chose, car il ne bat que légèrement les algorithmes déjà utilisés. "Tout ce que nous pouvons espérer, c'est une triple accélération", a déclaré van der Hoeven. "Rien au-delà."

De plus, les circuits d'équipement informatique ont changé. Il y a vingt ans, les ordinateurs effectuaient l'addition beaucoup plus rapidement que la multiplication. L'écart dans les taux de multiplication et d'addition a depuis sérieusement diminué, ce qui fait que, sur certaines puces, la multiplication peut même dépasser l'addition. En utilisant certains types d'équipements, "vous pouvez accélérer l'ajout en forçant l'ordinateur à multiplier les nombres, et c'est une sorte de folie", a déclaré Harvey.

L'équipement change avec le temps, mais les meilleurs algorithmes de sa catégorie durent toujours. Peu importe à quoi ressembleront les ordinateurs à l'avenir, l'algorithme Harvey et van der Hooven sera toujours le moyen le plus efficace de multiplier les nombres.