Negative base
From Wikipedia, the free encyclopedia
Numeral systems by culture | |
---|---|
Hindu-Arabic numerals | |
Indian Eastern Arabic Khmer |
Indian family Brahmi Thai |
East Asian numerals | |
Chinese Suzhou Counting rods |
Japanese Korean |
Alphabetic numerals | |
Abjad Armenian Cyrillic Ge'ez |
Hebrew Greek (Ionian) Āryabhaṭa |
Other systems | |
Attic Babylonian Egyptian Etruscan |
Mayan Roman Urnfield |
List of numeral system topics | |
Positional systems by base | |
Decimal (10) | |
2, 4, 8, 16, 32, 64 | |
1, 3, 9, 12, 20, 24, 30, 36, 60, more… | |
A negative base (or negative radix) may be used to construct a non-standard positional numeral system. Like other place-value systems, each position holds multiples of the appropriate power of the system's base; but that base is negative — that is to say, the base b is equal to − r for some natural number r (r≥2).
Negative-base systems can accommodate all the same numbers as standard place-value systems; but both positive and negative numbers are represented without the use of a minus sign (or, in computer representation, a sign bit); this advantage is countered by an increased complexity of arithmetic operations. The need to store the "information" normally contained by a negative sign often results in a negative-base number being one digit longer than its positive-base equivalent.
The common names for negative-base positional numeral systems are formed by prefixing nega- to the name of the corresponding positive-base system; for example, negadecimal (base -10) corresponds to decimal (base 10), negaternary (base -3) to ternary (base 3), and negabinary (base -2) to binary (base 2).
Contents |
[edit] Example
Consider what is meant by the representation 12243 in the negadecimal system, whose base b is -10:
multiples of b4 (i.e. 10000) |
multiples of b3 (i.e. -1000) |
multiples of b2 (i.e. 100) |
multiples of b1 (i.e. -10) |
multiples of b0 (i.e. 1) |
1 | 2 | 2 | 4 | 3 |
Since 10000 + (-2000) + 200 + (-40) + 3 = 8163, the representation 12243 in negadecimal notation is equivalent to 8163 in decimal notation.
[edit] History
Negative numerical bases were first considered by Vittorio Grunwald in his work Giornale di Matematiche di Battaglini, published in 1885. Grunwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later independently rediscovered by A. J. Kempner in 1936 and Zdzisław Pawlak and A. Wakulicz in 1959.
Negabinary was first implemented in computer hardware in the experimental Polish computers SKRZAT 1 and BINEG in 1950. Implementations since then have been rare.
[edit] Notation and use
Denoting the base as − r, every integer a can be written uniquely as
where each digit dk is an integer from 0 to r − 1 and the leading digit dn is > 0 (unless n = 0). The base − r expansion of a is then given by the string .
Negative-base systems may thus be compared to signed-digit representations, such as balanced ternary, where the radix is positive but the digits are taken from a partially negative range.
Some numbers have the same representation in base − r as in base r. For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal. Similarly,
- 17 = 24 + 20 = ( − 2)4 + ( − 2)0
and is represented by 10001 in binary and 10001 in negabinary.
The numbers -15 to 15 with their expansions in a number of positive and corresponding negative bases are:
Decimal | Negadecimal | Binary | Negabinary | Ternary | Negaternary |
---|---|---|---|---|---|
-15 | 25 | -1111 | 110001 | -120 | 1220 |
-14 | 26 | -1110 | 110110 | -112 | 1221 |
-13 | 27 | -1101 | 110111 | -111 | 1222 |
-12 | 28 | -1100 | 110100 | -110 | 1210 |
-11 | 29 | -1011 | 110101 | -102 | 1211 |
-10 | 10 | -1010 | 1010 | -101 | 1212 |
-9 | 11 | -1001 | 1011 | -100 | 1200 |
-8 | 12 | -1000 | 1000 | -22 | 1201 |
-7 | 13 | -111 | 1001 | -21 | 1202 |
-6 | 14 | -110 | 1110 | -20 | 20 |
-5 | 15 | -101 | 1111 | -12 | 21 |
-4 | 16 | -100 | 1100 | -11 | 22 |
-3 | 17 | -11 | 1101 | -10 | 10 |
-2 | 18 | -10 | 10 | -2 | 11 |
-1 | 19 | -1 | 11 | -1 | 12 |
0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 |
2 | 2 | 10 | 110 | 2 | 2 |
3 | 3 | 11 | 111 | 10 | 120 |
4 | 4 | 100 | 100 | 11 | 121 |
5 | 5 | 101 | 101 | 12 | 122 |
6 | 6 | 110 | 11010 | 20 | 110 |
7 | 7 | 111 | 11011 | 21 | 111 |
8 | 8 | 1000 | 11000 | 22 | 112 |
9 | 9 | 1001 | 11001 | 100 | 100 |
10 | 190 | 1010 | 11110 | 101 | 101 |
11 | 191 | 1011 | 11111 | 102 | 102 |
12 | 192 | 1100 | 11100 | 110 | 220 |
13 | 193 | 1101 | 11101 | 111 | 221 |
14 | 194 | 1110 | 10010 | 112 | 222 |
15 | 195 | 1111 | 10011 | 120 | 210 |
Note that the base − r expansions of negative integers have an even number of digits, while the base − r expansions of the non-negative integers have an odd number of digits.
[edit] Calculation
The base − r expansion of a number can be found by repeated division by − r, recording the non-negative remainders of , and concatenating those remainders, starting with the last. Note that if a / b = c, remainder d, then bc + d = a. For example, in negaternary:
Therefore, the negaternary expansion of 146 is 21102.
Note that in most programming languages, the result (in integer arithmetic) of dividing a negative number by a negative number is rounded towards 0, usually leaving a negative remainder; to get the correct result in such case, computer implementations of the above algorithm should add 1 and r to the quotient and remainder respectively:
def negaternary(i):
digits = []
while i != 0:
i, remainder = divmod (i, -3)
if (remainder < 0):
i, remainder = i + 1, remainder + 3
digits.insert (0, str (remainder))
return ''.join (digits)
[edit] Arithmetic operations
The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.
[edit] Addition
To add two negabinary numbers, start with a carry of 0, and, starting from the least significant bits, add the bits of the two numbers plus the carry. The resulting number is then looked up in the following table to get the bit to write down as result, and the next carry:
number bit carry -2 0 1 (Note: -2 occurs only during subtraction.) -1 1 1 0 0 0 1 1 0 2 0 -1 3 1 -1 (Note: 3 occurs only during addition.)
The second row of this table, for instance, expresses the fact that -1 = 1 + 1×(-2); the fifth row says 2 = 0 + -1×(-2); etc.
As an example, to add 1010101 (1+4+16+64 = 85) and 1110100 (4+16-32+64 = 52),
carry: 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 carry: 0 1 -1 0 -1 1 -1 0 0
so the result is 110011001 (1-8+16-128+256 = 137).
[edit] Subtraction
To subtract, multiply each bit of the second number by -1, and add the numbers, using the same table as above.
As an example, to compute 1101001 (1-8-32+64 = 25) minus 1110100 (4+16-32+64 = 52),
carry: 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 carry: 0 0 1 -1 1 0 0
so the result is 100101 (1+4-32 = -27).
To negate a number, compute 0 minus the number.
[edit] Multiplication and division
Shifting to the left multiplies by -2, shifting to the right divides by -2.
To multiply, multiply like normal decimal or binary numbers, but using the negabinary rules for adding the carry, when adding the numbers.
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 + ------------------------------------- carry: 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 carry: 0 -1 0 -1 -1 -1 -1 -1 0 -1 0 0
For each column, add carry to number, and divide the sum by -2, to get the new carry, and the resulting bit as the remainder.
[edit] Fractional numbers
Base − r representation may of course be carried beyond the radix point, allowing the representation of non-integral numbers.
As with positive-base systems, terminating representations correspond to fractions where the denominator is a power of the base; repeating representations correspond to other rationals, and for the same reason.
[edit] Non-unique representations
Unlike positive-base systems, where integers and terminating fractions have non-unique representations (for example, in decimal 0.999... = 1) in negative-base systems the integers have only a single representation. However, there do exist rationals with non-unique representations; for example, in negaternary,
- .
Such non-unique representations can be found by considering the largest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integral-base system.) The rationals thus non-uniquely expressible are those of form
- .
[edit] Imaginary base
The construction of the integers from the natural numbers, and of the complex numbers from the reals, suggests the use of an imaginary number as the radix of a number system. The earliest known imaginary-base number system is the quater-imaginary base, first proposed by Donald Knuth in 1955, with radix 2i and digits 0, 1, 2, and 3; it can represent any complex number in a single string without the use of i or minus sign.[1]
Imaginary-base arithmetic is not much different from negative-base arithmetic, since an imaginary-base number may be considered as the interleave of its real and imaginary parts; using INTERCAL-72 notation,
- x(2i) + (2i)y(2i) = x(2i) ¢ y(2i).
Further extension to hexadeci-quaternion or even hexapenintadiacosi-octonion bases is possible, but not particularly useful.
[edit] See also
[edit] References
- ^ D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"
- Vittorio Grunwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
- A. J. Kempner. (1936), 610-617
- Z. Pawlak and 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 May 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
- Weisstein, Eric W. "Negadecimal." From MathWorld--A Wolfram Web Resource.