Jean Vuillemin Professeur à l’École Normale Supérieure, nous parle ici de multiplication égyptienne. Pourquoi ? Car cet algorithme, très ancien, est redevenu un outil majeur, sous le nom de produit binaire. Le lecteur intéressé par les détails historiques se reportera à la version disponible ici.
En 1703, Leibnitz publie son Explication de l’arithmétique binaire. Il n’utilise qu’une seule page pour donner la table des nombres binaires et décrire les 4 opérations +, −, ×, ÷ (addition, soustraction, multiplication et division). Les trois autres pages font une large place aux considérations historiques : « cette Arithmétique par 0 & 1 se trouve contenir le mystère des lignes d’un ancien Roi & Philosophe nommé Fohy, qu’on croit avoir vécu il y a plus de 4000 ans, et que les Chinois regardent comme le Fondateur de leur Empire et de leur Science ». Pouvait-il deviner que, un peu moins de trois siècles plus tard, des milliards de pucerons utiliseraient ce calcul ?
Et on retrouve cet algorithme de la multiplication sur l’antique Papyrus de Rhind !
L’égyptologue écossais Rhind achète à Louxor un Papyrus qui porte maintenant son nom et qui est conservé au British Museum. Ce Papyrus date des Hyksos (vers – 1800). Son auteur, le scribe Ahmès, indique reprendre des documents du Moyen Empire (vers – 2000).
Ce document contient une initiation à l’Art du Calcul, avec près d’une centaine d’exemples pratiques, explicites et instructifs. Faisons abstraction des premières lectures – allez voir l’article de Jean Vuillemin qui étudie le sujet en détail – et ignorons tout ce qui concerne les fractions et le texte illustratif. Le fragment de fond ainsi extrait contient une dizaine d’exemples de produits entiers avec un algorithme commun qui est la Multiplication égyptienne. Cet algorithme jusqu’à aujourd’hui tient une place unique dans l’Histoire du Calcul.
L’approche décrite réduit la multiplication à une suite d’opérations primitives, exclusivement déterminée par les valeurs des opérandes entiers. Elle est donc indépendante du choix de la numération (base de représentation des nombres), modulo les trois opérations primitives que nous allons voir.
Regardons comment ça marche !
Un peu de patience et d’attention, vous verrez ce n’est pas dur… Calculons le carré de 12, donc 12 * 12 en base 10. Le point clé est que nous ne « savons pas » faire de multiplication. Ici, on a juste le droit de diviser et multiplier par deux, et faire des additions.
On cherche avec cet algorithme à obtenir a*b (la multiplication de a par b). Pour cela, on effectue le calcul en 3 colonnes comme sur la figure ci-dessous, avec une ligne pour chaque étape (itération). On démarre la 1ère ligne avec la valeur de a et b de départ (ici 12 * 12).
On calcule une nouvelle ligne ainsi, dans la colonne de a en calculant la division entière par 2 de la dernière valeur (ici 12 divisé par 2 = 6). On passe à la ligne suivante dans la colonne b en dupliquant b, ce qui revient à le multiplier par 2 (ici 12*2 = 24). Pour la colonne c, si le résultat précédent de la colonne a est pair, on recopie la valeur précédente de la colonne c sinon (résultat impair) on fait la somme des colonnes précédentes b et c.
. . . 
Et on obtient à la fin
Autrement dit, on «bascule » de division par deux en multiplication par deux, la valeur du nombre a sur celui du nombre b.
Mais à quoi bon faire ainsi ?
Oui ! Pour quoi, me direz vous on ressort ce vieil algorithme…Eh bien parce que le Produit Binaire[1] de Leibnitz n’est rien d’autre que la Multiplication Égyptienne, en base 2. Ce petit algorithme, du rang de Curiosité Mathématique, va passer à celui d’Algorithme Fondamental avec les premiers ordinateurs, sous l’influence de Von Neumann et de bien d’autres.
En effet, la particularité de cet algorithme, c’est qu’il est très rapide: chaque division divise a par 2 (élimine un bit de a, diront les informaticiens), jusqu’à ce que a = 0.
Attendez ! En langage plus simple: vous prenez un nombre, disons 1024, divisons le par 2, jusqu’à trouver 0 (ici, 1024 → 512 → 256 → 128 → 64 → 32 → 16→ 8 → 4 → 2 → 1→ 0) on a fait 11 divisions alors que le nombre est un peu plus grand que 1000, bref on réduit très rapidement même un très grand nombre en le divisant successivement par deux (pour un milliard on ne fait qu’une trentaine de divisions : essayez :)). C’est pour cela que l’algorithme est très rapide (et oui c’est bien cela ce fameux logarithme que l’on apprend en maths).
La bonne nouvelle est que pour les processeurs qui travaillent en base 2, l’addition est une opération simple et la duplication (la division par 2 d’un côté et multiplication par 2 de l’autre) n’est qu’un décalage des deux nombres.
Plus précisément c’est un décalage vers les poids forts (à gauche) d’un bit, avec l’insertion d’un 0 en poids faible. La division est un décalage dans l’autre sens, et la parité c’est le bit de poids faible ainsi expulsé ! Le calcul des 3 opérations primitives devient alors simple et rapide. Pour vous en convaincre le même exemple en base 2 :
c’est finalement encore plus simple en binaire, non ?
Tout microprocesseur moderne calcule chacune de ces opérations en quelques nanosecondes. Par souci d’économie, la grande majorité des processeurs ne dispose pas de multiplicateur câblé. On les dote alors d’un multiplieur logiciel en compilant le code de ce petit algorithme. Ce que le matériel ne peut pas faire directement, le logiciel le compense. C’est ainsi, que chaque microseconde, des milliards de circuits de notre monde numérique calculent à l’aide de la Multiplication égyptienne en base 2.
Jean Vuillemin (ENS, Paris) et Pierre Paradinas (Cnam, Paris).
Pour aller plus loin:
- Retrouver l’article complet de Jean sur ce lien;
[1] Ici le mot binaire n’a rien à voir avec le titre du blog.
Il était une fois… la thèse de 
L’exemple de corrélation. 
