System négabinaire

In Mathematical, the system négabinaire (-2 bases) is a positional numbering system not-standard used in the experimental Ordinateur S Polish SKRZAT 1 and BINEG in 1950. It has the unusual property to have the negative and positive numbers represented without a bit of sign, although the arithmetic operations are more complicated.

History

The negative numerical bases were discovered by Vittorio Grunwald in his work Giornale di Matematiche di Battaglini , published in 1885. Grunwald gave algorithms to carry out the additions, the subtractions, the multiplications, divisions, the extractions of roots, the test of divisibility and conversions of bases. The negative bases were independently later redécouvertes by A.J. Kempner in 1936 and Z. Pawlak and A. Wakulicz in 1959.

To write numbers in négabinaire

Each whole can be written in a single way in the form

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

where each figure D _K is 0 or 1 and the " bit conducteur" D _N is 1 (unless N =0). The development négabinaire of a given entirety is then given by the chain:

d_n; d_ {n-1}… d_1 d_0 \,

A few négabinaires numbers have the same representation in binary system. For example,

17=4^2+4^0 \,

and is represented by 10001 into binary and 10001 in négabinaire.

The numbers going from -5 to 6 with their developments négabinaires are: -5 1111 -4 1100 -3 1101 -2 10 -1 11 0 0 1 1 2 110 3 111 4 100 5 101 6 11010

The development négabinaire of a number can be found with a division repeated by -2, by recording the not-negative remainders of 0 or 1, by concaténant these remainders then while starting with the last. Note: if/B has = C, remains D, then bc + D = A. For example: 13/-2 = -6, remains 1 -6/-2 = 3, remains 0 3/-2 = -1, remains 1 -1/-2 = 1, remains 1 1/-2 = 0, remain 1 Consequently, the development négabinaire of 13 is 11101.

Note: the developments négabinaires of negative entireties have an even number of bits, while the developments négabinaires of positive entireties have an odd number of bits.

Addition

To add two négabinaires numbers, to start with a reserve 0, and by starting starting from the weak Bit of weight, to add the bits of the two numbers plus reserve. The resulting number is then required in the following table to obtain the bit to be written in the result, and following reserve:

bit number retained -2 0 1 (Note: -2 appears only during the subtraction). -1 1 1 0 0 0 1 1 0 2 0 -1 3 1 -1 (Note: 3 appears only during the addition).

The second line of this table, for example, expresses the fact that -1 = 1 + 1 × (- 2); the fifth line says that 2 = 0 + -1 × (- 2); etc

Like example, to add 1010101 (1+4+16+64 = 85) and 1110100 (4+16-32+64 = 52),

reserve: 1 -1 0 -1 1 -1 0 0 0 first number: 1 0 1 0 1 0 1 second number: 1 1 1 0 1 0 0 + -------------------------- number: 1 -1 2 0 3 -1 2 0 1 bit (result): 1 1 0 0 1 1 0 0 1 reserve: 0 1 -1 0 -1 1 -1 0 0

therefore, the result is 110011001 (1-8+16-128+256 = 137).

Subtraction

To withdraw, to multiply each bit of the second number by -1, and to add the numbers, by using the same table as above.

Like example, to calculate 1101001 (1-8-32+64 = 25) less 1110100 (4+16-32+64 = 52),

reserve: 0 1 -1 1 0 0 0 first number: 1 1 0 1 0 0 1 second number: -1 -1 -1 0 -1 0 0 + -------------------- number: 0 1 -2 2 -1 0 1 bit (result): 0 1 0 0 1 0 1 reserve: 0 0 1 -1 1 0 0

thus the result is 100101 (1+4-32 = -27).

To make negative a number, to calculate 0 minus the number.

Multiplication and division

To shift towards the left multiplies by -2, to shift towards the line divides by -2.

To multiply, to multiply as in decimal system, but by using the rules négabinaires to add reserve, when the numbers are added.

first number: 1 1 1 0 1 1 0 second number: 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 + ------------------------------------- reserve: 0 -1 0 -1 -1 -1 -1 -1 0 -1 0 0 number: 1 0 2 1 2 2 2 3 2 0 2 1 0 bit (result): 1 0 0 1 0 0 0 1 0 0 0 1 0 reserve: 0 -1 0 -1 -1 -1 -1 -1 0 -1 0 0

For each column, to add retained to number, and to divide the sum by -2, to obtain the news retained , and the resulting bit as remains.

" To Be written things" , like below, better Be written. Empty sections are ugly.

Divisibility tests

To Be written.

Root extraction

To Be written.

--> See also binary, trinary system balanced, System négaternaire and number bases.

External resources

Vittorio Grunwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
A.J. Kempner. (1936), 610-617
Z. Pawlek and A. Wakulicz Bulletin of the Academy Polonaise of Scienses , Class III, 5 (1957), 233-236; Series of technical sciences 7 (1959), 713-721
L. Wadel ANGER Transactions EC-6 1957,123
NR. Mr. Blachman, Communications off the ACM (1961), 257
IEEE Transactions 1963,274-276
Computer Design May 1967, 52-63
R.W. Marczynski, Annotated History off Computing , 1980,37-48
D. Knuth. The Art off Computer Programming , 2,3rd Volume. ED. pp204-205

Random links: