Algorithmes de multiplication et de division dans l'Égypte antique

Introduction

La méthode utilisée par les Égyptiens est attestée par le papyrus de Rhind (vers 1600 avant J.-C) qui se réfère à des documents du Moyen Empire (environ 2000 ans avant J. C). Les algorithmes de multiplication et de division sont suggérés par une liste de problèmes. Pour parodier Napoléon, «Du haut de ces algorithmes, 40 siècles vous contemplent !».

Dans cette présentation, la méthode sera réinterprétée dans un langage moderne. Les algorithmes sont exprimés en langage Mathematica et les idées guides sont formulées en commentant un exemple numérique.

Soit, par exemple, le produit 181×273 à effectuer. Une méthode consiste à exprimer le premier nombre en base 2 :

181×273 = (128 + 32 + 16 + 4 + 1)×273

= 1×273 + 4×273 + 16×273 + 32×273 + 128×273
= 273 + 22×273 + 24×273 + 25×273 + 27×273

Pour terminer le calcul, deux opérations arithmétiques suffisent : la multiplication de nombres par 2 et l’addition de nombres. En particulier, elle ne fait pas appel à des tables de multiplication.

Expression d'un entier en base 2

Pour convertir l’entier 181 en base 2, on peut procéder comme suit :

1-ère étape

  • Dresser la liste des puissances de 2, tant qu’elles ne sont pas supérieures à 181 :

a=181; i=1; d[i]=1; out={};
While[ d[i]≤a, AppendTo[out, d[i]]; d[i+1]=d[i]*2; i++];
TableForm[out]

1
2
4
8
16
32
64
128

2-ème étape

On passe en revue chaque ligne, pour déterminer celles qui doivent être biffées :

  • Dans la colonne 2, on trouve le chiffre en base 2 ; un 0 indique que la ligne est biffée ;
  • dans la colonne 3, on trouve le reste qui n’est pas encore converti ; le dernier reste doit être nul ;
    • puisque 181≥128, il faut prendre 128 et former la différence 181-128=53 ;
    • puisque 53<64, il faut biffer 64 ;
    • puisque 53≥32, il faut prendre 32 et former la différence 53-32=21 ;
    • puisque 21≥16, il faut prendre 16 et former la différence 21-16=5 ;
    • puisque 5<8, il faut biffer 8 ;
    • puisque 5≥4, il faut prendre 4 et former la différence 5-4=1 ;
    • puisque 1<2, il faut biffer 2 ;
    • puisque 1≥1, prendre 1 et former la différence 1-1=0.

e=a; n=i-1; out={};
Do[

If[ e≥d[i], f[i]=1;e=e-d[i], f[i]=0];
AppendTo[out, {d[i], f[i], e}],

{i, n, 1, -1}];
TableForm[out]

128 1 53
64 0 53
32 1 21
16 1 5
8 0 5
4 1 1
2 0 1
1 1 0

Multiplication égyptienne

Pour multiplier 181 par 273, on peut procéder comme suit :

1-ère étape

  • Dans la première colonne : dresser la liste des puissances de 2, tant qu’elles ne sont pas supérieures à 181 ;
  • dans la deuxième colonne : en regard de 2, 4, 8, ..., par doublements successifs, on calcule 2×273, 4×273, 8×273, ...

a=181; b=273; i=1; d[i]=1; g[1]=b; out={};
While[ d[i]≤a,

AppendTo[out, {d[i], g[i]}];
d[i+1]=d[i]*2; g[i+1]=g[i]*2;

i++];
TableForm[out]

1 273
2 546
4 1092
8 2184
16 4368
32 8736
64 17472
128 34944

2-ème étape

  • colonnes 1 à 3 : on exprime 181 en base 2 (voir les commentaires plus haut) ;
  • colonne 4 : on ne retient que les multiples de 273 situés sur des lignes non biffées.

n=i-1; e=a; out={};
Do[

If[ e≥d[i], f[i]=1;e=e-d[i];AppendTo[out, {d[i],f[i],e,g[i]}],

f[i]=0;AppendTo[out, {d[i],f[i],e}] ],

{i, n, 1, -1}];
TableForm[out]

128 1 53 34944
64 0 53
32 1 21 8736
16 1 5 4368
8 0 5
4 1 1 1092
2 0 1
1 1 0 273

3-ème étape

  • colonne 1 : les multiples de 273 qui ont été retenus doivent être additionnés ;
  • colonne 2 : sommes partielles ; la dernière somme est le résultat final.

h=0; out={};
Do[

If[ f[i]==1, h=h+g[i]; AppendTo[out, {g[i], h}] ],

{i, 1, n}];
TableForm[out]

273 273
1092 1365
4368 5733
8736 14469
34944 49413

Division égyptienne

Il s’agit d’une division euclidienne : le quotient est un entier et le reste est entier. Alors que les Égyptiens savaient manipuler certaines fractions, dans le papyrus de Rhind, le reste est généralement ignoré.

A titre d’exemple, considérons le quotient de 95432 par 285. Pour diviser 95432 par 285, on peut procéder comme suit.

1-ère étape

  • dans la première colonne : multiplier 285 répétitivement par 2, tant que le résultat n’est pas supérieur à 95432 ;
  • dans la deuxième colonne : en regard, écrire les multiples de 2.

a=95432; b=285; i=1; d[i]=1; g[1]=b; out={};
While[ g[i]≤a,

AppendTo[out, {g[i], d[i]}];
d[i+1]=d[i]*2; g[i+1]=g[i]*2;

i++];
TableForm[out]

285 1
570 2
1140 4
2280 8
4560 16
9120 32
18240 64
36480 128
72960 256

2-ème étape

  • dans la colonne 2, un 0 signifie que la ligne doit être biffée ;
  • dans la colonne 3 se trouve le reste qui sera, si possible, traité plus bas ; le dernier reste est le reste de la division.
    • puisque 95432≥72960, il faut prendre 256 et former la différence 95432-72960=22472 ;
    • puisque 22472<36480, il faut biffer 128 ;
    • puisque 22472≥18240, il faut prendre 64 et former la différence 22472-18240=4232 ;
    • puisque 4232<9120, il faut biffer 32 ;
    • puisque 4232<4560, il faut biffer 16 ;
    • puisque 4232≥2280, il faut prendre 8 et former la différence 4232-2280=1952 ;
    • puisque 1952≥1140, il faut prendre 4 et former la différence 1952-1140=812 ;
    • puisque 812≥570, il faut prendre 2 et former la différence 812-570=242 ;
    • puisque 242<285, il faut biffer 1 ;
    • le reste de la division est 242.
  • colonne 4 : on ne retient que les multiples de 2 situés sur des lignes non biffées.

n=i-1; e=a; out={};
Do[

If[ e≥g[i], f[i]=1; e=e-g[i]; AppendTo[out, {g[i],f[i],e,d[i]}],

f[i]=0; AppendTo[out, {g[i], f[i], e}] ],

{i, n, 1, -1}];
TableForm[out]

72960 1 22472 256
36480 0 22472
18240 1 4232 64
9120 0 4232
4560 0 4232
2280 1 1952 8
1140 1 812 4
570 1 242 2
285 0 242

3-ème étape

  • colonne 1 : les multiples de 2 qui ont été retenus doivent être additionnés ;
  • colonne 2 : sommes partielles ; la dernière somme est le quotient.
  • Réponse : le quotient est de 334 et le reste est de 242.

h=0; out={};
Do[

If[ f[i]==1, h=h+d[i]; AppendTo[out, {d[i], h}] ],

{i, 1, n}];
TableForm[out]

2 2
4 6
8 14
64 78
256 334

Justification de la division égyptienne

Une propriété de la division euclidienne est la suivante :

Si  r = a - b·q  avec  0 ≤ r < b,

alors  r  est le reste de la division de  a  par  b,  et  q  est le quotient de  a  par  b.

En effet, dans la 2-ème étape, colonne 3, la suite des restes

r0 = 95423 (implicitement)

r1 = 22472 = 95432 - 256×285;   r1≥0 ;

r2 = ...

...

r9 = 95432-256×285-64×285-8×285-4×285-2×285 = 95432-285×(256+64+8+4+2) = 242;   r9≥0 ;

est décroissante ; elle est achevée, car r9 < 285.

Il s’ensuit que, pour la division de 95432 par 285, le reste est r9 et le quotient est (256+64+8+4+2).

Version PDF   |   Contact   |   Accueil   >   Mathématiques, degré secondaire II