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 :

  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.

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 à :

1. 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) ;
2. recommencer jusqu'à n'obtenir qu'une seule ligne ;
3. 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.