Les enfants apprennent leurs tables de multiplication à l’école. Mémorisez-les. Bonne chance avec les nombres à trois chiffres. C’est là que les algorithmes entrent en jeu. Vous empilez les chiffres. Multipliez ligne par ligne. Pendant des milliers d’années, nous avons pensé que c’était le mieux que nous puissions faire. C’est lent. Brutalement lent pour le Big Data. Puis, en 1960, un jeune de 23 ans a tout changé. Le mystère de la vitesse de multiplication reste grand ouvert.
Pourquoi c’est important
La multiplication n’est pas seulement un devoir. Il gère Internet. Cryptage, IA, traitement audio. Tout cela repose sur la multiplication. Multiplication lourde. Lorsque vous multipliez des nombres énormes des millions de fois par seconde, chaque étape compte. Un léger gain d’efficacité permet d’économiser des milliards.
Regardez la méthode de l’école primaire. Deux chiffres signifient quatre multiplications à un chiffre. Trois chiffres ? Neuf. Il évolue quadratiquement. Doublez la longueur, quadruplez le travail. Doublez-le encore, le travail augmente de seize fois. Les informaticiens ignorent les secondes. Le matériel accélère de toute façon. Ils comptent les pas. Nous l’appelons la notation Big O. L’école primaire est O(n^2). Quadratique. Si votre nombre augmente de 1 000, le travail explose d’un million.
La charge de travail évolue avec le carré du nombre de chiffres.
Depuis l’Antiquité, les mathématiciens pensaient que cette limite quadratique était une loi de la nature. Andreï Kolmogorov, une légende soviétique, y a misé sa réputation lors d’une conférence en 1960. Il a déclaré aux étudiants de l’Université d’État de Moscou : « Cela prend O(n^2). » C’est une conjecture formelle. Un défi. Attendez que quelqu’un le prouve ou le casse.
Cela a pris une semaine. Anatoly Karatsuba était assis dans le public. Il avait 23 ans. Il est revenu avec la preuve que Kolmogorov avait tort. Le professeur était abasourdi. Kolmogorov a en fait écrit lui-même l’article pour une revue prestigieuse, mais il y a apposé le nom de Karatsuba. L’enfant ne le savait pas jusqu’à ce que les réimpressions arrivent par la poste.
L’astuce
Karatsuba a réalisé quelque chose de simple mais profond. Les multiplications coûtent cher. Les ajouts sont bon marché. Pourquoi ne pas les échanger ?
Prenez 12 x 34.
Divisez-le.
12 est 10 + 2.
34 est 30 + 4.
Traditionnellement, vous effectuez quatre multiplications :
1×3
1×4
2×3
2×4
Karatsuba a trouvé un moyen de le faire à trois.
Calculez la première partie : 1×3 = 3.
Calculez la dernière partie : 2×4 = 8.
Maintenant le milieu. Normalement, vous feriez (1×4) + (2×3). Deux multiplie. Additionnez plutôt les premiers nombres : 1+2=3. Additionnez les derniers nombres : 3+4=7. Multipliez ces sommes : 3×7=21. Soustrayez les parties que vous connaissez déjà. 21 – 3 – 8 = 10.
Boum. Vous avez obtenu le moyen terme avec une multiplication supplémentaire.
Est-ce que ça vaut le coup ?
Pas pour les petits nombres. Les frais généraux liés au fractionnement et à l’ajout vous coûtent cher.
Mais pour 1 234 x 5 678 ? Divisez-le en deux. Récursivité. Divisez ces moitiés. Faites-le à nouveau. L’épargne composée.
L’algorithme tombe à environ O(n^1,585).
Les nombres à mille chiffres nécessitaient autrefois un million de mults à un chiffre. Désormais, cela prend moins de 57 00 pas. Massif.
Ce n’est pas seulement de la théorie. C’est en Python.
Python utilise les mathématiques scolaires standard pour les petites entrées. Assez lisse.
Une fois que vous avez atteint environ 63 chiffres décimaux (selon la base de la machine), Python actionne un interrupteur. Karatsuba prend le relais. Vous ne voyez pas cela se produire. Mais c’est là. Gérer votre cryptographie.
Algorithmes Galactiques
La course s’est poursuivie pendant des décennies. Pouvons-nous aller plus vite ?
2019 a apporté le dernier choc. David Harvey et Joris van Der Hoeven ont publié un algorithme qui bat Karatsuba d’un mile.
O (n journal n).
Relisez-le.
Les logarithmes croissent incroyablement lentement.
n log n est à peine plus grand que n.
Fondamentalement, multiplier deux nombres massifs prend désormais à peu près le même temps que leur lecture.
C’est stupéfiant. Le plafond théorique semble avoir été touché.
Ou peut-être pas.
Voici le piège.
Cela ne fonctionne pas pour les chiffres qui nous intéressent.
L’algorithme de Harvey et Van Der Hoeven ne devient plus rapide que celui de Karatsuba que lorsque les chiffres deviennent vraiment grands. Pas grand “numéro de carte de crédit”. Grand galactique.
En informatique, nous avons un terme pour cela : algorithme galactique.
Belle théorie. Zéro utilisation pratique. Les chiffres requis sont plus importants que la plupart des transactions numériques de l’histoire de l’humanité réunies.
Nous sommes coincés au milieu.
Utiliser des astuces des années 1960 pour la plupart de nos tâches informatiques quotidiennes.
Porter des costumes du 21e siècle en plus des mathématiques du 20e siècle.
Utilisons-nous réellement O(n log n) dans le monde réel ?
Peut-être que lorsque nous traitons des données, la taille des galaxies est déterminée.
En attendant, nous attendons.
Pour le prochain tour.
Ou un meilleur matériel pour cacher notre paresse.
La réponse pourrait encore être quadratique.
Cela pourrait être linéaire.
Nous ne le savons pas encore.
