Algorithme de multiplication - Multiplication algorithm

Un algorithme de multiplication est un algorithme (ou méthode) pour multiplier deux nombres. Selon la taille des nombres, différents algorithmes sont utilisés. Des algorithmes de multiplication efficaces existent depuis l'avènement du système décimal.

Méthode de la grille

La méthode de la grille (ou méthode de la boîte) est une méthode d'introduction à la multiplication à plusieurs chiffres qui est souvent enseignée aux élèves de l'école primaire ou de l'école élémentaire . Il fait partie intégrante du programme national de mathématiques des écoles primaires 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 de centaines, de dizaines et d'unités, et les produits des parties sont ensuite calculés explicitement dans une étape de multiplication uniquement relativement simple, avant que ces contributions ne soient ensuite totalisées pour donner la réponse finale en une étape d'addition séparée.

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

  300
   40
   90
 + 12
 ————
  442

suivi d'une addition pour obtenir 442, soit en une seule somme (voir à droite), soit en formant les totaux ligne par ligne (300 + 40) + (90 + 12) = 340 + 102 = 442.

Cette approche de calcul (mais pas nécessairement avec la disposition explicite de la grille) est également connue sous le nom d' algorithme des produits partiels . Son essence est le calcul des multiplications simples séparément, toute addition étant laissée à l'étape de collecte finale.

La méthode de la grille peut en principe être appliquée à des facteurs de toute taille, bien que le nombre de sous-produits devienne encombrant à mesure que le nombre de chiffres augmente. Néanmoins, il est considéré comme une méthode utilement explicite pour introduire l'idée de multiplications à plusieurs chiffres ; et, à une époque où la plupart des calculs de multiplication sont effectués à l'aide d'une calculatrice ou d'un tableur, il peut s'agir en pratique du seul algorithme de multiplication dont certains élèves auront jamais besoin.

Longue multiplication

Si un système de numération positionnelle est utilisé, une manière naturelle de multiplier les nombres est enseignée dans les écoles comme la multiplication longue , parfois appelée multiplication scolaire , parfois appelée algorithme standard : multipliez le multiplicande par chaque chiffre du multiplicateur , puis additionnez tous les résultats décalés. Il nécessite la mémorisation de la table de multiplication pour les chiffres simples.

Il s'agit de l'algorithme habituel pour multiplier à la main de plus grands nombres en base 10. Les ordinateurs utilisaient initialement un algorithme de décalage et d'addition très similaire en base 2, mais les processeurs modernes ont optimisé les circuits pour des multiplications rapides en utilisant des algorithmes plus efficaces, au prix d'un algorithme plus complexe. réalisation matérielle. Une personne faisant une longue multiplication sur papier écrira tous les produits et les additionnera ensuite ; un utilisateur d' abacus additionnera les produits dès que chacun sera calculé.

Exemple

Cet exemple utilise une longue multiplication 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        )

Le pseudocode ci-dessous décrit le processus de multiplication ci-dessus. Il ne garde qu'une ligne pour conserver la somme qui devient finalement le résultat. Notez que l'opérateur '+=' est utilisé pour indiquer la somme à la valeur existante et l'opération de stockage (semblable à des langages tels que Java et C) pour la compacité.

multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1
  product = [1..p+q]                                        // Allocate space for result
  for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        // for all digits in a
      product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
      carry = product[a_i + b_i - 1] / base
      product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
    product[b_i + p] = carry                               // last digit comes from final carry
  return product

Optimiser la complexité de l'espace

Soit n le nombre total de chiffres dans les deux nombres d'entrée en base D . Si le résultat doit être conservé en mémoire alors la complexité spatiale est trivialement Θ( n ). Cependant, dans certaines applications, l'intégralité du résultat n'a pas besoin d'être conservée en mémoire et à la place, les chiffres du résultat peuvent être diffusés au fur et à mesure qu'ils sont calculés (par exemple, vers la console système ou un fichier). Dans ces scénarios, la multiplication longue a l'avantage de pouvoir être facilement formulée sous la forme d'un algorithme d' espace logarithmique ; qui est un algorithme qui n'a besoin que d'un espace de travail proportionnel au logarithme du nombre de chiffres dans l'entrée ( Θ (log  n )). C'est le double logarithme des nombres eux-mêmes multipliés (log log  N ). Notez que les opérandes eux-mêmes doivent toujours être conservés en mémoire et que leur espace Θ( n ) n'est pas pris en compte dans cette analyse.

La méthode est basée sur l'observation que chaque chiffre du résultat peut être calculé de droite à gauche en ne connaissant que le report de l'étape précédente. Soit a _i et b _i le i- ème chiffre de l'opérande, avec a et b complétés à gauche par des zéros pour avoir une longueur n , r _i le i- ème chiffre du résultat et c _i le report généré pour r _i (i=1 est le chiffre le plus à droite) alors

${\displaystyle {\begin{aligned}r_{i}&=\left(c_{i-1}+\sum _{j+k=i+1}a_{j}b_{k}\right)\mod D\\c_{i}&=\left\lfloor (c_{i-1}+\sum _{j+k=i}a_{j}b_{k})/D\right\rfloor \\c_{ 0}&=0\end{aligned}}}$

ou

${\displaystyle c_{i}=\left(\sum _{m=0}^{i-2}\sum _{j+k=im}a_{j}b_{k}\right)/D.}$

Un argument inductif simple montre que le report ne peut jamais dépasser n et que la somme totale pour r _i ne peut jamais dépasser D * n : le report dans la première colonne est nul, et pour toutes les autres colonnes, il y a au plus n chiffres dans la colonne , et un report d'au plus n de la colonne précédente (par l'hypothèse d'induction). La somme est au plus D * n , et le report à la colonne suivante est au plus D * n / D , ou n . Ainsi, ces deux valeurs peuvent être stockées dans O(log n ) chiffres.

En pseudocode, l'algorithme log-space est :

multiply(a[1..p], b[1..q], base)                  // Operands containing rightmost digits at index 1
    tot = 0
    for ri = 1 to p + q - 1                       // For each digit of result
        for bi = MAX(1, ri - p + 1) to MIN(ri, q) // Digits from b that need to be considered
            ai = ri − bi + 1                      // Digits from a follow "symmetry"
            tot = tot + (a[ai] * b[bi])
        product[ri] = tot mod base
        tot = floor(tot / base)
    product[p+q] = tot mod base                   // Last digit of the result comes from last carry
    return product

Utilisation dans les ordinateurs

Certaines puces implémentent une multiplication longue, en matériel ou en microcode , pour différentes tailles de mots entiers et à virgule flottante. En arithmétique de précision arbitraire , il est courant d'utiliser une multiplication longue avec la base définie sur 2 ^w , où w est le nombre de bits dans un mot, pour multiplier des nombres relativement petits.

Pour multiplier deux nombres à n chiffres en utilisant cette méthode, il faut environ n ² opérations. Plus formellement : en utilisant une métrique de taille naturelle du nombre de chiffres, la complexité temporelle de la multiplication de deux nombres à n chiffres en utilisant une multiplication longue est Θ ( n ² ).

Lorsqu'ils sont implémentés dans un logiciel, les algorithmes de multiplication longs doivent gérer des débordements lors des additions, ce qui peut être coûteux. Une solution typique consiste à représenter le nombre dans une petite base, b , telle que, par exemple, 8 b est un entier machine représentable. Plusieurs ajouts peuvent alors être effectués avant qu'un débordement ne se produise. Lorsque le nombre devient trop grand, nous en ajoutons une partie au résultat, ou nous réalisons et mappons la partie restante à un nombre inférieur à b . Ce processus est appelé normalisation . Richard Brent a utilisé cette approche dans son package Fortran, MP.

Multiplication de réseau

Tout d'abord, configurez la grille en marquant ses lignes et ses colonnes avec les nombres à multiplier. Ensuite, remplissez les cases avec les chiffres des dizaines dans les triangles du haut et les chiffres des unités en bas.

Enfin, additionnez le long des diagonales et effectuez au besoin pour obtenir la réponse

La multiplication en treillis, ou en tamis, est algorithmiquement équivalente à la multiplication longue. Elle nécessite la préparation d'un treillis (une grille dessinée sur papier) qui guide le calcul et sépare toutes les multiplications des additions . Il a été introduit en Europe en 1202 dans le Liber Abaci de Fibonacci . Fibonacci a décrit l'opération comme mentale, utilisant ses mains droite et gauche pour effectuer les calculs intermédiaires. Matrakçı Nasuh a présenté 6 variantes différentes de cette méthode dans ce livre du XVIe siècle, Umdet-ul Hisab. Il a été largement utilisé dans les écoles Enderun à travers l'Empire ottoman. Les ossements de Napier , ou bâtonnets de Napier utilisaient également cette méthode, telle que publiée par Napier en 1617, l'année de sa mort.

Comme le montre l'exemple, le multiplicande et le multiplicateur sont écrits au-dessus et à droite d'un treillis ou d'un tamis. On le trouve dans « Arithmétique » de Muhammad ibn Musa al-Khwarizmi , une des sources de Léonard mentionnée par Sigler, auteur du « Liber Abaci de Fibonacci », 2002.

• Pendant la phase de multiplication, le treillis est rempli avec des produits à deux chiffres des chiffres correspondants étiquetant chaque ligne et colonne : le chiffre des dizaines va dans le coin supérieur gauche.
• Lors de la phase d'addition, le réseau est sommé sur les diagonales.
• Enfin, si une phase de retenue est nécessaire, la réponse indiquée le long des côtés gauche et inférieur du réseau est convertie en forme normale en portant les chiffres des dizaines comme dans une longue addition ou une multiplication.

Exemple

Les images de droite montrent comment calculer 345 × 12 en utilisant la multiplication de réseau. Comme exemple plus compliqué, considérons l'image ci-dessous affichant le calcul de 23 958 233 multiplié par 5 830 (multiplicateur) ; le résultat est 139 676 498 390. Remarquez que 23 958 233 se trouvent au sommet du treillis et 5 830 se trouvent sur le côté droit. Les produits remplissent le réseau et la somme de ces produits (sur la diagonale) se trouve le long des côtés gauche et inférieur. Ensuite, ces sommes sont totalisées comme indiqué.

     2   3   9   5   8   2   3   3
   +---+---+---+---+---+---+---+---+-
   |1 /|1 /|4 /|2 /|4 /|1 /|1 /|1 /|
   | / | / | / | / | / | / | / | / | 5
 01|/ 0|/ 5|/ 5|/ 5|/ 0|/ 0|/ 5|/ 5|
   +---+---+---+---+---+---+---+---+-
   |1 /|2 /|7 /|4 /|6 /|1 /|2 /|2 /|
   | / | / | / | / | / | / | / | / | 8
 02|/ 6|/ 4|/ 2|/ 0|/ 4|/ 6|/ 4|/ 4|
   +---+---+---+---+---+---+---+---+-
   |0 /|0 /|2 /|1 /|2 /|0 /|0 /|0 /|
   | / | / | / | / | / | / | / | / | 3
 17|/ 6|/ 9|/ 7|/ 5|/ 4|/ 6|/ 9|/ 9|
   +---+---+---+---+---+---+---+---+-
   |0 /|0 /|0 /|0 /|0 /|0 /|0 /|0 /|
   | / | / | / | / | / | / | / | / | 0
 24|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|/ 0|
   +---+---+---+---+---+---+---+---+-
     26  15  13  18  17  13  09  00

 01
 002
 0017
 00024
 000026
 0000015
 00000013
 000000018
 0000000017
 00000000013
 000000000009
 0000000000000
 —————————————
  139676498390

= 139,676,498,390

Multiplication binaire ou paysanne

La méthode binaire est également connue sous le nom de multiplication paysanne, car elle a été largement utilisée par des personnes classées comme paysannes et n'ayant donc pas mémorisé les tables de multiplication requises pour une multiplication longue. L'algorithme était utilisé dans l'Egypte ancienne. Ses principaux avantages sont qu'il peut être enseigné rapidement, ne nécessite aucune mémorisation et peut être exécuté à l'aide de jetons, tels que des jetons de poker , si le papier et le crayon ne sont pas disponibles. L'inconvénient est qu'elle prend plus d'étapes qu'une longue multiplication, elle peut donc être lourde pour les grands nombres.

La description

Sur papier, notez dans une colonne les chiffres que vous obtenez lorsque vous divisez par deux le multiplicateur à plusieurs reprises, en ignorant le reste ; dans une colonne à côté, doubler à plusieurs reprises le multiplicande. Rayez chaque ligne dans laquelle le dernier chiffre du premier nombre est pair et ajoutez les nombres restants dans la deuxième colonne pour obtenir le produit.

Exemples

Cet exemple utilise la multiplication paysanne pour multiplier 11 par 3 pour arriver à un résultat de 33.

Decimal:     Binary:
11   3       1011  11
5    6       101  110
2   12       10  1100
1   24       1  11000
    ——         ——————
    33         100001

Description explicite des étapes :

• 11 et 3 sont écrits en haut
• 11 est réduit de moitié (5,5) et 3 est doublé (6). La partie fractionnaire est rejetée (5,5 devient 5).
• 5 est réduit de moitié (2,5) et 6 est doublé (12). La partie fractionnaire est rejetée (2,5 devient 2). Le chiffre de la colonne de gauche (2) est pair , donc le chiffre de la colonne de droite (12) est ignoré.
• 2 est réduit de moitié (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 :

${\displaystyle {\begin{aligned}3\times 11&=3\times (1\times 2^{0}+1\times 2^{1}+0\times 2^{2}+1\times 2^ {3})\\&=3\fois (1+2+8)\\&=3+6+24\\&=33.\end{aligned}}}$

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

Decimal:             Binary:
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 (before carry)
  139676498390         10000010000101010111100011100111010110

Multiplication binaire dans les ordinateurs

Il s'agit d'une variante de la multiplication paysanne.

En base 2, la multiplication longue se réduit à une opération presque triviale. Pour chaque bit '1' dans le multiplicateur , décalez le multiplicande d'une quantité appropriée, puis additionnez les valeurs décalées. Dans certains processeurs , il est plus rapide d'utiliser des décalages de bits et des additions plutôt que des instructions de multiplication, surtout si le multiplicateur est petit ou toujours le même.

Décaler et ajouter

Historiquement, les ordinateurs utilisaient un algorithme "shift and add" pour multiplier de petits nombres entiers. La multiplication longue en base 2 et la multiplication paysanne en base 2 se réduisent à ce même algorithme. En base 2, la multiplication par le seul chiffre du multiplicateur se réduit à une simple série d' opérations ET logiques . Chaque produit partiel est ajouté à une somme cumulée dès que chaque produit partiel est calculé. La plupart des microprocesseurs actuellement disponibles implémentent cet algorithme ou d'autres algorithmes similaires (tels que l'encodage Booth ) pour diverses tailles entières et à virgule flottante dans des multiplicateurs matériels ou dans un microcode .

Sur les processeurs actuellement disponibles, une instruction de décalage au niveau du bit est plus rapide qu'une instruction de multiplication et peut être utilisée pour multiplier (décaler à gauche) et diviser (décaler à droite) par des puissances de deux. La multiplication par une constante et la division par une constante peuvent être mises en œuvre en utilisant 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 le décalage de bits et l'addition.

((x << 2) + x) << 1 # Here 10*x is computed as (x*2^2 + x)*2
(x << 3) + (x << 1) # Here 10*x is computed as x*2^3 + x*2

Dans certains cas, de telles séquences de décalages et d'additions ou de soustractions surpasseront les multiplicateurs matériels et en particulier les diviseurs. Une division par un nombre de la forme ou souvent peut être convertie en une séquence aussi courte. ${\style d'affichage 2^{n}}$${\displaystyle 2^{n}\pm 1}$

Ces types de séquences doivent toujours être utilisés pour les ordinateurs qui n'ont pas d'instruction "multiplier", et peuvent également être utilisés par extension aux nombres à virgule flottante si l'on remplace les décalages par le calcul de 2*x comme x+x , car ces sont logiquement équivalents.

Multiplication par quart de carré

Deux quantités peuvent être multipliées à l'aide de quarts de carré en utilisant l'identité suivante impliquant la fonction plancher que certaines sources attribuent aux mathématiques babyloniennes (2000-1600 av.

${\displaystyle \left\lfloor {\frac {\left(x+y\right)^{2}}{4}}\right\rfloor -\left\lfloor {\frac {\left(xy\right)^ {2}}{4}}\right\rfloor ={\frac {1}{4}}\left(\left(x^{2}+2xy+y^{2}\right)-\left(x ^{2}-2xy+y^{2}\right)\right)={\frac {1}{4}}\left(4xy\right)=xy.}$

Si l'un de x + y et x − y est impair, l'autre est impair aussi, donc leurs carrés sont de 1 mod 4, alors la prise de parole réduit les deux d'un quart ; la soustraction annule alors les quarts, et l'élimination des restes n'introduit aucune différence par rapport à la même expression sans les fonctions de plancher. Vous trouverez ci-dessous une table de correspondance des quarts de carré avec le reste ignoré pour les chiffres 0 à 18 ; cela permet la multiplication de nombres jusqu'à 9×9 .

Si, par exemple, vous vouliez multiplier 9 par 3, vous constatez que la somme et la différence sont respectivement 12 et 6. En regardant ces deux valeurs sur le tableau, on obtient 36 et 9, dont la différence est de 27, qui est le produit de 9 et 3.

Antoine Voisin a publié une table des quarts de carré de 1 à 1000 en 1817 pour aider à la multiplication. Une table plus grande des quarts de carré de 1 à 100 000 a été publiée par Samuel Laundy en 1856, et une table de 1 à 200 000 par Joseph Blater en 1888.

Des multiplicateurs quart de carré ont été utilisés dans les ordinateurs analogiques pour former un signal analogique qui était le produit de deux signaux d'entrée analogiques. Dans cette application, la somme et la différence de deux tensions d' entrée sont formées à l'aide d' amplificateurs opérationnels . Le carré de chacun d'eux est approximé à l'aide de circuits linéaires par morceaux . Enfin, la différence des deux carrés est formée et mise à l'échelle par un facteur d'un quart en utilisant encore 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 nombres entiers de 8 bits, par exemple, l'appareil 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 le droit. Pour les entiers de 8 bits, la table des quarts de carré aura 2 ⁹ -1 = 511 entrées (une entrée pour toute la plage 0..510 des sommes possibles, les différences n'utilisant que les 256 premières entrées de 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 large de 16 bits (les valeurs d'entrée sont de (0²/4 )=0 à (510²/4)=65025).

La technique du multiplicateur quart de carré a également profité aux systèmes 8 bits qui ne prennent pas en charge un multiplicateur matériel. Charles Putney a implémenté cela pour le 6502 .

Algorithmes de multiplication rapide pour les grandes entrées

Algorithme de multiplication complexe

La multiplication complexe implique normalement quatre multiplications et deux additions.

${\style d'affichage (a+bi)(c+di)=(ac-bd)+(bc+ad)i.}$

Ou

${\displaystyle {\begin{array}{c|c|c}\times &a&bi\\\hline c&ac&bci\\\hline di&adi&-bd\end{array}}}$

Mais il existe un moyen de réduire le nombre de multiplications à trois.

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 coûte plus cher que trois additions ou soustractions, comme lors du calcul à la main, alors il y a un gain de vitesse. Sur les ordinateurs modernes, une multiplication et une addition peuvent prendre à peu près le même temps, il peut donc n'y avoir aucun gain de vitesse. Il y a un compromis en ce sens qu'il peut y avoir une certaine perte de précision lors de l'utilisation de la virgule flottante.

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

Multiplication de Karatsuba

Pour les systèmes qui doivent multiplier des nombres de l'ordre de plusieurs milliers de chiffres, tels que les systèmes de calcul formel et les bibliothèques bignum , la multiplication longue est trop lente. Ces systèmes peuvent employer la multiplication de Karatsuba , découverte en 1960 (publiée en 1962). Le cœur de la méthode de Karatsuba réside dans l'observation que la multiplication à deux chiffres peut être faite avec seulement trois au lieu des quatre multiplications classiquement requises. Ceci est un exemple de ce qu'on appelle maintenant un algorithme diviser pour régner . Supposons que nous voulions multiplier deux nombres à 2 chiffres en base m : x ₁ m + x ₂ et y ₁ m + y ₂ :

1. calculer x ₁ · y ₁ , appeler le résultat F
2. calculer x ₂ · y ₂ , appeler le résultat G
3. calculer ( x ₁ + x ₂ ) · ( y ₁ + y ₂ ), appeler le résultat H
4. calculer H − F − G , appeler le résultat K ; ce nombre est égal à x ₁ · y ₂ + x ₂ · y ₁
5. calculer F · m ² + K · m + G .

Pour calculer ces trois produits de nombres en base m , nous pouvons utiliser à nouveau la même astuce, en utilisant efficacement la récursivité . Une fois les nombres calculés, nous devons les additionner (étapes 4 et 5), ce qui prend environ n opérations.

La multiplication de Karatsuba a une complexité temporelle de O ( n ^{log ₂ 3} ) O( n ^1.585 ), ce qui rend cette méthode beaucoup plus rapide que la multiplication longue. En raison de la surcharge de récursivité, la multiplication de Karatsuba est plus lente que la multiplication longue pour les petites valeurs de n ; les implémentations typiques passent donc à la multiplication longue pour les petites valeurs de n .

L'algorithme de Karatsuba a été le premier algorithme connu pour la multiplication qui est 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.

En 1963, Peter Ungar a suggéré de mettre m à i pour obtenir une réduction similaire de l'algorithme de multiplication complexe. Pour multiplier ( a  +  bi ) · ( c  +  di ), procédez comme suit :

1. calculer b · d , appeler le résultat F
2. calculer a · c , appeler le résultat G
3. calculer ( a + b ) · ( c + d ), appeler le résultat H
4. la partie imaginaire du résultat est K = H − F − G = a · d + b · c
5. la partie réelle du résultat est G − F = a · c − b · d

Comme l'algorithme de la section précédente, cela nécessite trois multiplications et cinq additions ou soustractions.

Toom–Cuisinier

Une autre méthode de multiplication s'appelle Toom-Cook ou Toom-3. La méthode Toom-Cook divise chaque nombre à multiplier en plusieurs parties. La méthode Toom-Cook est l'une des généralisations de la méthode Karatsuba. Un Toom-Cook à trois voies peut effectuer une multiplication de taille 3N pour le coût de cinq multiplications de taille N. Cela accélère l'opération d'un facteur 9/5, tandis que la méthode Karatsuba l'accélère de 4/3.

Bien que l'utilisation de plus en plus de parties puisse réduire davantage le temps consacré aux multiplications récursives, les frais généraux liés aux ajouts et à la gestion des chiffres augmentent également. Pour cette raison, la méthode des transformées de Fourier est généralement plus rapide pour les nombres de plusieurs milliers de chiffres, et asymptotiquement plus rapide pour les nombres encore plus grands.

Méthodes de transformée de Fourier

Démonstration de la multiplication de 1234 × 5678 = 7006652 à l'aide de transformées de Fourier rapides (FFT). Des transformations théoriques des nombres dans les entiers modulo 337 sont utilisées, en sélectionnant 85 comme racine huitième de l'unité. La base 10 est utilisée à la place de la base 2 ^w à des fins d'illustration.

L'idée de base due à Strassen (1968) est d'utiliser une multiplication polynomiale rapide pour effectuer une multiplication rapide d'entiers. L'algorithme a été rendu pratique et des garanties théoriques ont été fournies en 1971 par Schönhage et Strassen résultant en l' algorithme de Schönhage-Strassen . Les détails sont les suivants : Nous choisissons le plus grand entier w qui ne provoquera pas de débordement pendant le processus décrit ci-dessous. Ensuite, nous divisons les deux nombres en m groupes de w bits comme suit

${\displaystyle a=\sum _{i=0}^{m-1}{a_{i}2^{wi}}{\text{ and }}b=\sum _{j=0}^{m -1}{b_{j}2^{wj}}.}$

Nous regardons ces nombres comme des polynômes dans x , où x = 2 ^w , pour obtenir,

${\displaystyle a=\sum _{i=0}^{m-1}{a_{i}x^{i}}{\text{ and }}b=\sum _{j=0}^{m -1}{b_{j}x^{j}}.}$

Alors on peut dire que,

${\displaystyle ab=\sum _{i=0}^{m-1}\sum _{j=0}^{m-1}a_{i}b_{j}x^{(i+j)} =\somme _{k=0}^{2m-2}c_{k}x^{k}.}$

Il est clair que le réglage ci-dessus est réalisé par multiplication polynomiale, de deux polynômes a et b . L'étape cruciale consiste maintenant à utiliser la multiplication rapide de Fourier de polynômes pour réaliser les multiplications ci-dessus plus rapidement qu'en temps naïf O ( m ² ).

Pour rester dans le cadre modulaire des transformées de Fourier, on cherche un anneau avec une (2 m )ième racine de l'unité. On fait donc la multiplication modulo N (et donc dans l' anneau Z / NZ ). De plus, N doit être choisi de manière à ce qu'il n'y ait pas de « bouclage », essentiellement, qu'aucune réduction modulo N ne se produise. Ainsi, le choix de N est crucial. Par exemple, cela pourrait être fait comme,

${\style d'affichage N=2^{3m}+1.}$

L'anneau Z / NZ aurait donc une (2 m )ième racine de l'unité, à savoir 8. De plus, on peut vérifier que c _k < N , et donc aucun bouclage ne se produira.

L'algorithme a une complexité temporelle de Θ ( n  log ( n ) log (log ( n ))) et est utilisé dans la pratique pour les nombres avec plus de 10 000 à 40 000 chiffres décimaux. En 2007, cela a été amélioré par Martin Fürer ( algorithme de Fürer ) pour donner une complexité temporelle de n  log( n ) 2 ^{( log * ( n )) en} utilisant des transformées de Fourier sur des nombres complexes. Anindya De, Chandan Saha, Piyush Kurur et Ramprasad Saptharishi ont donné un algorithme similaire utilisant l'arithmétique modulaire en 2008, atteignant le même temps d'exécution. Dans le contexte du matériel ci-dessus, ce que ces derniers auteurs ont atteint est de trouver N bien inférieur à 2 ^{3 k} + 1, de sorte que Z / NZ a une (2 m )ième racine de l'unité. Cela accélère le calcul et réduit la complexité temporelle. Cependant, ces derniers algorithmes ne sont plus rapides que Schönhage-Strassen que pour des entrées peu pratiques.

En mars 2019, David Harvey et Joris van der Hoeven ont publié un article décrivant un algorithme de multiplication O ( n log n ) .

L'utilisation de transformations théoriques des nombres au lieu de transformations de Fourier discrètes évite les problèmes d' erreur d'arrondi en utilisant l'arithmétique modulaire au lieu de l'arithmétique à virgule flottante . Afin d'appliquer la factorisation qui permet à la FFT de fonctionner, la longueur de la transformée doit être factorisable en petits nombres premiers et doit être un facteur de N − 1 , où N est la taille du champ. En particulier, le calcul utilisant un champ de Galois GF( k ² ), où k est un nombre premier de Mersenne , permet d'utiliser une transformée dimensionnée à la puissance 2 ; Par exemple, k = 2 ³¹ − 1 prend en charge les tailles de transformation jusqu'à 2 ³² .

Limites inférieures

Il y a une limite d'abaisser trivial Ω ( n ) pour la multiplication de deux n nombres -bit sur un seul processeur; aucun algorithme d'appariement (sur les machines conventionnelles, c'est-à-dire sur les machines équivalentes de Turing) ni aucune borne inférieure plus nette n'est connue. La multiplication se situe en dehors de AC ⁰ [ p ] pour tout p premier , ce qui signifie qu'il n'y a pas de famille de circuits de taille polynomiale (ou même sous-exponentielle) à profondeur constante utilisant des portes AND, OR, NOT et MOD _p qui peuvent calculer un produit. Cela résulte d'une réduction à profondeur constante de MOD _q à la multiplication. Des limites inférieures pour la multiplication sont également connues pour certaines classes de programmes de branchement .

Multiplication polynomiale

Tous les algorithmes de multiplication ci-dessus peuvent également être étendus pour multiplier des polynômes . Par exemple, l'algorithme de Strassen peut être utilisé pour la multiplication polynomiale. 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 longues peuvent être généralisées pour permettre la multiplication de formules algébriques :

 14ac - 3ab + 2 multiplied by ac - ab + 1

 14ac  -3ab   2
   ac   -ab   1
 ————————————————————
 14a2c2  -3a2bc   2ac
        -14a2bc         3 a2b2  -2ab
                 14ac           -3ab   2
 ———————————————————————————————————————
 14a2c2 -17a2bc   16ac  3a2b2    -5ab  +2
 =======================================

Comme autre exemple de multiplication basée sur des colonnes, envisagez de multiplier 23 tonnes longues (t), 12 quintaux (cwt) et 2 quarters (qtr) par 47. Cet exemple utilise des mesures avoirdupois : 1 t = 20 cwt, 1 cwt = 4 qtr.

    t    cwt  qtr
   23     12    2
               47 x
 ————————————————
  141     94   94
  940    470
   29     23
 ————————————————
 1110    587   94
 ————————————————
 1110      7    2
 =================  Answer: 1110 ton 7 cwt 2 qtr

Multipliez d'abord les quarts par 47, le résultat 94 est écrit dans le premier espace de travail. Ensuite, multipliez cwt 12*47 = (2 + 10)*47 mais n'additionnez pas encore les résultats partiels (94, 470). De même, multipliez 23 par 47 pour obtenir (141, 940). La colonne des quarts est totalisée et le résultat placé dans le deuxième espace de travail (un mouvement trivial dans ce cas). 94 quarters est 23 cwt et 2 qtr, alors placez le 2 dans la réponse et mettez le 23 dans la colonne suivante à gauche. Additionnez maintenant les trois entrées dans la colonne cwt donnant 587. C'est 29 t 7 cwt, alors écrivez le 7 dans la réponse et le 29 dans la colonne de gauche. Additionnez maintenant la colonne des tonnes. Il n'y a aucun ajustement à faire, donc le résultat est juste copié.

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

Voir également

• Multiplicateur binaire
• Algorithme de division
• Logarithme
• Calcul mental
• Prosthaphérèse
• Règle à calcul
• Système Trachtenberg
• Schéma de Horner pour l'évaluation d'un polynôme
• Système de nombre de résidus § Multiplication pour un autre algorithme de multiplication rapide, particulièrement efficace lorsque de nombreuses opérations sont effectuées en séquence, comme en algèbre linéaire
• Papa multiplicateur
• Arbre de Wallace

Les références

Lectures complémentaires

• Warren Jr., Henry S. (2013). Hacker's Delight (2 éd.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.
• Savard, John JG (2018) [2006]. "Techniques arithmétiques avancées" . quadribloc . Archivé de l'original le 2018-07-03 . Récupéré le 16/07/2018 .
• Johansson, Kenny. Calculs basés sur le décalage et l'ajout de faible puissance et de faible complexité (PDF) (thèse de thèse). Études de Linköping en science et technologie (1 éd.). Linköping, Suède : Département de génie électrique, Université de Linköping . ISBN 978-91-7393-836-5. ISSN  0345-7524 . N° 1201. Archivé (PDF) de l'original le 2017-08-13 . Récupéré le 2021-08-23 . (x+268 pages)

Liens externes

Arithmétique de base

• Les nombreuses façons de l'arithmétique dans les mathématiques de tous les jours de l'UCSMP
• Une présentation Powerpoint sur les mathématiques anciennes
• Vidéo Flash de multiplication de treillis

Algorithmes avancés

• Algorithmes de multiplication utilisés par GMP