Si vous pensiez que les tables de multiplication à l'école étaient difficiles, imaginez multiplier des nombres par des milliards de chiffres. Crédit :Shutterstock/Nina Buday
La multiplication de deux nombres est facile, droit?
À l'école primaire, nous apprenons à faire de longues multiplications comme ceci :
Des méthodes similaires à celles-ci remontent à des milliers d'années, du moins aux anciens Sumériens et Egyptiens.
Mais est-ce vraiment la meilleure façon de multiplier deux grands nombres ensemble ?
En longue multiplication, nous devons multiplier chaque chiffre du premier nombre par chaque chiffre du deuxième nombre. Si les deux nombres ont chacun N chiffres, c'est N 2 (ou N X N ) multiplications au total. Dans l'exemple ci-dessus, N est 3, et nous devions faire 3 2 =9 multiplications.
Vers 1956, le célèbre mathématicien soviétique Andrey Kolmogorov a conjecturé que c'est le meilleur moyen possible multiplier deux nombres ensemble.
En d'autres termes, peu importe comment vous organisez vos calculs, la quantité de travail que vous avez à faire sera proportionnelle à au moins N 2 . Deux fois plus de chiffres signifie quatre fois plus de travail.
Kolmogorov a estimé que si un raccourci était possible, il aurait sûrement déjà été découvert. Après tout, les gens multiplient les nombres depuis des milliers d'années.
C'est un superbe exemple de l'erreur logique connue sous le nom de « l'argument de l'ignorance ».
Un moyen plus rapide
Quelques années plus tard, La conjecture de Kolmogorov s'est avérée spectaculairement fausse.
En 1960, Anatoli Karatsuba, un étudiant en mathématiques de 23 ans en Russie, découvert une astuce algébrique sournoise qui réduit le nombre de multiplications nécessaires.
Par exemple, multiplier des nombres à quatre chiffres, au lieu d'avoir besoin de 4 2 =16 multiplications, La méthode de Karatsuba s'en tire avec seulement neuf. En utilisant sa méthode, deux fois plus de chiffres signifie seulement Trois fois plus de travail.
Cela s'accumule à un avantage impressionnant à mesure que les chiffres augmentent. Pour les nombres à mille chiffres, La méthode de Karatsuba nécessite environ 17 fois moins de multiplications qu'une longue multiplication.
Mais pourquoi diable voudrait-on multiplier ces grands nombres ensemble ?
En réalité, il y a énormément d'applications. L'un des plus visibles et économiquement significatifs est la cryptographie.
Les grands nombres dans la vraie vie
Chaque fois que vous vous engagez dans une communication cryptée sur Internet, par exemple, accéder à votre site Web bancaire ou effectuer une recherche sur le Web - votre appareil effectue un nombre époustouflant de multiplications, impliquant des nombres avec des centaines voire des milliers de chiffres.
Très probablement, votre appareil utilise l'astuce de Karatsuba pour cette arithmétique. Tout cela fait partie de l'incroyable écosystème logiciel qui permet à nos pages Web de se charger aussi rapidement que possible.
Le long chemin vers la multiplication. Crédit :David Harvey
Pour certaines applications plus ésotériques, les mathématiciens doivent faire face à des nombres encore plus grands, avec des millions, des milliards voire des milliards de chiffres. Pour des nombres aussi énormes, même l'algorithme de Karatsuba est trop lent.
Une véritable percée intervient en 1971 avec les travaux des mathématiciens allemands Arnold Schönhage et Volker Strassen. Ils ont expliqué comment utiliser la transformée de Fourier rapide (FFT) récemment publiée pour multiplier efficacement des nombres énormes. Leur méthode est couramment utilisée par les mathématiciens aujourd'hui pour manipuler des nombres dans les milliards de chiffres.
La FFT est l'un des algorithmes les plus importants du 20ème siècle. Une application familière dans la vie quotidienne est l'audio numérique :chaque fois que vous écoutez des MP3, services de streaming musical ou radio numérique, Les FFT gèrent le décodage audio dans les coulisses.
Un moyen encore plus rapide ?
Dans leur article de 1971, Schönhage et Strassen ont également fait une conjecture frappante. Expliquer, Je vais devoir être un peu technique pendant un moment.
La première moitié de leur conjecture est qu'il devrait être possible de multiplier N -chiffres utilisant un nombre d'opérations de base proportionnel à au plus N Journal ( N ) (c'est N fois le logarithme népérien de N ).
Leur propre algorithme n'a pas tout à fait atteint cet objectif ; ils étaient trop lents d'un facteur de log (log N ) (le logarithme du logarithme de N ). Néanmoins, leur intuition les a amenés à soupçonner qu'il leur manquait quelque chose, et cela N Journal ( N ) devrait être réalisable.
Au cours des décennies qui ont suivi 1971, quelques chercheurs ont trouvé des améliorations à l'algorithme de Schönhage et Strassen. Notamment, un algorithme conçu par Martin Fürer en 2007 s'est considérablement rapproché de l'insaisissable N Journal ( N ).
La deuxième partie (et beaucoup plus difficile) de leur conjecture est que N Journal ( N ) devrait être la limite de vitesse fondamentale - qu'aucun algorithme de multiplication possible ne pourrait faire mieux que cela.
Semble familier?
Avons-nous atteint la limite ?
Il y a quelques semaines, Joris van der Hoeven et moi avons publié un article de recherche décrivant un nouvel algorithme de multiplication qui atteint enfin le N Journal ( N ) Saint Graal, réglant ainsi la partie « facile » de la conjecture de Schönhage-Strassen.
Le document n'a pas encore été évalué par des pairs, donc une certaine prudence s'impose. C'est une pratique courante en mathématiques de diffuser les résultats de la recherche avant qu'ils n'aient fait l'objet d'un examen par les pairs.
Au lieu d'utiliser des FFT unidimensionnelles - la base de tous les travaux sur ce problème depuis 1971 - notre algorithme repose sur multidimensionnel FFT. Ces gadgets n'ont rien de nouveau :le format d'image JPEG largement utilisé dépend des FFT en 2 dimensions, et les FFT tridimensionnelles ont de nombreuses applications en physique et en ingénierie.
Dans notre papier, nous utilisons des FFT avec 1, 729 dimensions. C'est difficile à visualiser, mais mathématiquement pas plus gênant que le cas bidimensionnel.
Vraiment, de très gros chiffres
Le nouvel algorithme n'est pas vraiment pratique dans sa forme actuelle, parce que la preuve donnée dans notre article ne fonctionne que pour des nombres ridiculement grands. Même si chaque chiffre était écrit sur un atome d'hydrogène, il n'y aurait pas assez de place disponible dans l'univers observable pour les écrire.
D'autre part, nous espérons qu'avec d'autres améliorations, l'algorithme pourrait devenir pratique pour les nombres avec seulement des milliards ou des milliards de chiffres. Si c'est le cas, il pourrait bien devenir un outil indispensable dans l'arsenal du mathématicien computationnel.
Si la conjecture complète de Schönhage-Strassen est correcte, puis d'un point de vue théorique, le nouvel algorithme est la fin du chemin – il n'est pas possible de faire mieux.
Personnellement, Je serais très surpris si la conjecture s'avérait fausse. Mais il ne faut pas oublier ce qui est arrivé à Kolmogorov. Les mathématiques peuvent parfois réserver des surprises.
Cet article est republié à partir de The Conversation sous une licence Creative Commons. Lire l'article original. 
