Multiplication rapide

Pour la science a écrit:

Une méthode de multiplication plus rapide pour les grands nombres
Sean Bailly

À l'école primaire, les élèves apprennent à multiplier les nombres entiers selon une méthode qui a prouvé son efficacité depuis son invention il y a des millénaires, à l'époque des Sumériens et des égyptiens. Cependant, la procédure devient vite longue et fastidieuse quand on multiplie des nombres très grands. Existe-t-il des méthodes de multiplication plus rapides ? Joris van der Hoeven, du laboratoire d'informatique de l'école polytechnique, et David Harvey, de l'université de Nouvelle-Galles du Sud, en Australie, en ont trouvé une nouvelle.

Nous connaissons tous la méthode classique qui consiste à multiplier chaque chiffre du premier nombre par chacun du second nombre, puis additionner ces résultats intermédiaires. Si chacun des nombres contient n chiffres, le nombre total d'opérations évolue comme n^2, si bien que le nombre de calculs à effectuer devient rapidement énorme quand on multiplie des grands nombres. Pour multiplier deux nombres contenant un milliard de chiffres chacun, il faut ainsi réaliser un milliard de milliard d'opérations, ce qui prendrait un an sur les plus puissants ordinateurs personnels actuels.

Peut-on faire mieux ? En 1960, prenant acte qu'aucune méthode plus efficace n'avait été trouvée en 4 000 ans, le grand mathématicien russe Andrei Kolmogorov conjectura que cela n'était pas possible et organisa un séminaire pour le prouver deux ans plus tard. Mais l'un des participants, Anatoli Karatsuba, découvrit en une semaine une méthode plus rapide où le nombre d'opérations à réaliser est de l'ordre de n^1,58. Le chercheur avait notamment observé qu'en isolant des blocs de chiffres dans les nombres à multiplier et en réalisant des opérations d'addition et de soustraction sur ces blocs de chiffres, il était possible d'économiser certaines multiplications. Or les additions et les soustractions sont des opérations plus simples, et donc plus rapides à effectuer pour un ordinateur.

La méthode de Karatsuba a été améliorée dans les années qui ont suivies, notamment grâce à l'Américano-canadien Stephen Cook et au Russe Andrei Toom. Puis en 1971, Arnold Schönhage et Volker Strassen, de l'université de Constance, en Allemagne, ont franchi une étape décisive en utilisant une technique nommée transformée de Fourier rapide, découverte en 1965, pour accélérer la procédure de multiplication. Couramment utilisée en traitement du signal, la transformée de Fourier rapide est un algorithme qui permet de calculer la « transformée de Fourier discrète » où les données d'un signal exprimées en fonction du temps sont reformulées en fonction des fréquences. Schönhage et Strassen ont utilisé la puissance de cet algorithme pour réaliser la multiplications de deux nombres découpés en blocs contenant de l'ordre de log(n) chiffres (par exemple, le nombre 12 345 678 devient 12 | 34 | 56 | 78).

La complexité de ce nouvel algorithme (le nombre d'opérations à réaliser) évolue comme n × log(n) × log(log(n)). Il devient plus performant que les approches précédentes quand les nombres dépassent 10 000 à 40 000 chiffres. Cette méthode a de nombreuses applications, par exemple, pour calculer le nombre ? avec une grande précision ou pour chercher les nombres premiers de Mersenne (de la forme 2p-1 où p est aussi un nombre premier). Mais, en plus d'avoir découvert ce nouvel algorithme, Arnold Schönhage et Volker Strassen ont aussi conjecturé qu'il devait être possible de trouver une méthode encore plus rapide dont la complexité est de l'ordre de n × log(n).

En 2007, Martin Fürer, de l'université de l'état de Pennsylvanie, aux états-Unis, a découvert un algorithme plus rapide que celui de Schönhage et Strassen, et plusieurs autres ont suivi qui se sont rapproché progressivement de la limite conjecturée. C'est finalement Joris van der Hoeven et David Harvey qui ont mis au point un algorithme de multiplication possédant la complexité attendue de n × log(n). Leur approche s'appuie sur les stratégies précédentes - scinder les nombres à multiplier puis utiliser la transformée de Fourier rapide. L'innovation consiste à utiliser une version multidimensionnelle de la transformée. Par exemple dans l'algorithme de compression d'image en format .jpeg, la transformée utilisée est bidimensionnelle. Dans l'algorithme de Joris van der Hoeven et David Harvey, la dimension est 1729 !

D'un point de vue théorique, ce résultat est une avancée importante et vient à bout d'un problème qui tenait depuis près de 50 ans. Mais en pratique, l'algorithme n'est pas très utile - pour l'instant -, car il ne devient plus performant que les autres que pour des nombres gigantesques, contenant plus de 2^1729^12 chiffres (en base 2), soit plus de chiffres qu'il n'y a d'atomes dans l'Univers observable...

« Nous voulions d'abord expliquer le plus clairement possible l'algorithme, explique Joris van der Hoeven, sans tenter d'optimiser le seuil où il devient efficace. » Mais les chercheurs proposent déjà des pistes pour abaisser ce seuil. En outre, la performance de cet algorithme dépend aussi de l'architecture matérielle des ordinateurs : elle sera d'autant plus grande qu'une addition sera plus rapide qu'une multiplication sur l'ordinateur utilisé.

Et une question demeure : si Joris van der Hoeven et David Harvey ont effectivement montré qu'il était possible d'avoir un algorithme avec une complexité de n × log(n), il reste à prouver qu'on ne peut pas faire mieux. Un défi bien plus ardu attend les mathématiciens !