Algorithme de multiplication d'entiers 📖 Wikipedia

Ce type de multiplication n'utilise que des additions et des multiplications ou des divisions par 2. Elle ne nécessite pas de connaître de table de multiplication (autre que la multiplication par 2).

• Technique de la multiplication dans l'Égypte antique
• (variante) Technique de multiplication dite russe

Ce type de multiplication utilise la décomposition décimale des nombres et nécessite de multiplier chaque chiffre du premier nombre par chaque chiffre du second. Elle nécessite de connaître les tables de multiplication d'un chiffre par un autre. Cependant, plusieurs types de disposition ont été adoptés au cours des temps.

• Technique de la multiplication en Chine antique
• Technique de la multiplication par glissement
• Technique de la multiplication par jalousies
• Technique graphique de multiplication par décompte de points d'intersection (ne nécessite pas de connaître la table de multiplication).

Si un système de notation positionnelle est utilisé, une façon naturelle de multiplier des nombres est enseignée dans les écoles sous le nom de multiplication longue ou multiplication à la main, parfois appelée multiplication scolaire ou algorithme standard : multiplier le multiplicande par chaque chiffre du multiplicateur et ensuite additionner ensemble tous les résultats partiels correctement décalés. Elle nécessite de mémoriser la table de multiplication d'un chiffre par un autre.

C'est l'algorithme habituel pour multiplier à la main de grands nombres en base 10. Une personne faisant une multiplication longue sur une feuille de papier écrira tous les produits puis les additionnera ; un utilisateur d'abaque fera la somme des produits partiels dès qu'ils auront été calculés.

Cet exemple utilise la multiplication longue pour multiplier 23 958 233 (multiplicande) par 5 830 (multiplicateur) et fournit comme résultat 139 676 498 390 (produit).

      23958233
×         5830
———————————————
      00000000 ( =  23 958 233 ×     0)
     71874699  ( =  23 958 233 ×    30)
   191665864   ( =  23 958 233 ×   800)
+ 119791165    ( =  23 958 233 × 5 000)
———————————————
  139676498390 ( = 139 676 498 390)

Les méthodes décrites dans le précédent paragraphe nécessitent pour la plupart de multiplier chaque chiffre du multiplicateur par chaque chiffre du multiplicande. Si ces deux nombres ont ${\displaystyle n}$  chiffres, cela exige ${\displaystyle n^{2}}$  produits : on dit que le calcul a une complexité en temps quadratique, ou en ${\displaystyle {\mathcal {O}}(n^{2})}$ .

L'apparition des ordinateurs a permis et exigé la mise au point d'algorithmes plus rapides pour les grands nombres, les premiers trouvés ayant une complexité en temps de la forme ${\displaystyle O(n^{1+a})}$ , où ${\displaystyle a}$  est un réel positif strictement inférieur à 1. Arnold Schönhage et Volker Strassen ont conjecturé en 1971 que le produit de deux entiers a une complexité en ${\displaystyle O(n\log n)}$ , c'est-à-dire qu'il existe un algorithme ayant cette complexité en temps, et qu'aucun n'en a de meilleure^[1],[2]. La meilleure complexité actuelle est depuis 2019 en ${\displaystyle O(n\log n)}$  mais n'est pas utilisable en pratique car elle n'est atteinte que pour des nombres extrêmement grands, supérieurs à ${\displaystyle 2^{1729^{12}}}$  dans la publication d'origine^[1],[2]. Aucun algorithme présentant une meilleure complexité que celle conjecturée n'a été trouvé et la conjecture de Schönhage et Strassen est toujours supposée valide en 2019^[1]. Tous les algorithmes ci-dessous ont été mis au point après 1960.

• Algorithme de Karatsuba : complexité en ${\displaystyle {\mathcal {O}}(n^{\log _{2}(3)})}$  soit approximativement en ${\displaystyle {\mathcal {O}}(n^{1,585})}$  ; conçu en 1962^[3], c'est le premier algorithme ayant une complexité sub-quadratique^[1] ;
• Algorithme Toom-Cook ou "Toom3" : complexité en ${\displaystyle {\mathcal {O}}(n^{\log _{3}(5)})}$  soit approximativement en ${\displaystyle {\mathcal {O}}(n^{1,465})}$  ;
• Algorithme de Schönhage-Strassen, méthode utilisant la transformation de Fourier rapide : complexité en ${\displaystyle {\mathcal {O}}(n\cdot \log n\cdot \log \log n)}$ , conçu en 1971^[1] ;
• Algorithme de Fürer : complexité en ${\displaystyle {\mathcal {O}}(n\log nK^{O(\log ^{*}n)})}$ , où ${\displaystyle \log ^{*}n}$  désigne le logarithme itéré et ${\displaystyle K}$  un nombre strictement supérieur à 1^[1], conçu en 2007 ;
• Algorithme de Harvey et van der Hoeven : en mars 2019, David Harvey et Joris van der Hoeven annoncent un algorithme de multiplication en ${\displaystyle {\mathcal {O}}(n\log n)}$ ^[4],[5]. L'algorithme est publié dans les Annals of Mathematics en 2021^[6],[1]. Schönhage et Strassen ont prédit que n log(n) est le meilleur résultat possible, et Harvey en conclut : « ...notre travail devrait être la fin de la route pour ce problème, bien que nous ne sachions pas encore comment le prouver rigoureusement »^[7].

La plupart des processeurs récents implémentent les multiplications sous forme de circuits électroniques, mais qui ne gèrent que des entiers de taille limitée. On appelle de tels circuits des multiplieurs.

• Multiplication de matrices

• Preuve par neuf
• Calcul mental

•   Arithmétique et théorie des nombres
•   Portail de l'informatique théorique