Technique de multiplication dite russe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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 fin si
        x = x / 2
        y = y * 2
     Fin tant que
     Retourner r
  Fin fonction  

Note: les opérations effectuées ici sont des opérations sur des entiers et sont à valeurs dans les entiers.

Si x est impair, i.e. si il existe k entier naturel tel que x=2*k+1, alors x/2 = k.

Exemple de multiplications dites Russes[modifier | modifier le code]

13 x 238 on écrit

13/2 = quotient 6 reste 1, 238, 238
6/2 = quotient 3 reste 0, (476 pour mémoire), 238
3/2 = quotient 1 reste 1, 952, 1190
1/2 = quotient 0 reste 1, 1904 (stop : le quotient est nul), 3094

13 × 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[modifier | modifier le code]

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.

Voir aussi[modifier | modifier le code]