Faire une multiplication... plus vite qu’à l’école !  

Nous avons tous appris à l’école primaire à faire des multiplications, en suivant une méthode qui nous paraît familière et naturelle, mais est-elle vraiment rapide ?

1. La méthode scolaire

Pour multiplier entre eux deux nombres entiers a et b, on multiplie a par chaque chiffre de b et on écrit ces produits intermédiaires en biais les uns au-dessous des autres. Ensuite, on additionne ces produits intermédiaires. Selon les pays, il existe quelques variantes dans la façon de poser les opérations, mais globalement, c'est ainsi que fonctionne la méthode scolaire de la multiplication.

 
Lorsque les nombres a et b sont grands, c’est-à-dire qu’ils comportent beaucoup de chiffres, alors cette méthode devient trop coûteuse en temps. Cela mérite réflexion.

1. Pourquoi juge-t-on cette méthode trop coûteuse en temps ?
2. Existe-t-il une autre méthode qui nous permettrait de gagner du temps ?

Ces questions sont intéressantes pour plusieurs raisons.

1. Du point de vue pratique : effectuer rapidement des calculs sur de grands nombres est utile dans beaucoup de domaines d'application de l'informatique, par exemple, pour manipuler l’information ou pour résoudre efficacement des problèmes géométriques et arithmétiques.
2. Du point de vue théorique : la méthode scolaire de la multiplication nous paraît si familière et naturelle que toute amélioration significative - et nous allons en découvrir une - constitue une véritable surprise.

Mais que veut-on dire par « la méthode scolaire est trop coûteuse en temps » ? Les informaticiens ne mesurent pas le temps de calcul en secondes (car l'année prochaine, de nouveaux ordinateurs plus rapides seront disponibles sur le marché), mais en nombre d’opérations de base qu'une méthode réalise. On peut ainsi comparer des algorithmes et pas les ordinateurs sous-jacents. Une opération de base est quelque chose qu'un ordinateur ou un homme peut faire en une seule étape. Les opérations de base dont nous avons besoin ici sont des calculs qui font intervenir des nombres à un seul chiffre en base 10, les nombres étant donc écrits avec les chiffres 0, 1, 2…, 8, 9. Plus précisément, on considère :

1. Multiplication de deux nombres à un chiffre : si nous connaissons nos tables, nous pouvons pour deux nombres x et y à un chiffre qu'on nous donne, déterminer en une seule étape les deux chiffres u et v de leur produit : x × y = 10 × u + v où u et v n'ont qu'un seul chiffre. Nous appelons cette opération multiplication élémentaire.
   Par exemple, pour les nombres x = 3 et y = 7, nous savons que x × y = 3 × 7 = 21 = 2 × 10 + 1, nous obtenons donc les chiffres du résultat u = 2 et v = 1. Pour x = 3 et y = 2, nous avons u = 0 et v = 6.
2. Addition de trois nombres à un chiffre : pour trois nombres à un chiffre x, y, z, nous pouvons trouver les deux chiffres de leur total en une étape : x + y + z = 10 × u + v où u et v n'ont qu'un seul chiffre. (Nous verrons juste après la raison pour laquelle nous voulons additionner ici trois nombres à un chiffre plutôt que deux.)
   Par exemple, pour x = 3, y = 5 et z = 4, nous avons u = 1 et v = 2, parce que 3 + 5 + 4 = 12 = 1 × 10 + 2.

En ne considérant que ces deux opérations de base, on va comparer des algorithmes de multiplication. Combien d’opérations de base la méthode scolaire de la multiplication nécessite-t-elle alors ? Avant de pouvoir répondre à cette question, nous devons d’abord évoquer l’addition de deux grands nombres, car nous en avons également besoin pour la multiplication.

L'addition de grands nombres

Combien d'opérations faut-il pour additionner deux nombres a et b ? Cela dépend naturellement de leur longueur. Supposons que a et b comportent chacun n chiffres. (Si l’un des deux nombres est plus court, nous ajoutons simplement des zéros devant celui-ci, pour obtenir deux nombres de même longueur.) Pour les additionner, nous les écrivons l’un au-dessous de l’autre et additionnons de droite à gauche les chiffres dans chaque colonne selon la méthode présentée ci-dessus. À partir du résultat 10 × u + v, nous inscrivons le chiffre v comme chiffre du résultat dans la colonne considérée et nous ajoutons le chiffre u comme troisième chiffre (retenue) à la colonne suivante. Voici un exemple avec des nombres à quatre chiffres, donc pour n = 4 :

Nous procédons ainsi de droite à gauche pour toutes les n colonnes. Finalement, nous inscrivons la dernière retenue sans autre calcul comme chiffre du résultat le plus à gauche. Nous avons alors effectué au total n opérations de base, à savoir une addition de deux ou trois chiffres pour chaque colonne.

La multiplication d'un grand nombre par un nombre à un chiffre

Revenons à la méthode scolaire de la multiplication. Les produits intermédiaires distincts, écrits chacun sur une ligne, qui apparaissent dans cette méthode, émanent de la multiplication d'un grand nombre a (c’est-à-dire le multiplicande) par un nombre à un seul chiffre y (qui fait partie du multiplicateur). Regardons à présent de plus près cette opération, en détaillant ses résultats intermédiaires un peu plus que d’habitude. Considérons de droite à gauche les chiffres de a. Nous multiplions chaque chiffre x de a par y. Nous écrivons le résultat 10 × u + v sur une nouvelle ligne, de sorte que v se trouve dans la même colonne que x, et u à sa gauche. Ensuite, nous additionnons tous ces résultats intermédiaires à deux chiffres. Cela nous fournit le produit intermédiaire, que nous écrivons habituellement directement sur une seule ligne en mémorisant les retenues. Pour le dernier produit intermédiaire de notre exemple du début, cela se présente ainsi :

Combien d’opérations de base avons-nous effectuées ? Pour chacun des n chiffres de a, nous avons effectué une multiplication élémentaire. (Dans l'exemple ci-dessus : quatre multiplications élémentaires pour les quatre chiffres du nombre 5678.) Ensuite, nous avons dû additionner les résultats intermédiaires dans n + 1 colonnes. Il n’y a qu’un seul chiffre dans la colonne la plus à droite, nous ne devons donc rien calculer dans celle-ci. Mais dans les autres n colonnes, il y a deux chiffres et éventuellement une retenue de la colonne précédente, de sorte que nous avons besoin d’effectuer une addition de ces chiffres. Cela fait donc n additions. Avec les multiplications élémentaires, cela fait au total 2 n opérations de base pour la « multiplication d’un nombre à n chiffres par un nombre à un chiffre » (ou n additions et n multiplications).

Analyse de la méthode scolaire de la multiplication

Analysons à présent le nombre d’opérations de base que nécessite la méthode scolaire de la multiplication pour deux grands nombres a et b, qui comportent n chiffres. (Comme avant, si l’un des nombres est plus court, nous écrivons suffisamment de zéros.)

Pour chaque chiffre y de b, nous devons calculer un produit intermédiaire a × y. C'est une « multiplication d’un grand nombre par un nombre à un chiffre », elle nécessite donc 2 n opérations de base, tel qu’expliqué ci-dessus. Comme b possède au total n chiffres, nous devons effectuer n × (2 × n) = 2 × n² opérations de base, pour calculer tous les produits intermédiaires.

Ensuite, nous devons additionner les produits intermédiaires, placés en biais les uns au-dessous des autres. Pour nous simplifier le calcul, pensons à inscrire des zéros aux endroits vides ; nous obtenons alors n nombres de la même longueur, que nous devons tous additionner. À cette fin, nous utilisons plusieurs fois la méthode décrite ci-dessus pour l'addition des grands nombres : nous additionnons d’abord la première ligne avec la deuxième, puis nous additionnons la troisième ligne avec ce sous-total, et ainsi de suite, jusqu'à ce que nous ayons finalement additionné tous les n produits intermédiaires. Nous avons donc besoin de n − 1 additions de grands nombres. (Dans l'exemple, avec n = 4, nous avons besoin de trois additions pour faire le total des quatre produits intermédiaires, c’est-à-dire : 5678 + 113560 = 119238, 119238 + 1703400 = 1822638 et 1822638 + 22712000 = 24534638.)

Mais combien d’opérations de base cela fait-il ? Pour être en mesure de le dire, nous devons connaître la longueur de tous les sous-totaux qui apparaissent pendant cette série d’additions. Changeons de perspective : le résultat final de notre calcul, a × b, peut au plus avoir 2 n chiffres. (Si vous ne voyez pas pourquoi, réfléchissez-y !) Au fur et à mesure que nous additionnons les lignes les unes après les autres, les nombres deviennent toujours plus grands, ils ne redeviennent jamais plus petits. Par conséquent, tous les résultats intermédiaires ne peuvent avoir qu'une longueur au plus égale à 2 n chiffres. Selon l'analyse ci-dessus relative à l'addition, cela signifie que chaque addition distincte de produits intermédiaires nécessite au plus 2 n opérations de base. Pour nos n − 1 additions de ces nombres, nous avons donc besoin au plus de (n – 1) × (2 n) = 2 n² − 2 n opérations de base.

En pratique, nous ne calculons pas ces additions intermédiaires, nous préférons additionner successivement tous les chiffres présents dans chaque colonne, en commençant par la colonne de droite, sans oublier de prendre en compte la retenue éventuelle. Mais cela revient au même pour le nombre global d'opérations élémentaires.

Conjointement avec les 2 n² opérations de base pour calculer les produits intermédiaires, cela fait donc au total au plus 4 n² − 2 n opérations de base, pour multiplier deux nombres de n chiffres avec la méthode scolaire ; dont n² sont des multiplications élémentaires. Le nombre d'additions est ici évidemment surestimé, car les premières additions sont plus petites, mais l'ordre de grandeur est respecté (qu'il y ait en réalité environ n ou n² additions).

Qu’est-ce que cela signifie concrètement ? Si nous voulons effectuer des calculs sur des nombres vraiment longs, disons avec 100 000 chiffres, nous avons alors besoin de presque 40 milliards d'opérations de base pour une seule multiplication, dont 10 milliards de multiplications élémentaires. Nous avons besoin d'environ 200 000 opérations arithmétiques en moyenne pour chaque chiffre de sortie distinct d'un tel produit. C'est un rapport manifestement très défavorable, et il devient d'autant plus défavorable que les nombres deviennent plus longs : avec 1 million de chiffres, nous avons besoin de presque 4000 milliards d'opérations de base (dont mille milliards de multiplications élémentaires), cela fait en moyenne environ 2 millions d'opérations de base pour un seul chiffre du résultat.

Considérons maintenant que la multiplication est une opération plus coûteuse que l'addition, ce qui est souvent le cas en pratique, et essayons d'améliorer le coût en temps de la multiplication.