Loading AI tools
De Wikipédia, l'encyclopédie libre
La technique de multiplication dite russe consiste à diviser par 2 le multiplicateur (et ensuite les quotients obtenus), jusqu'à un quotient nul, et à noter les restes ; et à multiplier parallèlement le multiplicande par 2. On additionne alors les multiples obtenus du multiplicande correspondant aux restes non nuls.
Cela revient en fait à écrire le multiplicateur en base 2 et à faire ensuite des multiplications par 2 et des additions. C'est donc une variante de la technique de la multiplication en Égypte antique, bien qu'elle ait pu être redécouverte indépendamment.
En pseudo code, l'algorithme de multiplication dite russe peut s'écrire :
Fonction mult (x,y) r = 0 Tant que x est différent de 0 Si x est impair alors r = r + y x = x - 1 fin si x = x / 2 y = y * 2 Fin tant que Renvoyer r Fin fonction
Note : les opérations effectuées ici sont des opérations sur des entiers et sont à valeurs dans les entiers.
Pour 13 x 238 on peut écrire :
Opérations sur le multiplicateur | Opérations sur le multiplicande | Somme cumulée des multiples du multiplicande |
13 divisé par 2 : le quotient est 6, le reste est 1, |
238, | 238 |
6 divisé par 2 : le quotient est 3, le reste est 0, |
, | Le reste est nul, pas d'ajout du multiple.
238 |
3 divisé par 2 : le quotient est 1, le reste est 1, |
, | Le reste est non nul,
on ajoute le multiple obtenu à cette étape : |
1 divisé par 2 : le quotient est 0, le reste est 1. Le quotient est nul, on stoppe l'algorithme. |
Le reste est non nul,
on ajoute le multiple obtenu à cette étape : | |
13 = 1101 en base 2 (obtenu en lisant les restes de bas en haut dans le tableau, et écrit selon la convention usuelle de droite — unités — à gauche — puissances élevées).
Pour limiter le nombre d'opérations, il faut généralement choisir comme multiplicateur le plus petit des deux nombres à multiplier. Toutefois, si l'un d'eux est une puissance de 2, c'est plutôt lui qu'il faut préférer (il n'y a pas d'addition). Les restes deviennent forcément nuls, et donc le résultat devient stable, à partir du moment où le quotient est lui-même nul. Formellement, la condition d'arrêt (s'arrêter lorsque le quotient est nul) est donc seulement une commodité.
Graphiquement, l'on peut dire qu'une multiplication transforme un rectangle multiplicateur x multiplicande en une ligne en conservant le nombre d'éléments.
L'algorithme graphique consiste pour la multiplication russe à :
La technique de multiplication dite russe est très liée, mathématiquement, à l'algorithme d'exponentiation rapide, et peut être vue comme une version « additive » de ce dernier. En effet, la technique de multiplication dite russe permet de calculer, pour tout entier k et élément g d'un monoïde additif, l'élément (addition de k termes) tandis que l'algorithme d'exponentiation rapide permet de calculer, pour tout entier k et élément g d'un monoïde multiplicatif, l'élément (multiplication de k termes). Autrement dit, exprimés dans le langage des monoïdes, ces deux algorithmes sont strictement identiques.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.