De la numération binaire
De la numération binaire
Auteur :
Gottfried Wilhelm Leibniz (1646-1716) - mathématicien et philosopheAuteur de l'analyse: Yves Serra, ingénieur
Publication :
« De progressione dyadica», manuscrit des archives Leibniz de la Niedersächsische Landesbibliothek Hannover, fac-similé publié dans Erich Hochstetter & Hermann-Josef Greve, eds., Herrn von Leibniz’ Rechnung mit Null und Einz (Berlin, Siemens Aktiengesellschaft, 1966)Année de publication :
1679Nombre de pages :
3Résumé :
Ce manuscrit exceptionnel apparaît à ce jour comme la plus ancienne évocation d'un calculateur binaire, à l’instar de ceux que nous utilisons aujourd’hui. Car, comme nous le rappelle Leibniz dès 1679, pour multiplier des 0 et des 1, point n'est besoin de connaître la table de multiplication décimale !
Source de numérisation :
Niedersächsische Landesbibliothek Hannover
Ce manuscrit exceptionnel, écrit par Leibniz à 33 ans mais non publié, fait le lien entre deux de ses travaux majeurs, paraissant a priori indépendants : son idée du calcul binaire (article de 1703 qui n’évoque pas de machine à calculer) et son idée de machine à calculer décimale (texte BibNum, article de 1710 correspondant au travail de Leibniz de 1673 à 1709). Ces deux idées n’ont sans doute pas été développées indépendamment et, même si Leibniz ne l’a pas publié, ce manuscrit apparaît à ce jour comme la plus ancienne évocation d'un calculateur binaire.
Yves Serra, ingénieur civil des Ponts et Chaussées (1975), est informaticien, directeur dans un groupe de marketing et d'ingénierie ; il prépare un Master de philosophie et d'histoire des sciences. Il est par ailleurs collectionneur de machines à calculer anciennes et récentes.
Le manuscrit « De Progressione Dyadica » de Leibniz
Yves Serra, ingénieur
Les bibliographies de Leibniz font toutes référence à deux publications importantes pour l'histoire du calcul et des machines à calculer. L'une, publiée en 1710 dans les Miscellanea Berolinensis, présente la machine arithmétique (1) que Leibniz a conçue entre 1673 et 1709. L'autre, publiée en 1703, est un mémoire à l’Académie des Sciences de Paris sur le calcul binaire ("Explication de l’arithmétique binaire qui se sert des seuls caractères 0 & 1 avec des remarques sur son utilité & sur ce qu’elle donne le sens des anciennes figures chinoises de Fohy (2)").
En rapprochant ces deux publications, on espèrerait trouver le texte qui, faisant la synthèse du calcul binaire et de la mécanisation, serait le précurseur de l'informatique. Mais rien dans les bibliographies officielles, rien dans les publications, rien de connu par des spécialistes de Leibniz interrogés, dont l’intérêt se centre souvent plus sur la dimension philosophique de l'auteur que sur ses inventions techniques. Leibniz aurait-il arpenté ces deux chemins sans les faire se croiser ? La présente analyse reprend rapidement l'enquête qui amène à savourer que non, Leibniz n'est pas passé à côté de ce rapprochement et il existe bien un texte, manuscrit, de 1679 qui, à ce jour, apparaît être la plus ancienne évocation d'un calculateur binaire.
@@@@@@@
La recherche commence en s'appuyant sur Internet et en alternant questions posées aux moteurs en français, allemand, latin et anglais ; après de nombreux tâtonnements émergent des références à un texte, resté manuscrit, jamais publié par Leibniz ou dans ses œuvres. Il serait donc passé largement inaperçu des commentateurs. Ce manuscrit est daté du 15 mars 1679. Il est titré « De progressione dyadica » et est conservé à la bibliothèque de Hanovre (Niedersächsische Landesbibliothek Hannover). Preuve du caractère confidentiel de ce manuscrit, un ouvrage de référence sur Leibniz et la notation binaire omet simplement d'en parler (3). Déception.
Ne disposant que du titre « de Progressione Dyadica », on pense naturellement qu'il est une préfiguration du mémoire de 1703 ; reste à voir comment y figure le calcul mécanisé – la vérification s'impose.
Malheureusement, l'original, manuscrit de trois pages en latin, n'est pas disponible sur Internet et aucune traduction non plus. Il faut donc se tourner vers les sources moins électroniques, et effectivement, enfin, les recherches convergent vers un ouvrage en allemand de 1966 cité par plusieurs chercheurs :
Leibniz, De Progressione Dyadica, Pars I, (MS, 15 March 1679), published in facsimile (with German translation) in Erich Hochstetter and Hermann-Josef Greve, eds., Herrn von Leibniz’ Rechnung mit Null und Einz (Berlin : Siemens Aktiengesellschaft, 1966) (4).
Figure 1 : Le livre de 1966 dans lequel est apparu pour la première fois le manuscrit de 1679 de Leibniz, « De progressione dyadica ». Le manuscrit est conservé à la Niedersächsischen Landesbibliothek Hannover.
Il faut ensuite trouver l'ouvrage, grâce à Internet cette fois, l'acquisition peut se faire chez un antiquaire de Munich qui en a un exemplaire. L'ouvrage comporte bien un fac-similé des trois pages du manuscrit de Leibniz, une traduction en allemand faite par le religieux Pater Franz X. Wernz S.J. (Munich) et une analyse, en allemand, écrite par Hermann-Josef Greve (5). Après quelques mois d'enquête, le travail peut commencer ! Et le manuscrit comporte bien en sa troisième page la présentation de ce qui est certainement la première description d'un calculateur binaire. Dans son analyse, Hermann-Josef Greve rend hommage à Eric Hochstetter (6) comme le découvreur de cette description dans ce manuscrit de Leibniz au sein de la bibliothèque de Hanovre – et lui ne disposait pas d'Internet pour l'aider !
@@@@@@@
Le lecteur aura compris que cette longue introduction a pour objectif de marquer la difficulté qu'il y a encore, à ce jour, à revenir aux textes originaux, même essentiels et même d'auteurs aussi reconnus que Leibniz et, symétriquement, de l'utilité des initiatives qui, comme BibNum, ne se contentent pas de republier pour la nième fois ce qui est déjà facilement accessible.
Le manuscrit de Leibniz est reproduit ci-contre avec la traduction en français, réalisée par l'auteur de la présente analyse. La traduction s'appuie à la fois sur le texte en latin et sur le texte en allemand, mais beaucoup également sur le contenu binaire des exemples donnés par Leibniz !
Description de la notation binaire par Leibniz
La première page décrit la notation binaire. S'appuyant sur une liste des 100 premiers nombres écrits en bases dix et deux, Leibniz explique tout d'abord comment passer d'un nombre binaire au suivant, puis explicite le calcul avec les puissances successives de la base sur l'exemple du passage de 1011000 à 88.
La méthode proposée par Leibniz pour la conversion inverse du décimal en binaire est la division successive par 2 en conservant le reste, 0 ou 1 à chaque étape. 365 (7) devient ainsi 101101101.
Figure 2 : (à g. texte de Leibniz, à dr. transcription) En divisant 365 par 2, on obtient 182 et il reste 1, porté sur la colonne de droite ; en divisant 182 par 2, on obtient 91 et il reste 0, porté sur la colonne de droite ; etc. Le 1 final (en bas à gauche) est systématiquement reporté en bas à droite. ATTENTION, le chiffre binaire se lit de bas en haut dans la colonne de gauche : on obtient ainsi que 365 s’écrit 101101101 en base 2.
Il généralise cette méthode en montrant qu'en divisant ce même chiffre en binaire 101101101 par 1010, soit 10 en décimal, et en gardant les restes à chaque division, on retrouve bien 365. La division est posée ici selon la méthode « à la française » commentée plus loin avec les explications de Leibniz sur la division en binaire.
L'opération consiste en deux divisions la première de 101101101 (365) par 1010 (10) donne le quotient 100100 (36) et le reste 101 (5), puis la seconde division où il divise 100100 (36) par 1010 (10) pour trouver le quotient 11 (3) et le reste 110 (6) (8).
La première page comporte également deux annotations séparées du texte principal. La première commente les régularités d'apparition des 0 et des 1 dans la succession des nombres naturels exprimés en binaire. Leibniz se construit dans cette annotation un plan de travail pour rechercher d'autres régularités dans les progressions des chiffres en notation binaire.
La seconde annotation souligne la facilité de la multiplication binaire qui rend inutile l'apprentissage de la table de Pythagore. Cette annotation est bien sûr à mettre en exergue pour ce qui va suivre.
L’addition et la soustraction en binaire
Dans la seconde page du manuscrit, Leibniz commence par décrire l'addition en binaire. Il affirme la facilité de cette addition en constatant qu'ayant écrit 10110 puis 11011 dessous, il peut ensuite écrire directement le résultat.
Malheureusement, il écrit 1000001 au lieu de 110001 (9). Les autres additions, plus complexes, et justes, faites par Leibniz plus loin nous montrent qu'il s'agit bien là d'une simple erreur et que, surtout, il s'agit d'un manuscrit non relu que Leibniz n'aurait pas publié en l'état.
Après cette première addition simple, Leibniz poursuit par l'exemple d'une addition de cinq nombres, sans erreur cette fois, et explique que l'addition en binaire se ramène à un simple comptage des 1 dans chaque colonne. Nul besoin de connaître la table d'addition, connaissance requise pour opérer en notation décimale. Dans la continuité de sa démonstration, Leibniz propose de mélanger additions et soustractions et de trouver simplement le résultat en compensant directement les +1 et -1 dans chaque colonne.
![Figure 3 : (à g. texte de Leibniz, à dr. transcription) En partant de la colonne de droite, on compte trois 1, on pose 1 en bas et on retient 1 ; la deuxième colonne donne quatre avec la retenue ; on pose O et on retient 2 ; la troisième colonne donne six avec la retenue ; on pose O et on retient 3 (comme écrit Leibniz, si le nombre de 1 est pair, on « transfére[r] la moitié du nombre d'unités à la colonne suivante » ; etc. On a fait figurer sur la ligne du haut du tableau les retenues successives, représentées par Leibniz sous forme de points.](/files/u1/Figure-3_23.jpg)
Figure 3 : (à g. texte de Leibniz, à dr. transcription) En partant de la colonne de droite, on compte trois 1, on pose 1 en bas et on retient 1 ; la deuxième colonne donne quatre avec la retenue ; on pose O et on retient 2 ; la troisième colonne donne six avec la retenue ; on pose O et on retient 3 (comme écrit Leibniz, si le nombre de 1 est pair, on « transfére[r] la moitié du nombre d'unités à la colonne suivante » ; etc. On a fait figurer sur la ligne du haut du tableau les retenues successives, représentées par Leibniz sous forme de points.
Enfin, Leibniz présente la technique de la soustraction par ajout du complément à 10, technique qu'il a déjà présentée par ailleurs en décimal, et technique également utilisée par Pascal pour faire des soustractions avec sa "pascaline" (10).
La division et la multiplication en binaire
La troisième page du manuscrit comporte une partie haute qui traite de la multiplication et du calculateur binaire, par laquelle nous terminerons, et une partie basse qui traite de la division. Leibniz reprend la division qu'il a déjà considérée sur la première page, pour transcrire 365 depuis la notation binaire (101101101) vers la notation décimale par divisions successives par 10 (1010 en binaire). Leibniz utilise pour cela la méthode « à la française » qui consiste à poser le dividende et, dessous, le diviseur autant de fois que de puissances de la base et, à droite du dividende, construire le quotient en posant progressivement, de gauche à droite, les restes successifs au dessus du dividende, et en barrant les chiffres déjà employés. Les exemples ci-dessous, de difficulté progressive et exprimés en décimal, sont tirés de l'ouvrage « L'arithmétique en sa perfection » de F. Le Gendre (Paris, 1684) :
La vidéo en lien (11) permet de voir comment se construit cette dernière division. Avec la même notation, la division de 365 par 10 devient en binaire :
Le quotient est donc 100100, soit 36, et le reste 101 soit 5. Cette division se présente très simplement, et Leibniz remarque qu'elle peut même être exécutée sans barrer les chiffres et sans noter les étapes intermédiaires. Cette simplicité n'est en fait pas liée à la numération binaire mais à l'absence de retenues dans cet exemple, et Leibniz s'en aperçoit dès la ligne suivante où, pour diviser à nouveau 36 par 10, soit 100100 par 1010, il s'y reprend à trois fois avec forces ratures et, finalement, revient à la méthode « à la française » :
Soit un quotient de 11, donc 3 en décimal, et un reste de 110, 6 en décimal.
Suite à cet exemple, Leibniz précise comment faire une retenue en série dans la soustraction, et le présente sous une forme pratique d'algorithme que nous écririons aujourd'hui :
soit à soustraire 1
tant que au dessus il y a zéro,
mettre 1
décaler d'une colonne vers la gauche,
fin tant que
au dessus il y a 1,
mettre zéro
c'est fini
soit à soustraire 1
tant que au dessus il y a zéro,
mettre 1
décaler d'une colonne vers la gauche,
fin tant que
au dessus il y a 1,
mettre zéro
c'est fini
@@@@@@@
Détaillons maintenant la partie du manuscrit relative à la multiplication. Leibniz souligne dès l'abord l'apport majeur de la notation binaire : plus besoin d'apprendre les tables de multiplication ! Plus de tables de Pythagore. Pour multiplier il suffit d'écrire soit le nombre lui même soit de décaler d'un zéro.
Un exemple illustre ce principe, repris ci-dessous en totalité car il visualise l'idée que Leibniz va développer ensuite :
Figure 4 : (à g. texte de Leibniz, à dr. transcription) Multiplication 93 x 14 = 1302 (explications ci-après).
Les paragraphes suivants constituent la principale originalité de ce manuscrit : la mécanisation de ce calcul.
La mécanisation du calcul
Dès la première ligne, Leibniz annonce la possibilité d'une machine mécanique pouvant faire cette multiplication en notation binaire facilement et sans effort.
Ce type de calcul pourrait également être réalisé avec une machine (sans roues) (…) Avec une boîte munie de trous, qui peuvent être ouverts et fermés.
Prenons donc une boîte avec des trous qui pourraient libérer des billes conformément à chaque ligne de la multiplication ci-dessus :
Les billes tombent ensuite dans des rigoles, matérialisation des colonnes de la multiplication posée :
Étape 1 : Le multiplicateur 1110 comporte un 0 à droite, on laisse une colonne à droite (comme dans une multiplication posée à la main). Le deuxième chiffre en partant de la droite étant un 1, on s’arrête là et on injecte les billes.
La boîte sera décalée vers la gauche autant de fois que le demande le multiplicateur, soit 3 fois dans l'exemple de la multiplication par 1110 (soit 14).
Étape 2 : Deuxième décalage, correspondant au chiffre 1 suivant. On se décale d’une autre colonne vers la gauche et on injecte les billes, qui viennent se superposer à celles qui étaient déjà là.
Étape 3 : Troisième décalage, correspondant au chiffre 1 suivant, et dernier.
Ce dispositif de construction d'une machine avec partie fixe et partie mobile est celui que Leibniz a également retenu pour sa machine à calculer en décimal (12). Les premières esquisses de cette machine sont de 1673, donc antérieures au manuscrit, et il est vraisemblable que Leibniz en ait ici réutilisé l'idée.
Ensuite, naturellement, Leibniz précise que les billes ne devront pas pouvoir passer d'une rigole à l'autre.
@@@@@@@
Il reste à préciser comment se comportent les billes dans une même rigole pour assurer totalisation et retenues. Leibniz formule alors deux idées-clef. D'une part, s’il y a deux billes dans une rigole, elles doivent « tomber » et s’il n'y a qu'une bille dans une rigole, elle y reste :
Car la chose peut être organisée que deux billes sortent toujours nécessairement ensemble, et autrement ne doivent pas sortir.
D'autre part, des deux billes qui « tombent », l'une va dans la rigole suivante et l'autre tombe dans un réservoir placé sous la machine : la première constitue la retenue.
Il est clair que ces deux idées sont nécessaires et suffisantes à réaliser le calcul souhaité, totalisation et retenue. Détaillons ce qui se passe visuellement, sur le plan des principes avant de revenir sur les aspects mécaniques esquissés par Leibniz.
La boîte mobile (celle du dessus) a libéré par 3 fois les billes correspondant à la multiplication par 1110 de 1011101 – c’est le résultat de l’étape 3 ci-dessus:
Quatrième étape, calculons le résultat de droite à gauche. Dans la colonne des unités, il y a zéro billes, le résultat est 0. Dans les deux colonnes suivantes, correspondant à 10 et 100, soit 2 et 4, il n'y a qu'une bille qui, d'après la première règle, reste dans sa rigole.
Dans la colonne suivante, 1000 soit 8, il y a 2 billes, elles tombent donc, en laissant zéro, et générant une retenue dans la colonne suivante :
Dans la colonne des 10000, il y a maintenant 3 billes dont 2 vont tomber, générant une retenue, et il en restera une.
Et ainsi de proche en proche, jusqu'au résultat final où seules restent des colonnes avec 0 ou 1 billes :
Le résultat de la multiplication est bien 10100010110 !
Essais de réalisation de la machine
Les quelques lignes du manuscrit permettent également, au delà de ces principes, de voir comment Leibniz en envisage la réalisation matérielle.
La première boîte est un réservoir de billes avec un alignement de trous qui, ouverts ou fermés pour 1 ou 0, matérialisent le multiplicande. La boîte est déplacée pour chaque puissance de 2 du multiplicateur et un système de roues à deux dents permet à chaque puissance de présenter une bille devant l'orifice. L'analogie avec sa machine décimale est transparente.
Les lignes suivantes sur la réalisation de la retenue sont moins explicites. Il faut en effet un dispositif avec une « porte » qui permette à une bille d'une colonne de passer vers la suivante mais seulement quand elle est accompagnée d'une autre bille et que cette seconde bille tombe alors dans une boite située en dessous. Les dispositifs imaginés par Leibniz pour sa machine décimale étant bien plus complexes, nul doute qu'il aurait résolu la question s'il avait poursuivi la mise en œuvre de la présente machine binaire, mais le texte lui-même n'ouvre pas de piste très claire sur la façon dont il envisageait la réalisation de ce mécanisme.
Malgré cette imprécision de la source, et au moins à deux reprises, la réalisation matérielle de ce qu'aurait pu être cette machine a été proposée.
Ludolf von Mackensen a conçu une machine en bois qui a été réalisée en 1971 par le Deutsches Museum de Munich. Une analyse et des photos en sont disponibles dans la thèse de Kasimierz Trzesicki (13).
Gerhard Weber en a conçu une en matériau transparent en 2000, dont nous reproduisons la photo ci-dessous. La description en est reprise dans l'article d’Erwin Stein (14).
Figure 5 : Modèle d’une machine binaire suivant Leibniz réalisé en 2003-2004 par E. Stein & G. Weber (Institut de mécanique et de mécanique computationnelle, Université Leibniz de Hanovre)
Sans nier la large extrapolation technique que représente cette machine en regard du contenu du manuscrit de Leibniz, force est de constater que Leibniz, dès 1679, a anticipé l'intérêt de construire une machine à calculer en binaire, et en a esquissé une conception qui s’est montrée fonctionnelle. Il n'a pas repris cette proposition de mécanisation dans son mémoire à l'Académie des Sciences de Paris de 1703 qui comporte bien, en revanche, la description de la notation binaire ainsi que celle des quatre opérations en prolongement du manuscrit de 1679. Bien que manuscrit et clairement inachevé, le document « de Progressione Dyadica » du 15 mars 1679 est bien, à ce jour, un texte fondateur.
Décembre 2010
(1) Voir ce texte analysé sur BibNum (Yves Serra).
(2) Texte en ligne ici
(3) H. J. Zacher. Die Hauptschriften zur Dyadik von G. W. Leibniz. Klosterman, Frankfurt, 1973
(4) L'ouvrage est publié par Siemens en 1966 à l'occasion du 250ème anniversaire de la mort de Leibniz (14 novembre 1716). La traduction française du titre est : Le Calcul avec des 0 et 1, selon M. de Leibniz.
(5) Hermann-Josef Greve, né en 1903, diplômé de l'Université de Köln, Directeur de Saarbergwerke AG, Saarbrücken.
(6) Erich Hoschstetter 1888-1968 Professeur de Philosophie à l'Université de Munster, Directeur du Centre de recherche Leibniz de Munster et membre correspondant de l'Académie des Sciences de Gottingen.
(7) On constate que Leibniz prend souvent le nombre 365 (jours de l’année) comme exemple dans ses articles. Voir texte BibNum précité sur la machine de Leibniz, où celui-ci prend à propos de sa machine l’exemple de la multiplication 365 1709 (année où il écrit son article).
(8) La division en binaire, suivant le mode classique en usage (et non la division à la française utilisée par Leibniz), nécessite une certaine accommodation. La première division, 101101101 par 1010, ne pose pas de problème, puisqu’elle se fait comme en décimal : on trouve facilement le quotient 100100 et le reste 101. La division de ce quotient, 100100, par le diviseur 1010, est plus délicate (rappel : on ne fait intervenir que des 0 et des 1) : en 10010 il y va 1 fois 1010, reste 1000 – on abaisse un 0 (le dernier chiffre du dividende)– en 10000, il y va une fois 1010, reste 110. Cette deuxième division a donc bien 11 comme quotient et 110 comme reste.
(9) Il s’agit de l’addition décimale 22 + 27 = 49. En binaire, Leibniz fait une erreur dans la dernière colonne à gauche : on doit additionner 1 et 1, et il y a déjà 1 en retenue provenant des autres colonnes. On doit alors écrire en bas 11 (débordement du 1), et non 100 comme écrit Leibniz par inadvertance, emporté par son élan.
(10) Voir l’analyse BibNum du texte de Blaise Pascal sur sa machine (1645).
(11) Diviser à la française : http://yves.serra.pagesperso-orange.fr/division.htm (vidéo pédagogique).
(12) Voir analyse BibNum, déjà citée.
(13)http://logika.uwb.edu.pl/KT/Leibnizjanskie%20inspiracje%20informatyki.pdf (en polonais).
(14)http://www.ikb.poznan.pl/fcee/2006.07/full/fcee_2006-07_319-332_calculemus.pdf (FCEE Foundations of civil and environmental engineering, n°7, août 2006).
Ce manuscrit de Leibniz est à ce jour la plus lointaine étape de notre remontée dans le temps. Si vous trouvez un texte antérieur au 15 mars 1679 présentant l’idée d'une machine à calculer binaire, BibNum se fera un plaisir d'en publier l'analyse (Y.S.)
À LIRE (LIVRES)
Friedrich L. Bauer, Origins and Foundations of Computing (in cooperation with with Heinz Nixdorf Museums Forum), Springer 2007.
Jean Marguin, Histoire des instruments et machines à calculer, Hermann 1994.
À CONSULTER (SITES INTERNET)
http://www-history.mcs.st-andrews.ac.uk/Extras/Harriot_binary_numbers.html
Ce lien montre comment la notation binaire avait été explorée, avant Leibniz, par Thomas Harriot (Oxford 1560, Londres 1621).
>> Téléchargez le manuscrit de Gottfried Wilhelm Leibniz
 |
« De progressione dyadica» (6.38 Mo) |
>> Téléchargez l'analyse d'Yves Serra
|
Le manuscrit « De Progressione Dyadica » de Leibniz (387.35 Ko) |
Le code a été copié dans votre presse-papier
Embarquer le document
Emdbed :
- Désolé, il n'y a pas encore de commentaire.
sites/default/themes/bibnum-front/thickbox.php
