 Negative base

Numeral systems by culture HinduArabic numerals Western Arabic
Eastern Arabic
Indian family
TamilBurmese
Khmer
Lao
Mongolian
ThaiEast Asian numerals Chinese
Japanese
SuzhouKorean
Vietnamese
Counting rodsAlphabetic numerals Abjad
Armenian
Āryabhaṭa
CyrillicGe'ez
Greek (Ionian)
HebrewOther systems Aegean
Attic
Babylonian
Brahmi
Egyptian
Etruscan
InuitKharosthi
Mayan
Quipu
Roman
Sumerian
UrnfieldList of numeral system topics Positional systems by base Decimal (10) 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 20, 24, 30, 36, 60, 64 List of numeral systems A negative base (or negative radix) may be used to construct a nonstandard positional numeral system. Like other placevalue 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 is equal to for some natural number (r ≥ 2).
Negativebase systems can accommodate all the same numbers as standard placevalue 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 negativebase number being one digit longer than its positivebase equivalent.
The common names for negativebase positional numeral systems are formed by prefixing nega to the name of the corresponding positivebase 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).^{[1]}
Contents
Example
Consider what is meant by the representation 12,243 in the negadecimal system, whose base is −10:
multiples of
(i.e., 10,000)multiples of
(i.e., −1,000)multiples of
(i.e., 100)multiples of
(i.e., −10)multiples of
(i.e., 1)1 2 2 4 3 Since 10,000 + (−2,000) + 200 + (−40) + 3 = 8,163, the representation 12,243 in negadecimal notation is equivalent to 8,163 in decimal notation.
History
Negative numerical bases were first considered by Vittorio Grünwald in his work Giornale di Matematiche di Battaglini, published in 1885. Grünwald 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 implemented in the early Polish computer BINEG, built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the Mathematical Institute in Warsaw.^{[2]} Implementations since then have been rare.
Notation and use
Denoting the base as − r, every integer a can be written uniquely as
where each digit is an integer from 0 to and the leading digit is (unless ). The base expansion of is then given by the string .
Negativebase systems may thus be compared to signeddigit 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 as in base r. For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal. Similarly,
 17 = 2^{4} + 2^{0} = ( − 2)^{4} + ( − 2)^{0}
and is represented by 10001 in binary and 10001 in negabinary.
Some numbers 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 −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 15 195 1111 10011 120 210 Note that the base expansions of negative integers have an even number of digits, while the base expansions of the nonnegative integers have an odd number of digits.
Calculation
The base expansion of a number can be found by repeated division by , recording the nonnegative remainders of , and concatenating those remainders, starting with the last. Note that if , remainder d, then . For example, in negaternary:
Therefore, the negaternary expansion of 146 is 21,102.
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 (shown below in the Python programming language):
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)
Arithmetic operations
The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.
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 Comment −2 0 1 −2 occurs only during subtraction. −1 1 1 0 0 0 1 1 0 2 0 −1 3 1 −1 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).
Another Method
While adding two negabinary numbers, everytime a carry is generated an extra carry should be propagated to next bit. Consider same example as above
extra carry: 1 1 0 1 0 0 0 carry: 1 0 1 1 0 1 0 0 0 first number: 1 0 1 0 1 0 1 second number: 1 1 1 0 1 0 0 +  Answer: 1 1 0 0 1 1 0 0 1
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.
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.
Fractional numbers
Base representation may of course be carried beyond the radix point, allowing the representation of nonintegral numbers.
As with positivebase 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.
Nonunique representations
Unlike positivebase systems, where integers and terminating fractions have nonunique representations (for example, in decimal 0.999… = 1) in negativebase systems the integers have only a single representation. However, there do exist rationals with nonunique representations; for example, in negaternary,
 .
Such nonunique 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 integralbase system.) The rationals thus nonuniquely expressible are those of form
 .
Imaginary base
Main article: Complex base systemsJust as using a negative base allows the representation of negative numbers without an explicit negative sign, using an imaginary base allows the representation of Gaussian integers. Donald Knuth proposed the quaterimaginary base (base 2i) in 1955.^{[3]}
Imaginarybase arithmetic is not much different from negativebase arithmetic, since an imaginarybase number may be considered as the interleave of its real and imaginary parts; using INTERCAL72 notation,
 x_{(2i)} + (2i)y_{(2i)} = x_{(2i)} ¢ y_{(2i)}.
See also
Notes
 ^ Knuth 1998 and Weisstein each refer to the negadecimal system. In the index Knuth 1998 refers to the negabinary system, as does Weisstein. The negaternary system is discussed briefly in Petkovšek, Marko (1990), "Ambiguous numbers are dense", The American Mathematical Monthly 97 (5): 408–411, doi:10.2307/2324393, ISSN 00029890, MR1048915.
 ^ Marczynski, R. W., "The First Seven Years of Polish Computing", IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980
 ^ D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. AddisonWesley. pp. 205, "Positional Number Systems"
References
 Vittorio Grünwald. Giornale di Matematiche di Battaglini (1885), 203221, 367
 A. J. Kempner. (1936), 610617
 Z. Pawlak and A. Wakulicz Bulletin de l'Academie Polonaise des Scienses, Classe III, 5 (1957), 233236; Serie des sciences techniques 7 (1959), 713721
 L. Wadel IRE Transactions EC6 1957, 123
 N. M. Blachman, Communications of the ACM (1961), 257
 IEEE Transactions 1963, 274276
 Computer Design May 1967, 5263
 R. W. Marczynski, Annotated History of Computing, 1980, 3748
 Knuth, Donald (1998), The Art of Computer Programming, Volume 2 (3rd ed.), pp. 204–205.
 Weisstein, Eric W., "Negabinary" from MathWorld.
 Weisstein, Eric W., "Negadecimal" from MathWorld.
Categories: Nonstandard positional numeral systems
 Computer arithmetic
Wikimedia Foundation. 2010.