# Technique de multiplication dite russe

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.

## Algorithme

En pseudo code, l'algorithme de multiplication dite russe peut s'écrire :
Note : les opérations effectuées ici sont des opérations sur des entiers et sont à valeurs dans les entiers.

## Exemple de multiplications dites russes

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=6\times 2+1$ 13 divisé par 2 : le quotient est 6, le reste est 1, | 238, | 238 |
| $6=3\times 2+0$ 6 divisé par 2 : le quotient est 3, le reste est 0, | $238\times 2=476$, | Le reste est nul, pas d'ajout du multiple. 238 |
| $3=1\times 2+1$ 3 divisé par 2 : le quotient est 1, le reste est 1, | $476\times 2=952$, | Le reste est non nul, on ajoute le multiple obtenu à cette étape : $238+952=1190$ |
| $1=0\times 2+1$ 1 divisé par 2 : le quotient est 0, le reste est 1. Le quotient est nul, on stoppe l'algorithme. | $952\times 2=1904$ | Le reste est non nul, on ajoute le multiple obtenu à cette étape : $1190+1904=3094$ |
| $13\times 238=3094$ |||
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é.

## Algorithme graphique

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 à :
* a) si le multiplicateur est pair, prendre la moitié inférieure du rectangle et la coller sur un côté (on transforme ainsi un rectangle 2n x p en un rectangle n x 2p) ; b) si le multiplicateur est impair, enlever d'abord la dernière ligne et la mettre à part, ce qui ramène au cas précédent 1.a) ;
* recommencer jusqu'à n'obtenir qu'une seule ligne ;
* additionner toutes les lignes mises à part.

## Lien avec l'algorithme d'exponentiation rapide

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 $k\cdot g=g+\dotsb +g$ (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 $g^{k}=g\times \dotsb \times g$ (multiplication de k termes). Autrement dit, exprimés dans le langage des monoïdes, ces deux algorithmes sont strictement identiques.