Section courante

A propos

Section administrative du site

Introduction

La multiplication russe, aussi surnommée multiplication par décalage de bits, est une technique de multiplication de deux nombres basée sur le principe d'une multiplication par 2. Elle était également connue des anciens Égyptiens environ 2 000 avant Jésus-Christ. La multiplication par 2 correspond à un décalage de bits vers la gauche de 1. Ainsi, cette manière de calculer permettra d'effectuer une multiplication sans effectuer d'opération d'addition et sera également beaucoup plus rapide d'exécution. En assembleur, par exemple sur des microprocesseurs de la famille des 80x86 (du 8088 au 80386DX) une opération de décalage de bits prend rarement plus que 2 cycles d'horloges pour être complétée et une addition peut prendre entre 3 et 24 cycles d'horloge et une multiplication peut prendre entre 9 et 118 cycles d'horloges.

L'algorithme se base sur le principe qu'on aura une division par 2 (décalage d'un bit vers la gauche) de la valeur de la variable A et et qu'on aura une multiplication par 2 (d'un décalage de bits vers la droite) de la variable B tant que la variable A soit supérieur à 0. S'il y a un restant à la division, une addition est faite dans la variable C. Si par exemple, on souhaite multiplier 32 (A) par 14 (B) pour obtenir C, on procédera de la façon suivante :

A A quotient 2 A ∩ 2 B C = C + B x (A ∩ 1) C
32 32 % 2 = 0 32 ∩ 1 = 0 14 C + B x 0 = 0 0 + 0 = 0
16 16 % 2 = 0 16 ∩ 1 = 0 28 C + B x 0 = 0 0 + 0 = 0
8 8 % 2 = 0 8 ∩ 1 = 0 56 C + B x 0 = 0 0 + 0 = 0
4 4 % 2 = 0 4 ∩ 1 = 0 112 C + B x 0 = 0 0 + 0 = 0
2 2 % 2 = 0 2 ∩ 1 = 0 224 C + B x 0 = 0 0 + 0 = 0
1 1 % 2 = 1 1 ∩ 1 = 1 448 C + B x 1 = 448 0 + 448 = 448

Si par exemple, on souhaite multiplier 13 (A) par 17 (B) pour obtenir C, on procédera de la façon suivante :

A A quotient 2 A ∩ 2 B C = C + B x (A ∩ 1) C
13 13 % 2 = 1 13 ∩ 1 = 1 17 C + B x 1 = 17 0 + 17 = 17
6 6 % 2 = 0 6 ∩ 1 = 0 34 C + B x 0 = 17 17 + 0 = 17
3 3 % 2 = 1 3 ∩ 1 = 1 68 C + B x 1 = 85 17 + 68 = 85
1 1 % 2 = 1 1 ∩ 1 = 1 136 C + B x 1 = 221 85 + 136 = 221

Algorithme

On aura donc un algorithme comme ceci :

MODULE Multiplication(x,y)
   r ← 0
   BOUCLE TANT QUE x ≠ 0
      SI x est impair ALORS
         r ← r + y
         x ← x - 1
      FIN SI
      x ← x / 2
      y ← y x 2
   FIN BOUCLE TANT QUE
   RETOURNER r

Exemples

L'exemple suivant, écrit en Free Pascal, permet d'effectuer la multiplication de nombre entier avec des multiplication et des divisions par 2 :

  1. Program MultiplicationRusseSamples;
  2.  
  3. Function Mult(x,y:Integer):Integer;
  4. Var
  5.  r:Integer ;
  6. Begin
  7.  r := 0;
  8.  While x <> 0 do Begin
  9.   If Odd(x)Then Begin
  10.    r := r + y;
  11.    x := x - 1;
  12.   End;
  13.   x := x div 2;
  14.   y := y * 2;
  15.  End;
  16.  Mult := r;
  17. End;
  18.  
  19. BEGIN
  20.  WriteLn('8 x 8 = ',8*8,', ',Mult(8,8));
  21.  WriteLn('32 x 14 = ',32*14,', ',Mult(32,14));
  22.  WriteLn('13 x 17 = ',13*17,', ',Mult(13,17));
  23. END.

on obtiendra le résultat suivant :

8 x 8 = 64, 64
32 x 14 = 448, 448
13 x 17 = 221, 221

L'exemple suivant, écrit en Free Pascal, permet d'effectuer la multiplication de nombre entier avec des décalages de bits :

  1. Program MultiplicationRusseShiftSamples;
  2.  
  3. Function Mult(x,y:Integer):Integer;
  4. Var
  5.  r:Integer ;
  6. Begin
  7.  r := 0;
  8.  While x <> 0 do Begin
  9.   If x and 1 = 1 Then Begin
  10.    r := r + y;
  11.    x := x - 1;
  12.   End;
  13.   x := x shr 1;
  14.   y := y shl 1;
  15.  End;
  16.  Mult := r;
  17. End;
  18.  
  19. BEGIN
  20.  WriteLn('8 x 8 = ',8*8,', ',Mult(8,8));
  21.  WriteLn('32 x 14 = ',32*14,', ',Mult(32,14));
  22.  WriteLn('13 x 17 = ',13*17,', ',Mult(13,17));
  23. END.

on obtiendra le résultat suivant :

8 x 8 = 64, 64
32 x 14 = 448, 448
13 x 17 = 221, 221

En ce basant sur le même principe, on peut ainsi faire une division par 10 en PHP de la manière suivante :

  1. <?php
  2. function Div10($value) {
  3.     $q = ($value >> 1) + ($value >> 2);
  4.     $q = $q + ($q >> 4);
  5.     $q = $q + ($q >> 8);
  6.     $q = $q + ($q >> 16);
  7.     $q = $q >> 3;
  8.     return $q + (($value - ((($q << 2) + $q) << 1)) > 9);
  9. }
  10.  
  11. echo "3456 / 10 = ".Div10(3456)."</br >";
  12. echo "231 / 10 = ".Div10(231)."</br >";
  13. echo "10 / 10 = ".Div10(10)."</br >";
  14. echo "16 / 10 = ".Div10(16)."</br >";
  15. ?>

on obtiendra le résultat suivant :

3456 / 10 = 345
231 / 10 = 23
10 / 10 = 1
16 / 10 = 1

Dernière mise à jour : Dimanche, le 30 avril 2017