Système négabinaire

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.

Sommaire

Histoire

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

Écrire des nombres en négabinaire

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

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

où chaque chiffre dk est soit 0 ou 1 et le "bit conducteur" dn 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=4^2+4^0\,

et 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 :

-5  1111
-4  1100
-3  1101
-2    10
-1    11
 0     0
 1     1
 2   110
 3   111
 4   100
 5   101
 6 11010

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 Grunwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
  • A. J. Kempner. (1936), 610-617
  • Z. Pawlek et A. Wakulicz Bulletin de l'Academie Polonaise des Scienses, Classe III, 5 (1957), 233-236; Serie 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
  • D. Knuth. The Art of Computer Programming, Volume 2, 3rd. Ed. pp204-205

Voir aussi

Articles connexes

Lien externe

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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Système négabinaire de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Systeme negabinaire — 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 les ordinateurs expérimentaux polonais SKRZAT 1 et BINEG en 1950. Il possède la propriété inhabituelle d… …   Wikipédia en Français

  • Systeme negaternaire — Système négaternaire En mathématiques, le système négaternaire est un système de numération positionnel non standard dans lequel les nombres sont écrits comme des sommes de puissances successives de 3. Les trois chiffres sont 0, 1 et 2. L… …   Wikipédia en Français

  • Système négaternaire — En mathématiques, le système négaternaire est un système de numération positionnel non standard dans lequel les nombres sont écrits comme des sommes de puissances successives de 3. Les trois chiffres sont 0, 1 et 2. L avantage d utilisation d une …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”