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 :

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 :

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.

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, ...

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.

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.

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.

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.

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.

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 :

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

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

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