On a tous appris à multiplier ensemble deux nombres entiers. Une partie de la communauté mathématique a même cru, au XX^e siècle, que la méthode enseignée dans nos écoles était la meilleure méthode qui puisse exister pour ce faire. Et s’il en était autrement ?

Si on vous demande de multiplier
\[45 758 780 \times 96 803 528 \]
sans calculatrice, comment feriez-vous ? Il y a fort à parier que vous écririez les nombres un au-dessus de l’autre, puis multiplieriez le nombre du haut par la dernière décimale du nombre du bas (les unités), un chiffre à la fois et à partir de la droite.

Après avoir obtenu le produit du nombre du haut par l’unité du bas, vous feriez des calculs similaires avec les dizaines du bas, avant de procéder avec les centaines, etc. Vous vous rendriez facilement compte que le processus est bien long…

Avec cette méthode, on doit multiplier chaque chiffre du premier nombre avec chaque chiffre du deuxième nombre. En cours de route, si on multiplie deux nombres de $n$ chiffres ensemble, ça revient à faire $n^2$ multiplications élémentaires – c’est-à-dire des multiplications de nombres entiers entre 0 et 9.

Ainsi, si on veut multiplier deux nombres de 4 chiffres chacun, ça fait 16 multiplications élémentaires. Si on désire multiplier deux nombres de 8 chiffres chacun, on doit exécuter 64 multiplications élémentaires, ce qui est beaucoup !

Bien que l’on ait souhaité faire une seule multiplication, on finit par faire $n^2$ multiplications élémentaires, ainsi que quelques additions. On verra plus tard que les additions sont beaucoup plus faciles que les multiplications.

Peut-on faire mieux ?

Pourrait-on faire moins de multiplications élémentaires ? Pourrait-on même imaginer en faire significativement moins ?

Ce sont des questions que posa, en 1960, le mathématicien Andreï Kolmogorov à ses étudiants. Kolmogorov croyait profondément que c’était impossible, notamment parce qu’une façon aussi efficace de multiplier n’avait toujours pas été développée, même après des milliers d’années à multiplier. Il en était si persuadé qu’il organisa un séminaire afin de prouver sa conjecture. Après exactement une semaine, Anatoli Karatsuba, âgé de seulement 23 ans, décrivit un algorithme qui requiert beaucoup moins de multiplications élémentaires que l’algorithme qu’on a tous appris à l’école. C’était suffisant pour que Kolmogorov partage la bonne nouvelle et décide que le séminaire était terminé.

Alors, comment fait-on des multiplications plus efficacement ?

Le principe de l’algorithme de Karatsuba s’appelle « diviser pour régnernbsp;». Ça veut dire qu’on divise le problème initial (la multiplication de deux grands nombres), en plusieurs petits problèmes. Par exemple, au lieu de multiplier deux nombres à $n$ chiffres ensemble, on pourrait faire quelques multiplications de nombres à $n/2$ chiffres. Pour obtenir un gain d’efficacité, il y a deux conditions :

• Le problème original est un processus relativement long. Mathématiquement, on dira que « sa complexité n’est pas linéaire ». C’est le cas de la multiplication, étant donné que faire deux multiplications de deux nombres de $n/2$ chiffres requiert moins de multiplications élémentaires que de faire une seule multiplication de nombres de n chiffres.
• Le nombre de petits problèmes doit être petit. Créer trop de petits problèmes pourrait même nous faire perdre de l’efficacité par rapport au problème original.

Dans le cas de la méthode de Karatsuba, on divise la multiplication de deux nombres de $n$ chiffres en trois multiplications de $n/2$ chiffres. On doit aussi faire des additions et des soustractions pour recombiner les résultats, mais celles-ci nécessitent peu d’opérations en comparaison (voir encadré).

Par exemple, pour multiplier ensemble deux nombres de huit chiffres, on doit les séparer en nombres de quatre chiffres. Pour chaque nombre de huit chiffres, on crée deux nombres de quatre chiffres: celui de gauche et celui de droite. Ensuite, on multiplie ensemble les nombres de gauche et ceux de droite. Ainsi, au lieu de faire 45 758 780 × 96 803 528, on fait 4 575 x 9 680 et 8 780 x 3 528. On doit faire une multiplication supplémentaire pour combiner les deux. En multipliant ensemble des nombres de quatre chiffres, même trois fois, on sauve du temps. Là où le gain de temps est considérable, c’est qu’on applique aussi la même méthode pour faire les « plus petites » multiplications, c’est-à-dire celles avec moins de décimales.

Ceci permet un gain de temps considérable, comme expliqué plus bas.

Comment ça marche ?

Disons que l’on souhaite multiplier deux nombres, $a$ et $b$, qui ont chacun un nombre pair de chiffres, par exemple $2k$ chiffres¹. On peut réécrire les nombres $a$ et $b$ comme

\[a = a1_ × 10^k + a_2 \text{ et } b = b_1 × 10^k + b_2, \]

dans lesquels $a_1 , a_2 , b_1$ et $b_2$ sont des nombres à k chiffres. Utiliser la distributivité pour obtenir le produit $a \times b$ nous donne

Même si les multiplications par des puissances de 10 sont en quelque sorte gratuites (on « ajoute des 0 »), on n’atteint pas le gain d’efficacité promis. Outre les multiplications par des puissances de 10, on fait quatre multiplications de nombre à $k$ chiffres… comme dans la méthode initiale !

En fait, l’algorithme de Karatsuba utilise un truc supplémentaire : Il suffit de remarquer qu’on peut, au lieu de faire $(a_1 \times b_2 + b_1 \times a_2)$ dans l’exemple ci-dessus, écrire
\[(a_1 + a_2) \times (b_1 + b_2) – a_1 \times b_1 – a_2 \times b_2 \]
Si cela semble encore plus compliqué qu’au départ, on réduit en fait le nombre de multiplications à faire, puisque
\[a_1 \times b_1 \text{ et } a_2 \times b_2\]
sont des expressions qu’on doit déjà calculer. Ainsi, le nombre de multiplications de nombres à k chiffres passe de quatre à trois. Certes, on doit faire des additions, mais celles-ci sont beaucoup moins coûteuses (voir encadré).

Pour multiplier deux nombres de $2k$ chiffres chacun, on devait faire $4k^2$ multiplications élémentaires avec la méthode apprise à l’école. Maintenant, on doit faire trois fois plus de multiplications élémentaires qu’il en faut pour multiplier des nombres à $k$ chiffres. Si $T$ est une fonction qui compte le nombre de multiplications élémentaires effectuées pour multiplier deux nombres à $n$ chiffres², on a alors la récurrence
\[T(n) = 3T(n/2), \text{ quand } n > 1, \text{ et } T(1) = 1.\]
Celle-ci se résout par l’expression
\[T (n) = n^{\log_2 (3)} \approx n^{1,58}.\]

Une belle amélioration sur la méthode apprise à l’école, qui nous faisait faire $n^2$ multiplications élémentaires.

Pour avoir une idée du gain d’efficacité, on peut regarder le tableau ci-contre.

Y a-t-il plus efficace ?

Il y a une soixantaine d’années, la découverte de la méthode de Karatsuba a permis l’ouverture d’un tout nouveau champ de recherche. Depuis, d’autres méthodes encore plus efficaces ont été mises au jour. Certes, plusieurs d’entre elles sont difficiles à mémoriser, ce qui les rend peu réalistes pour un algorithme qui serait enseigné à l’école. En revanche, elles s’avèrent de formidables outils pour les ordinateurs qui doivent accomplir de nombreuses multiplications, ne serait-ce que pour crypter vos informations sensibles. Cela dit, si je vous demande de multiplier de grands nombres, peut-être gagneriez-vous à aller chercher la calculatrice !

Pour en s\(\alpha\)voir plus !

• KARATSUBA, Anatolii. « The complexity of computations », dans Proceedings of the Steklov Institute of Mathematics, n° 211, pages 169–183, janvier 1995. L’auteur décrit l’histoire de la découverte de son algorithme.
• HARTNETT, Kevin. « Mathematicians Discover the Perfect Way to Multiply », dans Quanta Magazine, 11 avril 2019.
  En ligne (https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/).
  L’article décrit les progrès récents dans la quête de l’algorithme parfait pour la multiplication.

PDF