Multiplication égyptienne et puissances

Multiplication égyptienne

Le système de numération égyptien permet de faire simplement des additions mais pose problème lorsqu'il s'agit de faire des multiplications. Les scribes avaient donc imaginé un moyen astucieux de remplacer les multiplications par des additions. Dans le but de réduire le plus possible le nombre d'additions à effectuer, ils se servaient des puissances de 2. Par exemple, pour calculer 27x26, on peut ajouter 25 fois 27 à 27, ce qui représente 25 additions. L'idée des scribes égyptiens consistait à compléter le tableau suivant :

Tous les résultats sont obtenus en doublant le résultat précédent, c'est à dire en faisant 4 additions. Il suffit ensuite de recomposer 26 en utilisant les puissances de 2, on trouve 26=16+8+2 et de calculer la somme des termes correspondants dans le tableau, c'est à dire 432+216+54=702 qui est bien le produit de 17 par 26. On a fait 2 nouvelles additions, plus 4 additions pour trouver la décomposition de 26. Au total, nous avons effectué la multiplication en faisant 10 additions au lieu de 25.

Vous pouvez voir le détail d'une multiplication égyptienne sur le site rigolmath.

Nous allons écrire un programme Minilogo qui effectue des multiplications à la façon des égyptiens. Le seul problème est de déterminer les puissances de 2 à ajouter pour obtenir un nombre. Il suffit de penser à la numération en base 2 pour se persuader que ce problème a bien une solution. Par exemple, en base 2 le nombre 26 s'écrit 11010, ce qui traduit 26=1x2⁴+1x2³+0x2²+1x2¹+0x2⁰, c'est à dire le 26=16+8+2 utilisé dans l'exemple précédent. Or pour trouver les chiffres formant un nombre en base 2 il suffit de faire une suite de divisions euclidiennes et de conserver les restes qui donnent les chiffres en partant de la droite.

Ainsi, pour 26, la division par 2 donne 13 et un reste de 0, puis pour 13 on obtient 6 et un reste de 1, puis pour 6 on obtient 3 et un reste de 0, puis pour 3 on obtient 1 et un reste de 1, et enfin pour 1 on obtient 0 et un reste de 1. Les restes sont donc 01011, en réécrivant dans l'ordre on a bien 11010.

Pour écrire notre programme nous allons utiliser les variables suivantes:

• a et b pour les deux nombres à multiplier
• pa pour les produits de a par les puissances de 2 (obtenus par doublement)
• q et r pour les résultats des divisions euclidiennes
• s pour le total donnant le produit

Ceci nous donne le programme :

dans a 27 dans b 26
aff(a," x ",b," = ")
dans pa a
dans s 0
tantque b>0 [
dans q ent(b/2) dans r b-2*q 
si r=1 [dans s s+pa]
dans b q dans pa pa+pa
]
aff s

Vous pouvez tester ce script dans la feuille de calcul Minilogo en effectuant un copier-coller.

Puissances

L'idée des scribes égyptiens pourrait sembler n'être qu'une simple curiosité. Elle est pourtant revenue à l'ordre du jour grâce à l'informatique. En effet on est parfois amener à calculer des puissances avec des exposants très élevés (par exemple dans les problèmes de cryptage à clef révélée). Calculer xⁿ peut se faire en multipliant n-1 fois x par x. Ce nombre de produits peut être considérablement réduit en utilisant la technique des scribes égyptiens et en remplaçant simplement double par carré.

Exercice

Ecrire un programme Minilogo qui calcule xⁿ de cette façon. (feuille de calcul Minilogo)

Une solution est disponible ici.

Le nombre e

La suite u définie par u(n)=(1+1/n)ⁿ converge vers le nombre e (environ 2,718281828).

Exercice

Ecrire un programme Minilogo qui permet de calculer u(n) pour de grandes valeurs n. Vérifier ainsi que u converge bien vers e. ( feuille de calcul Minilogo)

Une solution est disponible ici.