Algorithmes de multiplication de nombres entiers stockés sous forme de chaînes de caractères.

 Les algorithmes décrits ci-dessous ont été inventés par Jakow Trachtenberg, né le 17 juin 1888 à Odessa en Russie. Ils ont été développés et mis au point pendant sa captivité dans un camp de concentration allemand lors de la 2ème guerre mondiale, et ceci sans papier ni crayon. Après son évasion, Trachtenberg approfondira ses idées en Suisse.

Le grand avantage de ces algorithmes est qu'ils peuvent s'appliquer simplement à des nombres stockés sous forme de chaînes de caractères. Partant de là, il est possible manipuler de très grands nombres (de 255 chiffres en TP).


x

 N multiplié par x

2

 chaque chiffre est multiplié par 2 (à partir du chiffre des unités et ajouté au report éventuel). 
Ex : 175 * 2 = ?
   5*2=10 donne 0 comme chiffre le plus à droite et un report de 1
   7*2=14 augmenté du report de 1 fournit 15 et donc le chiffre 5 et un report de 1
   1*2=2 augmenté du report fournit le chiffre 3
   La réponse est : 350

3

 * le chiffre le plus à droite dans la réponse est 10 moins le chiffre le plus à droite dans le nombre de départ doublé et augmenté de 5 s'il est impair;
* chaque chiffre intermédiaire vaut 9 diminué du chiffre correspondant dans le nombre de départ doublé puis augmenté de la moitié de son voisin de droite et augmenté de 5 si le chiffre est impair;
* le chiffre le plus à gauche dans la réponse est la moitié du chiffre le plus à gauche dans le nombre de départ diminué de 2.
Ex : 1275 * 3 = ?
   (10-5)*2=10 augmenté de 5 puisque le dernier chiffre (5) est impair. On obtient donc 5 avec un report de 1
   (9-7)*2+[5/2]=6 augmenté du report de 1 et de 5 car 7 est impair. On obtient donc 2 et un report de 1
   (9-2)*2+[7/2]=17 plus le report de 1. On obtient donc 8 et un report de 1
   (9-1)*2+[2/2]=17 augmenté du report de 1 et de 5 car 1 est impair. On obtient donc 3 et un report de 2
   [1/2]-2=-2 plus le report de 2 fournit 0.
    La réponse est : 03825

4

 * le chiffre le plus à droite dans la réponse est 10 moins le chiffre le plus à droite dans le nombre de départ doublé et augmenté de 5 s'il est impair;
* chaque chiffre intermédiaire vaut 9 diminué du chiffre correspondant dans le nombre de départ augmenté de la moitié de son voisin de droite et augmenté de 5 si le chiffre est impair;
* le chiffre le plus à gauche dans la réponse est la moitié du chiffre le plus à gauche dans le nombre de départ diminué de 1.

Ex : 1275 * 4 = ?
   (10-5)=5 augmenté de 5 puisque le dernier chiffre (5) est impair. On obtient donc 0 avec un report de 1
   (9-7)+[5/2]=4 augmenté du report de 1 et de 5 car 7 est impair. On obtient donc 0 et un report de 1
   (9-2)+[7/2]=10 plus le report de 1. On obtient donc 1 et un report de 1
   (9-1)+[2/2]=9 augmenté du report de 1 et de 5 car 1 est impair. On obtient donc 5 et un report de 1
   [1/2]-1=-1 plus le report de 1 fournit 0.
   La réponse est : 05100

5

 * compléter le nombre par un '0' en 1ère position;
* le chiffre le plus à droite dans la réponse est 0 si le chiffre le plus à droite dans le nombre de départ est pair sinon il vaut 5;
* chaque chiffre intermédiaire vaut la moitié de son voisin de droite et augmenté de 5 si le chiffre est impair;
Ex : 1275 * 5 = ?
   Le premier chiffre vaut 5 puisque 5 est impair
   [5/2]=2 augmenté de 5 car 7 est impair. On obtient donc 7
   [7/2]=3 On obtient donc 3 et un report de 1
   [2/2]=1 augmenté de 5 car 1 est impair. On obtient donc 6
   [1/2]=0 On obtient donc 0
    La réponse est : 06375

6

 * compléter le nombre par un '0' en 1ère position;
* le chiffre le plus à droite dans la réponse est le chiffre le plus à droite dans le nombre de départ augmenté de 5 s'il est impair;
* chaque chiffre intermédiaire vaut le chiffre correspondant dans le nombre de départ augmenté de la moitié de son voisin de droite et augmenté de 5 si le chiffre est impair; 
Ex : 1275 * 6 = ?
   5 augmenté de 5 puisque le dernier chiffre est impair. On obtient donc 0 et un report de 1
   7+[5/2]=9 augmenté du report de 1 et de 5 car 7 est impair. On obtient donc 5 et un report de 1
   2+[7/2]=5 plus le report de 1. On obtient donc 6
   1+[2/2]=2 augmenté de 5 car 1 est impair. On obtient donc 7
   0+[1/2]=0 On obtient donc 0
   La réponse est : 7650

7

 * le chiffre le plus à droite dans la réponse est le chiffre le plus à droite dans le nombre de départ doublé et augmenté de 5 s'il est impair.
* chaque chiffre intermédiaire vaut le double du chiffre correspondant dans le nombre de départ augmenté de la moitié de son voisin de droite et augmenté de 5 si le chiffre est impair.
* le chiffre le plus à gauche dans la réponse est la moitié du chiffre le plus à gauche dans le nombre de départ. 
Ex : 1275 * 7 = ?
   5*2=10 augmenté de 5 puisque le dernier chiffre (5) est impair. On obtient donc 5 avec un report de 1
   7*2+[5/2]=16 augmenté du report de 1 et de 5 car 7 est impair. On obtient donc 2 et un report de 2
   2*2+[7/2]=7 plus le report de 2. On obtient donc 9
   1*2+[2/2]=3 augmenté de 5 car 1 est impair. On obtient donc 8
   [1/2]=0 fournit 0.
   La réponse est : 08925

8

 * le chiffre le plus à droite dans la réponse est 10 moins le chiffre le plus à droite dans le nombre de départ doublé;
* chaque chiffre intermédiaire vaut 9 diminué du chiffre correspondant dans le nombre de départ doublé puis augmenté de son voisin de droite;
* le chiffre le plus à gauche dans la réponse est le chiffre le plus à gauche dans le nombre de départ diminué de 2. 
Ex : 1275 * 8 = ?
   (10-5)*2=10 On obtient donc 0 avec un report de 1
   (9-7)*2+5=9 augmenté du report de 1. On obtient donc 0 et un report de 1
   (9-2)*2+7=21 augmenté du report. On obtient donc 2 et un report de 2
   (9-1)*2+2=18 augmenté du report. On obtient donc 0 et un report de 2
   1-2=-1 plus le report de 2 fournit 1.
   La réponse est : 10200

9

 * le chiffre le plus à droite dans la réponse est 10 moins le chiffre le plus à droite dans le nombre de départ;
* Chaque chiffre intermédiaire vaut 9 diminué du chiffre correspondant dans le nombre de départ augmenté de son voisin de droite;
* le chiffre le plus à gauche dans la réponse est le chiffre le plus à gauche dans le nombre de départ diminué de 1. 
Ex : 1275 * 9 = ?
   10-5=5 On obtient donc 5
   (9-7)+5=7 On obtient donc 7
   (9-2)+7=14 On obtient donc 4 et un report de 1
   (9-1)+2=10 augmenté du report de 1. On obtient donc 1 et un report de 1
   1-1=0 plus le report de 1 fournit 1.
   La réponse est : 11475

10

 * le chiffre le plus à droite dans la réponse est 0;
* chaque chiffre intermédiaire est le voisin de droite;
* le chiffre le plus à gauche dans la réponse est le chiffre le plus à gauche dans le nombre de départ.

11

 * le chiffre le plus à droite dans la réponse est le chiffre le plus à droite dans le nombre de départ;
* chaque chiffre intermédiaire vaut le chiffre correspondant dans le nombre de départ augmenté de son voisin de droite
* le chiffre le plus à gauche dans la réponse est le chiffre le plus à gauche dans le nombre de départ.



Le programme Pascal ci-dessous pourrait être amélioré en terme de nombre de lignes. Je ne l'ai pas optimisé, voulant rester proche de l'algorithme pour gagner en lisibilité. Il contient aussi des fonctions pour ajouter, soustraire et multiplier n'importe quels nombres entiers stockés sous forme de chaînes de caractères. 



PROGRAM Trachtenberg;

USES CRT;

FUNCTION Char2Byte(C:CHAR):BYTE;(* Transforme un caractère en byte *)
BEGIN
Char2Byte:=POS(C,'0123456789')-1;
END;

FUNCTION Byte2Char(i:BYTE):CHAR;(* Transforme un byte en caractère *)
VAR Chiffres:STRING[10];
BEGIN
Chiffres:='0123456789';
IF i>9 THEN Byte2Char:='?'
ELSE Byte2Char:=Chiffres[i+1];
END;

FUNCTION Add(S1,S2:STRING):STRING;(* Ajoute les 2 nombres *)
VAR L1,L2,k,Report,i:BYTE;
    S:STRING;
BEGIN
L1:=LENGTH(S1);L2:=LENGTH(S2);
IF L1>L2 THEN FOR i:=L2 TO L1-1 DO S2:='0'+S2
ELSE FOR i:=L1 TO L2-1 DO S1:='0'+S1;
L1:=LENGTH(S1);
Report:=0;
S:='';
FOR i:=L1 DOWNTO 1 DO
  BEGIN
  k:=Char2Byte(S1[i])+Char2Byte(S2[i])+Report;
  S:=Byte2Char(k MOD 10)+S;
  Report:=k DIV 10;
  END;
S:=Byte2Char(Report)+S;
IF S[1]='0' THEN DELETE(S,1,1);
Add:=S;
END;

FUNCTION Soust(S1,S2:STRING):STRING;(* Soustrait les 2 nombres *)
VAR L1,L2,Report,i:BYTE;
    k:SHORTINT;
    S:STRING;
BEGIN
L1:=LENGTH(S1);L2:=LENGTH(S2);
IF L1>L2 THEN FOR i:=L2 TO L1-1 DO S2:='0'+S2
ELSE FOR i:=L1 TO L2-1 DO S1:='0'+S1;
L1:=LENGTH(S1);
Report:=0;
S:='';
FOR i:=L1 DOWNTO 1 DO
  BEGIN
  k:=Char2Byte(S1[i])-Char2Byte(S2[i])+Report;
  Report:=0;
  WHILE k<0 DO
    BEGIN
    k:=k+10;
    Report:=Report-1;
    END;
  S:=Byte2Char(k)+S;
  END;
IF S[1]='0' THEN DELETE(S,1,1);
Soust:=S;
END;

FUNCTION Mul2(S:STRING):STRING;(* Multiplie le nombre par 2 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
Report:=0;
FOR i:=LENGTH(S) DOWNTO 1 DO
  BEGIN
  k:=Char2Byte(S[i])*2;
  S2:=Byte2Char(Report+k MOD 10)+S2;
  Report:=k DIV 10;
  END;
S2:=Byte2Char(Report)+S2;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul2:=S2;
END;

FUNCTION Mul3(S:STRING):STRING;(* Multiplie le nombre par 3 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
j:=Char2Byte(S[LENGTH(S)]);
k:=2*(10-j);
IF j MOD 2=1 THEN k:=k+5;
Report:=k DIV 10;
k:=k MOD 10;
S2:=Byte2Char(k)+S2;
FOR i:=LENGTH(S)-1 DOWNTO 1 DO
  BEGIN
  j:=Char2Byte(S[i]);
  j2:=Char2Byte(S[i+1]);
  k:=(9-j)*2+j2 DIV 2+Report;
  IF j MOD 2=1 THEN k:=k+5;
  Report:=k DIV 10;
  k:=k MOD 10;
  S2:=Byte2Char(k)+S2;
  END;
j:=Char2Byte(S[1]);
k:=j DIV 2-2+Report;
S2:=Byte2Char(k)+S2;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul3:=S2;
END;

FUNCTION Mul4(S:STRING):STRING;(* Multiplie le nombre par 4 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
j:=Char2Byte(S[LENGTH(S)]);
k:=10-j;
IF j MOD 2=1 THEN k:=k+5;
Report:=k DIV 10;
k:=k MOD 10;
S2:=Byte2Char(k)+S2;
FOR i:=LENGTH(S)-1 DOWNTO 1 DO
  BEGIN
  j:=Char2Byte(S[i]);
  j2:=Char2Byte(S[i+1]);
  k:=9-j+j2 DIV 2+Report;
  IF j MOD 2=1 THEN k:=k+5;
  Report:=k DIV 10;
  k:=k MOD 10;
  S2:=Byte2Char(k)+S2;
  END;
j:=Char2Byte(S[1]);
k:=j DIV 2-1+Report;
S2:=Byte2Char(k)+S2;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul4:=S2;
END;

FUNCTION Mul5(S:STRING):STRING;(* Multiplie le nombre par 5 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
S:='0'+S;
j:=Char2Byte(S[LENGTH(S)]);
IF j MOD 2=1 THEN S2:='5'
ELSE S2:='0';
Report:=0;
FOR i:=LENGTH(S)-1 DOWNTO 1 DO
  BEGIN
  j:=Char2Byte(S[i]);
  j2:=Char2Byte(S[i+1]);
  k:=j2 DIV 2+Report;
  IF j MOD 2=1 THEN k:=k+5;
  Report:=k DIV 10;
  k:=k MOD 10;
  S2:=Byte2Char(k)+S2;
  END;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul5:=S2;
END;

FUNCTION Mul6(S:STRING):STRING;(* Multiplie le nombre par 6 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
S:='0'+S;
j:=Char2Byte(S[LENGTH(S)]);
IF j MOD 2=1 THEN k:=j+5
ELSE k:=j;
Report:=k DIV 10;
k:=k MOD 10;
S2:=Byte2Char(k)+S2;
FOR i:=LENGTH(S)-1 DOWNTO 1 DO
  BEGIN
  j:=Char2Byte(S[i]);
  j2:=Char2Byte(S[i+1]);
  k:=j+j2 DIV 2+Report;
  IF j MOD 2=1 THEN k:=k+5;
  Report:=k DIV 10;
  k:=k MOD 10;
  S2:=Byte2Char(k)+S2;
  END;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul6:=S2;
END;

FUNCTION Mul7(S:STRING):STRING;(* Multiplie le nombre par 7 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
S:='0'+S;
j:=Char2Byte(S[LENGTH(S)]);
IF j MOD 2=1 THEN k:=2*j+5
ELSE k:=2*j;
Report:=k DIV 10;
k:=k MOD 10;
S2:=Byte2Char(k)+S2;
FOR i:=LENGTH(S)-1 DOWNTO 1 DO
  BEGIN
  j:=Char2Byte(S[i]);
  j2:=Char2Byte(S[i+1]);
  k:=2*j+j2 DIV 2+Report;
  IF j MOD 2=1 THEN k:=k+5;
  Report:=k DIV 10;
  k:=k MOD 10;
  S2:=Byte2Char(k)+S2;
  END;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul7:=S2;
END;

FUNCTION Mul8(S:STRING):STRING;(* Multiplie le nombre par 8 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
k:=20-2*Char2Byte(S[LENGTH(S)]);
Report:=k DIV 10;
k:=k MOD 10;
S2:=Byte2Char(k)+S2;
FOR i:=LENGTH(S)-1 DOWNTO 1 DO
  BEGIN
  j:=Char2Byte(S[i]);
  j2:=Char2Byte(S[i+1]);
  k:=(9-j)*2+j2+Report;
  Report:=k DIV 10;
  k:=k MOD 10;
  S2:=Byte2Char(k)+S2;
  END;
j:=Char2Byte(S[1]);
k:=j-2+Report;
S2:=Byte2Char(k)+S2;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul8:=S2;
END;

FUNCTION Mul9(S:STRING):STRING;(* Multiplie le nombre par 9 *)
VAR S2:STRING;
    Report,i,j,j2,k:BYTE;
BEGIN
S2:='';
k:=10-Char2Byte(S[LENGTH(S)]);
Report:=k DIV 10;
k:=k MOD 10;
S2:=Byte2Char(k)+S2;
FOR i:=LENGTH(S)-1 DOWNTO 1 DO
  BEGIN
  j:=Char2Byte(S[i]);
  j2:=Char2Byte(S[i+1]);
  k:=(9-j)+j2+Report;
  Report:=k DIV 10;
  k:=k MOD 10;
  S2:=Byte2Char(k)+S2;
  END;
j:=Char2Byte(S[1]);
k:=j-1+Report;
S2:=Byte2Char(k)+S2;
IF S2[1]='0' THEN DELETE(S2,1,1);
Mul9:=S2;
END;

FUNCTION Mul10(S:STRING):STRING;(* Multiplie le nombre par 10 *)
BEGIN
Mul10:=S+'0';
END;

PROCEDURE Swap(VAR S1,S2:STRING);(* Inverse les 2 chaînes *)
VAR Tmp:STRING;
BEGIN
Tmp:=S1;
S1:=S2;
S2:=Tmp
END;


FUNCTION Multi(C:CHAR;S:STRING):STRING;(* Multiplie le nombre par un 'chiffre' *)
BEGIN
CASE C OF
  '0': Multi:='0';
  '1': Multi:=S;
  '2': Multi:=Mul2(S);
  '3': Multi:=Mul3(S);
  '4': Multi:=Mul4(S);
  '5': Multi:=Mul5(S);
  '6': Multi:=Mul6(S);
  '7': Multi:=Mul7(S);
  '8': Multi:=Mul8(S);
  '9': Multi:=Mul9(S);
END;
END;

FUNCTION Mult(S1,S2:STRING):STRING;(* Multiplie 2 nombres *)
VAR S,S0:STRING;
    i:BYTE;
BEGIN
IF LENGTH(S1)>LENGTH(S2) THEN Swap(S1,S2);(* S1 est la chaîne la plus courte *)
S:='';S0:='';
FOR i:=LENGTH(S1) DOWNTO 1 DO
  BEGIN
  S:=Add(S,Multi(S1[i],S2)+S0);
  S0:=S0+'0';
  END;
Mult:=S
END;

VAR S,S1,S2:STRING;

BEGIN
CLRSCR;
WRITE('Nbre=');READLN(S);
WRITELN(S,' * 2 = ',Mul2(S));
WRITELN(S,' * 3 = ',Mul3(S));
WRITELN(S,' * 4 = ',Mul4(S));
WRITELN(S,' * 5 = ',Mul5(S));
WRITELN(S,' * 6 = ',Mul6(S));
WRITELN(S,' * 7 = ',Mul7(S));
WRITELN(S,' * 8 = ',Mul8(S));
WRITELN(S,' * 9 = ',Mul9(S));
WRITELN(Mul2(S)+' + '+Mul8(S)+' = ',Add(Mul2(S),Mul8(S)));
S1:='1234';S2:='903';
WRITELN(S1+' * '+S2+' = ',Mult(S1,S2));
WRITELN(Mul7(S)+' - '+Mul2(S)+' = ',Soust(Mul7(S),Mul2(S)));
END.
Page précédente.
Page d'accueil.