Algorithme de multiplication

méthode permettant de multiplier deux nombres. Selon la taille des nombres, certains algorithmes sont plus efficaces que d'autres. De nombreux algorithmes sont connus et le sujet a fait l'objet de nombreuses recherches.

La méthode la plus ancienne et la plus simple, connue depuis l'Antiquité sous le nom de multiplication posée ou multiplication classique , consiste à multiplier chaque chiffre du premier nombre par chaque chiffre du second, puis à additionner les résultats. Sa complexité temporelle est de O (n ), où n est le nombre de chiffres. Effectuée manuellement, cette opération peut également être appelée multiplication par grille ou multiplication en treillis . En informatique, on parle souvent de « décalage et addition », car seuls des décalages de bits et des additions sont nécessaires.

En 1960, Anatoly Karatsuba découvrit la multiplication de Karatsuba , déclenchant une vague de recherches sur les algorithmes de multiplication rapide. Cette méthode utilise trois multiplications au lieu de quatre pour multiplier deux nombres à deux chiffres. (Une variante permet également de multiplier rapidement des nombres complexes .) Appliquée récursivement , sa complexité temporelle est de O ( n^2). Décomposer un nombre en plus de deux parties donne lieu à la multiplication de Toom-Cook ; par exemple, avec trois parties, on obtient l' algorithme de Toom-3 . Utiliser un grand nombre de parties permet de fixer l'exposant arbitrairement près de 1, mais le facteur constant augmente également, ce qui rend cette méthode impraticable.

En 1968, l' algorithme de Schönhage-Strassen , qui utilise une transformée de Fourier sur un module , a été découvert. Sa complexité temporelle est O(n^2) . En 2007, Martin Fürer a proposé un algorithme de complexité O(n^2) . En 2014, Harvey, Joris van der Hoeven et Lecerf en ont proposé un de complexité O(n^3) , explicitant ainsi la algorithme galactique de complexité O(n^3) . Ce résultat correspond à une hypothèse de Schönhage et Strassen selon laquelle il s'agirait de la borne optimale, bien que cela reste à ce jour une conjecture .

Les algorithmes de multiplication d'entiers peuvent également être utilisés pour multiplier des polynômes au moyen de la méthode de substitution de Kronecker .

système de numération positionnel , une méthode naturelle de multiplication est enseignée à l'école : la multiplication posée , parfois appelée multiplication de base ou algorithme standard . Elle consiste à multiplier le multiplicande par chaque chiffre du multiplicateur , puis à additionner les résultats obtenus après décalage. Elle nécessite la mémorisation des tables de multiplication à un chiffre.

Voici l'algorithme habituel pour multiplier manuellement de grands nombres en base 10. Une personne effectuant une longue multiplication sur papier notera tous les produits puis les additionnera ; un utilisateur d'abaque additionnera les produits dès que chacun sera calculé.

Exemple

Cet exemple utilise la multiplication longue pour multiplier 23 958 233 (multiplicande) par 5 830 (multiplicateur) et arrive à 139 676 498 390 pour le résultat (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)

Autres notations

Dans certains pays comme l'Allemagne , la multiplication ci-dessus est représentée de manière similaire, mais avec le produit original conservé à l'horizontale et le calcul commençant par le premier chiffre du multiplicateur :

23958233 · 5830 ——————————————— 119791165 191665864 71874699 00000000 ——————————————— 139676498390

Le pseudocode ci-dessous décrit le processus de multiplication. Il ne conserve qu'une seule ligne pour stocker la somme, qui devient le résultat final. Notez que l'opérateur « += » est utilisé pour ajouter une valeur à une autre et stocker l'opération (comme dans des langages tels que Java et C) par souci de concision.

puces implémentent la multiplication longue, soit matériellement , soit par microcode , pour différentes tailles de mots entiers et à virgule flottante. En arithmétique arbitraire , on utilise couramment la multiplication longue avec la base 2 ^w , où w est le nombre de bits dans un mot, pour multiplier ^des nombres relativement petits. Multiplier deux nombres à n chiffres par cette méthode nécessite environ n² opérations. Plus formellement, multiplier deux nombres ^àn chiffres par multiplication longue requiert Θ ( n² ) opérations sur un seul chiffre (additions et multiplications).

Lorsqu'ils sont implémentés dans un logiciel, les algorithmes de multiplication longue doivent gérer les dépassements de capacité lors des additions, ce qui peut s'avérer coûteux. Une solution courante consiste à représenter le nombre dans une petite base, b , telle que, par exemple, 8b soit un entier représentable par la machine. Plusieurs additions peuvent alors être effectuées avant qu'un dépassement de capacité ne survienne. Lorsque le nombre devient trop grand, on en ajoute une partie au résultat, ou on reporte la partie restante et on la ramène à un nombre inférieur à b . Ce processus est appelé normalisation . Richard Brent a utilisé cette approche dans son package Fortran, MP.

Les ordinateurs utilisaient initialement un algorithme très similaire à la multiplication posée en base 2, mais les processeurs modernes ont optimisé les circuits pour des multiplications rapides grâce à des algorithmes plus efficaces, au prix d'une implémentation matérielle plus complexe. En base 2, la multiplication posée est parfois appelée « décalage et addition » , car l'algorithme se simplifie et consiste simplement à décaler vers la gauche (multiplier par les puissances de deux) et à additionner. La plupart des microprocesseurs actuels implémentent cet algorithme, ou d'autres similaires (comme le codage de Booth ), pour différentes tailles d'entiers et de nombres à virgule flottante, soit dans des multiplicateurs matériels , soit dans du microcode .la division par une constante peuvent être réalisées à l'aide d'une séquence de décalages et d'additions ou de soustractions. Par exemple, il existe plusieurs façons de multiplier par 10 en utilisant uniquement des décalages binaires et des additions.

Algorithmes de multiplication manuelle

Outre la multiplication posée classique, il existe plusieurs autres méthodes pour effectuer des multiplications à la main. Ces algorithmes peuvent être conçus pour optimiser la rapidité, simplifier les calculs ou présenter un intérêt pédagogique, notamment lorsque l'accès à un ordinateur ou à des tables de multiplication est impossible.

Méthode de grille

méthode de la grille (ou méthode des cases) est une méthode d'introduction à la multiplication à plusieurs chiffres souvent enseignée aux élèves de l' école primaire . Elle fait partie intégrante du programme national de mathématiques de l'école primaire en Angleterre et au Pays de Galles depuis la fin des années 1990.

Les deux facteurs sont décomposés (« partitionnés ») en leurs parties centaines, dizaines et unités, et les produits des parties sont ensuite calculés explicitement dans une étape de multiplication relativement simple, avant que ces contributions ne soient totalisées pour donner la réponse finale dans une étape d'addition distincte.

Le calcul 34 × 13, par exemple, pourrait être effectué à l'aide de la grille :

×304103004039012

suivi d'une addition pour obtenir 442, soit en une seule somme (voir à droite), soit en calculant les totaux ligne par ligne

(300 + 40) + (90 + 12) = 340 + 102 = 442.

Cette méthode de calcul (même si elle n'utilise pas nécessairement la grille explicite) est également connue sous le nom d'algorithme des produits partiels . Elle consiste essentiellement à calculer séparément les multiplications simples, toutes les additions étant reportées à l'étape finale de regroupement.

La méthode de la grille peut en principe s'appliquer à des facteurs de toute taille, bien que le nombre de sous-produits devienne important lorsque le nombre de chiffres augmente. Elle est néanmoins considérée comme une méthode explicite et utile pour introduire la notion de multiplication à plusieurs chiffres ; et, à une époque où la plupart des multiplications sont effectuées à l'aide d'une calculatrice ou d'un tableur , il se peut qu'elle soit, en pratique, le seul algorithme de multiplication dont certains élèves auront besoin.

Multiplication du réseau

Commencez par dresser la grille en inscrivant les nombres à multiplier sur ses lignes et ses colonnes. Ensuite, remplissez les cases avec les chiffres des dizaines dans les triangles du haut et les chiffres des unités dans ceux du bas.

La multiplication en treillis, ou multiplication par crible, est algorithmiquement équivalente à la multiplication posée. Elle nécessite la préparation d'un treillis (une grille dessinée sur papier) qui guide le calcul et sépare les multiplications des additions . Elle fut introduite en Europe en 1202 dans le Liber Abaci de Fibonacci . Fibonacci décrivait l'opération comme mentale, utilisant ses deux mains pour effectuer les calculs intermédiaires. Matrakçı Nasuh présenta six variantes de cette méthode dans son ouvrage du XVIe siècle, l'Umdet-ul Hisab. Elle était largement utilisée dans les écoles d'Enderun à travers l'Empire ottoman. Les bâtonnets de Napier , ou bâtonnets de Napier, utilisaient également cette méthode, comme l'a publié Napier en 1617, année de sa mort.

Comme le montre l'exemple, le multiplicande et le multiplicateur sont inscrits au-dessus et à droite d'un treillis, ou d'un crible. On trouve cette formule dans l'ouvrage « Arithmétique » de Muhammad ibn Musa al-Khwarizmi , une des sources de Léonard de Vinci citées par Sigler, auteur du « Liber Abaci de Fibonacci » (2002).

tables de multiplication nécessaires à la multiplication posée. Cet algorithme était utilisé dans l'Égypte antique. Ses principaux avantages sont sa rapidité d'apprentissage, l'absence de mémorisation et la possibilité d'utiliser des jetons, comme des jetons de poker , en l'absence de papier et de crayon. Son inconvénient est qu'elle comporte plus d'étapes que la multiplication posée, ce qui peut la rendre difficile à manipuler pour les grands nombres.

Description

Une colonne contient les nombres obtenus en divisant successivement le multiplicateur par deux sans tenir compte du reste. Une autre colonne, adjacente, contient les résultats obtenus en doublant successivement le multiplicande. Le produit est calculé en barrant chaque ligne dont le premier nombre se termine par un chiffre pair, puis en additionnant les nombres restants dans la seconde colonne.

Exemples

Cet exemple utilise la multiplication paysanne pour multiplier 11 par 3 afin d'obtenir un résultat de 33.

Décimal : Binaire : 11 3 1011 11 5 6 101 110 2 12 10 1100 1 24 1 11000 —— —————— 33 100001

Décrire explicitement les étapes :

Les chiffres 11 et 3 sont inscrits en haut.
11 est divisé par deux (5,5) et 3 est doublé (6). La partie fractionnaire est supprimée (5,5 devient 5).
5 est divisé par deux (2,5) et 6 est doublé (12). La partie décimale est supprimée (2,5 devient 2). Le chiffre de la colonne de gauche (2) étant pair , celui de la colonne de droite (12) est supprimé.
2 est divisé par deux (1) et 12 est doublé (24).
Toutes les valeurs non rayées sont additionnées : 3 + 6 + 24 = 33.

La méthode fonctionne car la multiplication est distributive , donc :

Un exemple plus complexe, utilisant les chiffres des exemples précédents (23 958 233 et 5 830) :

Décimal : Binaire : 5830 23958233 1011011000110 1011011011001001011011001 2915 47916466 101101100011 10110110110010010110110010 1457 95832932 10110110001 101101101100100101101100100 728 191665864 1011011000 1011011011001001011011001000 364 383331728 101101100 10110110110010010110110010000 182 766663456 10110110 101101101100100101101100100000 91 1533326912 1011011 1011011011001001011011001000000 45 3066653824 101101 10110110110010010110110010000000 22 6133307648 10110 101101101100100101101100100000000 11 12266615296 1011 1011011011001001011011001000000000 5 24533230592 101 10110110110010010110110010000000000 2 49066461184 10 101101101100100101101100100000000000 1 98132922368 1 1011011011001001011011001000000000000 ———————————— 1022143253354344244353353243222210110 (avant transport) 139676498390 10000010000101010111100011100111010110

multiplication du quart de carré

Cette formule peut, dans certains cas, être utilisée pour faciliter les opérations de multiplication :

Dans le cas où et sont des entiers, nous avons que

Parce que et sont soit tous deux pairs, soit tous deux impairs. Cela signifie que

et il suffit de (pré-)calculer la partie entière des carrés divisés par 4 comme dans l'exemple suivant.

Exemples

Ci-dessous figure un tableau de consultation des quarts de carrés dont le reste est ignoré pour les chiffres de 0 à 18 ; cela permet la multiplication des nombres jusqu'à $la fonction partie entière ; que certaines sources attribuent aux mathématiques babyloniennes (2000-1600 av. J.-C.).$

Antoine Voisin publia en 1817 une table de quarts de carré de 1 à 1000 pour faciliter les multiplications. Une table plus grande de quarts de carré de 1 à 100 000 fut publiée par Samuel Laundy en 1856 et une table de 1 à 200 000 par Joseph Blater en 1888

Les multiplicateurs quart de carré étaient utilisés dans les calculateurs analogiques pour générer un signal analogique produit de deux signaux d'entrée analogiques. Dans cette application, la somme et la différence de deux tensions d'entrée sont calculées à l'aide d'amplificateurs opérationnels . Le carré de chacune est approché par des circuits linéaires par morceaux . Enfin, la différence des deux carrés est calculée et multipliée par un facteur d'un quart grâce à un autre amplificateur opérationnel.

En 1980, Everett L. Johnson a proposé d'utiliser la méthode du quart de carré dans un multiplicateur numérique . Pour former le produit de deux entiers de 8 bits, par exemple, le dispositif numérique forme la somme et la différence, recherche les deux quantités dans une table de carrés, prend la différence des résultats et divise par quatre en décalant deux bits vers la droite. Pour les entiers de 8 bits, le tableau des quarts de carrés aura 2 ⁹− 1=511 entrées (une entrée pour la plage complète 0..510 des sommes possibles, les différences utilisant uniquement les 256 premières entrées dans la plage 0..255) ou 2 ⁹− 1=511 entrées (en utilisant pour les différences négatives la technique des compléments à 2 et du masquage de 9 bits, ce qui évite de tester le signe des différences), chaque entrée étant de 16 bits de large (les valeurs des entrées vont de (0²/4)=0 à (510²/4)=65025).

systèmes 8 bits qui ne prennent pas en charge un multiplicateur matériel. Charles Putney l'a implémentée pour le 6502. [

Complexité de calcul de la multiplication

De nouveaux problèmes non résolus en informatique

Un axe de recherche en informatique théorique porte sur le nombre d'opérations arithmétiques sur un bit nécessaires pour multiplier deux entiers de bits. On parle alors de complexité algorithmique de la multiplication. Les algorithmes classiques, calculés manuellement, ont une complexité asymptotique de O( n^2) , mais en 1960, Anatoly Karatsuba a découvert qu'une complexité inférieure était possible (avec l' algorithme de Karatsuba ).

Actuellement, l'algorithme présentant la meilleure complexité de calcul est un algorithme de 2019 développé par Joris van der Hoeven , qui utilise les stratégies de transformations arithmétiques introduites avec l' algorithme de Schönhage-Strassen pour multiplier des entiers en utilisant uniquement des opérations. On conjecture qu'il s'agit du meilleur algorithme possible, mais ses bornes inférieures ne sont pas connues.

multiplication de Karatsuba

où et sont inférieurs à . Le produit est alors où Ces formules nécessitent quatre multiplications et étaient connues de Charles Babbage . Karatsuba a observé que l' on peut calculer en seulement trois multiplications, moyennant quelques additions supplémentaires. Avec et comme précédemment, on peut observer que En raison de la surcharge liée à la récursivité, la multiplication de Karatsuba est plus lente que la multiplication longue pour les petites valeurs de n; les implémentations typiques optent donc pour la multiplication longue pour les petites valeurs de n . Cas général avec multiplication de N nombres En analysant les tendances après expansion, on constate ce qui suit : Chaque terme de la somme est associé à un nombre binaire unique compris entre 0 et 1 , par exemple 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 1 ... En d'autres termes, on obtient :, où désigne le chiffre du nombre i à la position j. Remarquez que Histoire L'algorithme de Karatsuba a été le premier algorithme connu de multiplication asymptotiquement plus rapide que la multiplication longue, et peut donc être considéré comme le point de départ de la théorie des multiplications rapides.

Toom-Cook

Démonstration du calcul de 1234 × 5678 = 7006652 par transformée de Fourier rapide (FFT). On utilise des transformations arithmétiques sur les entiers modulo 337, en choisissant 85 comme racine huitième de l'unité. La base 10 est utilisée à la place de la base 2 ^à des fins d'illustration.

Tout nombre en base B peut être écrit sous forme de polynôme :

De plus, la multiplication de deux nombres peut être considérée comme le produit de deux polynômes :

Étant donné que le coefficient de dans le produit est égal à un, il existe une convolution, et l'on peut utiliser la transformée de Fourier rapide (FFT) :

Par conséquent, la multiplication est réduite à une FFT, multiplications et une FFT inverse. Il en résulte une complexité temporelle de $Strassen (1968). Il a été rendu pratique et des garanties théoriques ont été fournies en 1971 par Schönhage et Strassen, ce qui a donné lieu à l' algorithme de Schönhage-Strassen .$

Améliorations supplémentaires

En 2007, le mathématicien suisse Martin Fürer, de l'Université d'État de Pennsylvanie, a amélioré la complexité asymptotique de la multiplication d'entiers en utilisant les transformées de Fourier sur les nombres complexes , où log ^* désigne le logarithme itéré . Anindya De, Chandan Saha, Piyush Kurur et Ramprasad Saptharishi ont proposé en 2008 un algorithme similaire utilisant l'arithmétique modulaire , atteignant le même temps d'exécution . Dans le contexte de ce qui précède, ces derniers auteurs ont réussi à trouver N bien inférieur à 2 ^^3k +1, de sorte que Z / NZ ait une racine (2 m )-ième de l'unité. Ceci accélère les calculs et réduit la complexité temporelle. Cependant, ces algorithmes ne sont plus rapides que l'algorithme de Schönhage-Strassen que pour des entrées excessivement grandes.

En 2014, Harvey, Joris van der Hoeven et Lecerf ont proposé un nouvel algorithme dont la complexité temporelle est de O(n^2), en explicitant la constante implicite dans l' exposant. Ils ont également proposé une variante de cet algorithme, dont la complexité temporelle est de O(n^2), mais dont la validité repose sur des conjectures classiques concernant la distribution des nombres premiers de Mersenne . En 2016, Covanov et Thomé ont proposé un algorithme de multiplication d'entiers basé sur une généralisation des nombres premiers de Fermat , dont la complexité est conjecturée comme étant de O (n^2 ). Ce résultat correspond au résultat conditionnel de Harvey, van der Hoeven et Lecerf de 2015, mais utilise un algorithme différent et repose sur une conjecture différente. En 2018, Harvey et van der Hoeven ont utilisé une approche basée sur l'existence de vecteurs de réseau courts, garantie par le théorème de Minkowski, pour démontrer une borne de complexité inconditionnelle de O(n^ 2) .

En mars 2019, Joris van der Hoeven ont annoncé la découverte d'un algorithme de multiplication en Annals of Mathematics en 2021. Puisque Schönhage et Strassen avaient prédit que n log( n ) était le « meilleur résultat possible », Harvey a déclaré : « …

limites inférieures

Il existe une borne inférieure triviale pour Ω ( n ) lors de la multiplication de deux nombres de n bits sur un seul processeur ; aucun algorithme correspondant (sur machines conventionnelles, c'est-à-dire sur machines équivalentes à la machine de Turing) ni aucune borne inférieure plus précise n'est connu. La conjecture de Hartmanis-Stearns impliquerait que cette borne inférieure ne peut être atteinte. La multiplication se situe en dehors de AC ^0 [ p ] pour tout nombre premier p , ce qui signifie qu'il n'existe aucune famille de circuits de profondeur constante et de taille polynomiale (ou même sous-exponentielle) utilisant des portes ET, OU, NON et MOD _p permettant de calculer un produit. Ceci découle d'une réduction de profondeur constante de MOD _q à la multiplication. Des bornes inférieures pour la multiplication sont également connues pour certaines classes de programmes à branchement .

multiplication de nombres complexes

La multiplication complexe implique normalement quatre multiplications et deux additions.

Comme l'a observé Peter Ungar en 1963, on peut réduire le nombre de multiplications à trois, en utilisant essentiellement le même calcul que l'algorithme de Karatsuba . Le produit ( a + bi ) · ( c + di ) peut être calculé de la manière suivante.

k ₁ = c · ( a + b )

k ₂ = a · ( d − c )

k ₃ = b · ( c + d )

Partie réelle = k ₁ − k ₃

Partie imaginaire = k ₁ + k ₂ .

Cet algorithme n'utilise que trois multiplications au lieu de quatre, et cinq additions ou soustractions au lieu de deux. Si une multiplication est plus coûteuse que trois additions ou soustractions, comme lors d'un calcul manuel, on observe un gain de vitesse. Sur les ordinateurs modernes, une multiplication et une addition peuvent prendre à peu près le même temps ; il se peut donc qu'il n'y ait aucun gain de vitesse. En revanche, l'utilisation de nombres à virgule flottante peut entraîner une légère perte de précision.

Pour les transformées de Fourier rapides (FFT) (ou toute transformation linéaire ), les multiplications complexes sont effectuées par des coefficients constants c + di (appelés facteurs de rotation dans les FFT), auquel cas deux des additions ( d − c et c + d ) peuvent être précalculées. Par conséquent, seules trois multiplications et trois additions sont nécessaires. Cependant, remplacer une multiplication par une addition de cette manière peut ne plus être avantageux avec les unités de calcul en virgule flottante modernes .

multiplication polynomiale

Tous les algorithmes de multiplication ci-dessus peuvent également être étendus à la multiplication de polynômes . Alternativement, la technique de substitution de Kronecker peut être utilisée pour convertir le problème de la multiplication de polynômes en une seule multiplication binaire.

Les méthodes de multiplication longue peuvent être généralisées pour permettre la multiplication de formules algébriques :

14ac - 3ab + 2 multiplié par ac - ab + 1

14ac -3ab 2 ac -ab 1 ———————————————————— 14a ² c ² -3a ² bc 2ac -14a ² bc 3 a ² b ² -2ab 14ac -3ab 2 ——————————————————————————————————————— 14a ² c ² -17a ² bc 16ac 3a ² b ² -5ab +2 =======================================

À titre d'exemple supplémentaire de multiplication basée sur les colonnes, considérez la multiplication de 23 tonnes longues (t), 12 quintaux (cwt) et 2 quarts (qtr) par 47. Cet exemple utilise les mesures avoirdupois : 1 t = 20 cwt, 1 cwt = 4 qtr.

 t cwt qtr 23 12 2 47 × ———————————————— 1. Multipliez tout par 47 1081 564 94 ———————————————— 2a. Reporter le quart et ajouter au quintal (94 = 23 × 4 + 2) (564) 94 23 2 ————— 587 2 2b. Reporter le poids en quintaux et l'ajouter à t (587 = 29 × 20 + 7) (1081) 587 2 29 7 ———————————————— 3. Ajout final 1110 7 2 Réponse : 1110 tonnes 7 quintaux 2 quarts

La même disposition et les mêmes méthodes peuvent être utilisées pour toutes les mesures traditionnelles et les monnaies non décimales telles que l'ancien système britannique £sd .