Système négabinaire

En mathématiques, le système négabinaire (base –2) est un système de numération positionnel non standard utilisé dans l'ordinateur expérimental polonais BINEG, construit en 1957-59. Il possède la propriété inhabituelle d'avoir les nombres négatifs et positifs représentés sans un bit de signe, bien que les opérations arithmétiques soient plus compliquées.

Graphique représentant des nombres en base -10.

Histoire

Les bases numériques négatives ont été découvertes par Vittorio Grünwald (en) dans son travail Giornale di Matematiche di Battaglini, publié en 1885. Grünwald donna des algorithmes pour exécuter les additions, les soustractions, les multiplications, les divisions, les extractions de racines, les tests de divisibilité et les conversions de bases. Les bases négatives furent redécouvertes indépendamment plus tard par Aubrey J. Kempner (en) en 1936 et Zdzisław Pawlak (en) et A. Wakulicz en 1959.

Écrire des nombres en négabinaire

Tout entier relatif peut être écrit de manière unique sous la forme

\sum _{k=0}^{n}d_{k}(-2)^{k}

où chaque chiffre d_k est soit 0 ou 1 et le « bit conducteur » d_n est 1 (à moins que n = 0). Le développement négabinaire d'un entier donné est alors donné par la chaîne :

d_{n};d_{n-1}...d_{1}d_{0}.

Quelques nombres négabinaires ont la même représentation en système binaire. Par exemple,

17=2^{4}+2^{0}

est représenté par 10001 en binaire et 10001 en négabinaire.

Les nombres allant de –5 à 6 avec leurs développements négabinaires sont :

Le développement négabinaire d'un nombre peut être trouvé avec une division répétée par –2, en enregistrant les restes non négatifs de 0 ou 1, en concaténant ces restes puis en démarrant avec le dernier. Note : si a / b = c, reste d, alors bc + d = a. Par exemple :

13 / –2 = –6, reste 1
–6 / –2 =  3, reste 0
 3 / –2 = –1, reste 1
–1 / –2 =  1, reste 1
 1 / –2 =  0, reste 1

Par conséquent, le développement négabinaire de 13 est 11101.

Note : les développements négabinaires d'entiers négatifs ont un nombre pair de bits, tandis que les développements négabinaires d'entiers positifs ont un nombre impair de bits.

Addition

Pour ajouter deux nombres négabinaires, démarrer avec une retenue 0, et en démarrant à partir du bit de poids faible, ajouter les bits des deux nombres plus la retenue. Le nombre résultant est alors recherché dans la table suivante pour obtenir le bit à écrire dans le résultat, et la retenue suivante :

nombre bit retenue
  –2    0    1 (Note : –2 apparaît seulement pendant la soustraction).
  –1    1    1
   0    0    0
   1    1    0
   2    0   –1
   3    1   –1 (Note : 3 apparaît seulement pendant l'addition).

La deuxième ligne de cette table, par exemple, exprime le fait que –1 = 1 + 1×(–2); la cinquième ligne dit que 2 = 0 + –1×(–2); etc.

Comme exemple, ajouter 1010101 (1 + 4 + 16 + 64 = 85) et 1110100 (4 + 16 – 32 + 64 = 52),

retenue :          1 –1  0 –1  1 –1  0  0  0
premier nombre :         1  0  1  0  1  0  1
deuxième nombre :        1  1  1  0  1  0  0 +
                  --------------------------
nombre:            1 –1  2  0  3 –1  2  0  1
bit (résultat) :   1  1  0  0  1  1  0  0  1
retenue:           0  1 –1  0 –1  1 –1  0  0

donc, le résultat est 110011001 (1 – 8 + 16 – 128 + 256 = 137).

Soustraction

Pour soustraire, multiplier chaque bit du deuxième nombre par –1, et ajouter les nombres, en utilisant la même table que ci-dessus.

Comme exemple, calculer 1101001 (1 – 8 – 32 + 64 = 25) moins 1110100 (4 + 16 – 32 + 64 = 52),

retenue :          0  1 –1  1  0  0  0
premier nombre :   1  1  0  1  0  0  1
deuxième nombre : –1 –1 –1  0 –1  0  0 +
                  --------------------
nombre:            0  1 –2  2 –1  0  1
bit (résultat) :   0  1  0  0  1  0  1
retenue:           0  0  1 –1  1  0  0

donc le résultat est 100101 (1 + 4 – 32 = –27).

Pour rendre négatif un nombre, calculer 0 moins le nombre.

Multiplication et division

Décaler vers la gauche multiplie par –2, décaler vers la droite divise par –2.

Pour multiplier, multiplier comme en système décimal, mais en utilisant les règles négabinaires pour ajouter la retenue, lorsqu'on ajoute les nombres.

premier nombre :                   1  1  1  0  1  1  0
deuxième nombre :                  1  0  1  1  0  1  1 *
                 -------------------------------------
                                   1  1  1  0  1  1  0
                                1  1  1  0  1  1  0
   
                          1  1  1  0  1  1  0
                       1  1  1  0  1  1  0

                 1  1  1  0  1  1  0                   +
                 -------------------------------------
retenue:         0 –1  0 –1 –1 –1 –1 –1  0 –1  0  0
nombre:          1  0  2  1  2  2  2  3  2  0  2  1  0
bit (résultat) : 1  0  0  1  0  0  0  1  0  0  0  1  0
retenue :           0 –1  0 –1 –1 –1 –1 –1  0 –1  0  0

Pour chaque colonne, ajouter retenue à nombre, et diviser la somme par –2, pour obtenir la nouvelle retenue, et le bit résultant comme reste.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Negabinary » (voir la liste des auteurs).
Vittorio Grünwald, Giornale di Matematiche di Battaglini (1885), 203-221, 367
A. J. Kempner. (1936), 610-617
Z. Pawlek et A. Wakulicz, Bulletin de l'Académie Polonaise des Sciences, Classe III, 5 (1957), 233-236; Série des sciences techniques 7 (1959), 713-721
L. Wadel IRE Transactions EC-6 1957, 123
N. M. Blachman, Communications of the ACM (1961), 257
IEEE Transactions, 1963, 274-276
Computer Design Mai 1967, 52-63
R. W. Marczynski, Annotated History of Computing, 1980, 37-48
Donald Knuth, The Art of Computer Programming, vol. 2, 3^e éd., p. 204-205

Voir aussi

Articles connexes

Liens externes

(en) Eric W. Weisstein, « Negabinary », sur MathWorld