Systèmes de numération et opérations arithmétiques représentés par des graphes

Conversion de base

Comment convertir un nombre de la base dix vers la base deux ? Sur le schéma ci-dessous (figure 1), la série des nombres entiers (limitée ici de zéro à neuf) constitue la première ligne, la seconde étant formée des restes de la division par deux de chaque nombre. Pour générer l'écriture d'un nombre dans la base 2, pointez ce nombre dans la première ligne, puis suivez les liens vers le bas : écrivez de droite à gauche les restes rencontrés en traversant la seconde ligne.

Figure 1.

Par exemple, pour écrire quatre, on rencontre successivement 0, 0, 1, puis une infinité de 0, ce qui forme, de droite à gauche : ...0000100 correspondant à l'écriture binaire du nombre quatre. Pour écrire en base deux des nombres supérieurs à neuf, il faut compléter ce schéma en prolongeant la série de nombres et celle des restes, et connecter ceux-ci par le même procédé : relier les couples de restes 0 et 1 entre eux deux à deux puis faire la boucle pour aller vers le résultat de la division entière du nombre par deux. Les nombres dix et onze seront reliés au nombre cinq, etc...

Le même schéma peut être utilisé pour décoder un nombre écrit en binaire. Prenons 110 par exemple. Pour décoder nous partons de la gauche du nombre, et pointons dans le schéma sous le premier couple de reste. Le premier chiffre est 1, nous suivons l'embranchement vers le 1, il nous mène à 1, nous continuons et arrivons au second embranchement, comme le second chiffre à décoder est 1, nous suivons le lien menant au 3, et ainsi de suite. Le résultat, 6, est le nombre atteint quand il n'y a plus de chiffres à analyser.

Nous pouvons généraliser à toutes les bases. En base trois par exemple, le convertisseur peut être dessiné comme ci-dessous (figure 2).

Figure 2.

De façon générale, on construit le schéma de conversion en écrivant les restes de la division des nombres par la base et en reliant chaque groupe de chiffres ainsi formé au nombre correspondant au résultat de la division du nombre par la base. Suivre les liens vers le bas à partir d'un nombre en écrivant les chiffres rencontrés est l'équivalent de l'application de l'opération habituelle de conversion, avec les divisions successives.

 

Addition

J'ai obtenu ces schémas en simplifiant le schéma d'addition suivant (Figure 3) en ne retenant que les liens connectés à des 0 en haut (et en effaçant les 0 et 1 supérieurs).

Figure 3.

Cette table d'addition en base 2 fonctionne de la façon suivante : prenons par exemple le nombre binaire 10001 et ajoutons sept. Nous allons parcourir le nombre de droite à gauche, et pointer au départ dans la case 7. Selon que le chiffre courant de notre nombre est 0 ou 1 nous suivrons le lien partant de 0 ou celui partant de 1 (en haut), cela nous mène dans une nouvelle case, sur un chiffre 0 ou 1 de la ligne du bas. Nous écrivons ce chiffre et nous passons au chiffre suivant (vers la gauche) en repartant en haut de la case courante. Le 1 initial nous mène au 0 de la case 4, puis le 0 suivant mène au 0 de la case 2 etc... le résultat sera ...00011000 avec une infinité de zéros à gauche. Nous venons de calculer 17 + 7 = 24.

Chaque case correspond à une retenue possible. La case zéro par exemple conserve les 0 en 0 et les 1 en 1. La case 1 mène à 1 pour un 0 en entrée mais fait passer à la case 0, car la retenue est utilisée. Comme 1 + 1 donne 2 (noté 10 en binaire) le chiffre 1 de la case 1 fait écrire un 0 mais reste dans la case 1 pour indiquer une retenue de 1 sur le rang suivant.

 

Multiplications & Divisions

Dans ma thèse, j'ai déjà exposé des tables de multiplication et de division exprimées sous cette forme, mais je n'avais pas cherché à effectuer de simples additions et soustractions. Voici, par exemple, la table de division et de multiplication par trois en base deux (figure 4).

Figure 4.

Pour multiplier par 3 on circule de droite à gauche le long du nombre à multiplier, et on pointe au départ en haut de la case 0. Le procédé est ensuite le même que précédemment, on suit le lien correspondant au nombre en lecture, et on écrit les chiffres obtenus en bas.

Pour diviser par trois, on circule de gauche à droite sur le nombre et on utilise la table en remontant (les chiffres du bas sélectionnent et ceux du haut sont les résultats).

Les divisions mènent parfois à des résultats infinis (à droite) : 1 divisé par trois donne 0 (case 1), puis le 0 entrant après la virgule donne 0 (case 2), puis le 0 suivant mène à 1 (case 1) et le cycle se perpétue : 0,0101010101...

Cette table à l'air plus compacte que la table d'addition précédente, mais en fait, comme pour l'addition, la table doit être aussi grande que l'opérande, il y a en outre une table spécifique pour chaque multiplicande.

En remarque, si nous utilisons la table ci-dessus à partir de la case 0, nous effectuons l'opération 3x, mais en partant de la case 1 nous obtenons 3x + 1, et la case 2 donnera 3x + 2.

 

Conversions à nouveau

Le schéma de la figure 1 peut être étiré (sans changement de connections) pour former celui-ci (figure 5).

Figure 5.

Pour convertir le nombre 6 en base 2 par exemple, on remonte les liens à partir du nombre 6 en écrivant de droite à gauche les chiffres binaires notés sur les arêtes rencontrées en remontant. On obtient successivement 0, 1, 1, 0, 0, 0... qui s'écrit 110 habituellement (en omettant les zéros initiaux).

Dans l'autre sens, en partant de 0 on décode un nombre binaire en suivant les liens indiqués par les chiffres portés sur les arêtes en fonction des chiffres du nombre à décoder lu de gauche à droite.

Mis à part le zéro et sa boucle initiale, on retrouve une figure connue [Knuth 1968], l'arbre binaire où tout nœud de valeur i à pour fils 2i et 2i+1.

 

Soustracations (des soustractions sans tracas).

Mais comment faire les soustractions ? Utiliser un inverseur (figure 6),

Figure 6.

pour complémenter le nombre à soustraire, puis ajouter 1 pour obtenir la notation complément à deux. Ou simplement poursuivre la table d'addition après le zéro. Voici la table d'addition étendue aux nombres négatifs (figure 7).

Figure 7.

La table est symétrique par rapport à l'axe vertical central de la case 0. Les nombres négatifs sont représentés avec une infinité de 1 à gauche (alors que les nombres positifs ont une infinité de 0 à gauche). Par exemple si nous ajoutons -4 à 0, nous obtenons d'après la table les chiffres 0 (case -2), 0 (case -1), 1 (case -1), 1 (case -1), etc... ce qui forme le nombre ...1111100.

Le nombre -1 est représenté par une infinité de 1 à gauche. ...11111, en y ajoutant 1 on tombe dans un cycle donnant une infinité de 0 (case 1).

Cette table peut à nouveau être simplifiée (en retirant les chiffres binaires de la ligne du haut et tous les liens partant des 1) pour obtenir l'arbre de conversion des nombres négatifs (figure 8).

Figure 8.

Le graphe des nombres binaires négatifs est similaire à celui des nombres positifs (figure 5), mais la boucle est sur le nombre -1 (qui a le même rôle que le zéro), et mis à part cette boucle, la racine de l'arbre restant est le nombre -2. Pour le reste, tout nœud i à pour fils 2i et 2i + 1.

 

Programme Smalltalk

Ce programme permet de créer des opérations fonctionnant en base 2 et de les tester.

Nouvelle Opération: crée une nouvelle opération vide. L'opération est représentée par un rectangle bleu-clair, on peut la déplacer en attrapant le haut du rectangle.

Nouvel élément: ajoute un élément dans l'opération sélectionnée, ou dans l'opération contenant l'élément sélectionné.

Calculer: applique l'opération sélectionnée au nombre binaire affiché ou saisi dans la première boite, affiche le résultat dans la seconde boite. Le traitement débute dans l'élément sélectionné.

Change sens: Détermine si l'opération traite le nombre d'entrée de gauche à droite ou de droite à gauche. Le sens de l'opération est indiqué par le point en haut de l'opération (à droite pour aller de droite à gauche).

Les deux boites suivantes permettent (quand c'est possible) la saisie et l'affichage de la conversion en base dix des deux premières boites.

Le bouton (^ ) transfert le résultat dans l'entrée.

Le bouton Opération Prédéfinie permet de créer automatiquement des opérations d'addition, de multiplication, de division.

Enfin, le bouton Effacer la sélection permet de supprimer les éléments et/ou les opérations.

 

Pour charger le programme cliquez ici. pour la version vw3.0 cliquez ici

 

Références

Knuth D. 1968-1973

Fundamental Algorithms The Art of Computer Programming

Second edition.

Addison Wesley

Figure (5) et (6) pp.400-401

Lesbros V. 1995

Atelier Incrémentiel pour la Musique Expérimentale

Thèse de Doctorat, Université Paris 8

pp.105-121

 

 


m a i l t o : v i @ a i . u n i v - p a r i s 8 . f r