Multiplication par SHIFTs de 2 naturels.

Voici un algorithme qui réalise l'exploit de multiplier 2 nombres entiers N et M en n'utilisant que des multiplications/divisions par 2.

A chaque étape, N est divisé par 2 (division entière) et M est multiplié par 2. 
Si N est impair, la valeur de M est ajoutée au futur résultat.
Exemple: 321 * 457
N          M
321       457      N est impair donc futur résultat=457
160       914      N est pair donc on n'ajoute pas 914
 80      1828      N est pair donc on n'ajoute pas 1828
 40      3656      N est pair donc on n'ajoute pas 3656
 20      7312      N est pair donc on n'ajoute pas 7312
 10     14624      N est pair donc on n'ajoute pas 14624
  5     29248      N est impair donc futur résultat=457+29248=29705
  2     58496      N est pair donc on n'ajoute pas 58496
  1    116992      N est impair donc résultat=29705+116992=146697

fonction Mult(N, M)
  paramètres: N, M: entier
  à valeur: entier

entier: S
S <-- 0
tant que NOT(N=1) faire
  si N mod 2=1 alors S <-- S+M
  fsi
  N <-- N\2
  M <-- M*2
ftant
S <-- S+M
résultat (S)

fonction Mult(N, M)
  paramètres: N, M: entier
  à valeur: entier

entier: S
S <-- 0
tant que NOT(N=1) faire
  si N=(N SHR 1) SHL 1 alors 
  sinon S <-- S+M
  fsi
  N <-- N SHR 1
  M <-- M SHL 1
ftant
S <-- S+M
résultat (S)

PROGRAM Mult;

VAR M,N,Prod,Tmp : LONGINT;

BEGIN
WRITE('1er nombre=');READLN(M);
WRITE('2ème nombre=');READLN(N);
Prod:=0;
WRITE(N,'*',M,'=');
IF N>M THEN BEGIN
            Tmp:=N;
            N:=M;
            M:=Tmp
		END;
WHILE NOT (N=0) DO
  BEGIN
  IF N<>(N SHR 1) SHL 1 THEN INC(Prod,M);{IF N MOD 2=1 THEN Prod:=Prod+M;}
  N:=N SHR 1;                            {N:=N DIV 2;}
  M:=M SHL 1;                            {M:=M*2;}
  END;
WRITELN(Prod);
END.