A negative base 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 is equal to for some natural number (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
Sign bit
In computer science, the sign bit is a bit in a computer numbering format that indicates the sign of a number. In IEEE format, the sign bit is the leftmost 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
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
(base 2).
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.
Poland , officially the Republic of Poland , is a country in Central Europe bordered by Germany to the west; the Czech Republic and Slovakia to the south; Ukraine, Belarus and Lithuania to the east; and the Baltic Sea and Kaliningrad Oblast, a Russian exclave, to the north...
computer BINEG, built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the Mathematical Institute in Warsaw
Warsaw
Warsaw is the capital and largest city of Poland. It is located on the Vistula River, roughly from the Baltic Sea and from the Carpathian Mountains. Its population in 2010 was estimated at 1,716,855 residents with a greater metropolitan area of 2,631,902 residents, making Warsaw the 10th most...
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
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 .
Signed-digit representation of numbers indicates that digits can be prefixed with a − sign to indicate that they are negative.Signed-digit representation can be used in low-level software and hardware to accomplish fast addition of integers because it can eliminate carries...
Balanced ternary is a non-standard positional numeral system , useful for comparison logic. It is a ternary system, but unlike the standard ternary system, the digits have the values −1, 0, and 1...
, 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 . For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal. Similarly,
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 non-negative integers have an odd number of digits.
Calculation
The base expansion of a number can be found by repeated division by , recording the non-negative remainders of , and concatenating those remainders, starting with the last. Note that if , remainder , 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 to the quotient and remainder respectively (shown below in the Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
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 bit
Least significant bit
In computing, the least significant bit is the bit position in a binary integer giving the units value, that is, determining whether the number is even or odd. The lsb is sometimes referred to as the right-most bit, due to the convention in positional notation of writing less significant digits...
s, 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),
so the result is 110011001 (1 − 8 + 16 − 128 + 256 = 137).
Another Method
While adding two negabinary numbers, every-time 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),
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
numbers, but using the negabinary rules for adding the carry, when adding the numbers.
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
Radix point
In mathematics and computing, a radix point is the symbol used in numerical representations to separate the integer part of a number from its fractional part . "Radix point" is a general term that applies to all number bases...
, 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.
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
.
Imaginary base
Just as using a negative base allows the representation of negative numbers without an explicit negative sign, using an imaginary
Imaginary number
An imaginary number is any number whose square is a real number less than zero. When any real number is squared, the result is never negative, but the square of an imaginary number is always negative...
In number theory, a Gaussian integer is a complex number whose real and imaginary part are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. The Gaussian integers are a special case of the quadratic...
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
The quater-imaginary numeral system was first proposed by Donald Knuth in 1955, in a submission to a high-school science talent search. It is a non-standard positional numeral system which uses the imaginary number 2i as its base. It is able to uniquely represent every complex number using only...
(base 2i) in 1955.
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
INTERCAL
INTERCAL, a programming language parody, is an esoteric programming language that was created by Don Woods and James M. Lyon, two Princeton University students, in 1972. It satirizes aspects of the various programming languages at the time, as well as the proliferation of proposed language...
-72 notation,
x(2i) + (2i)y(2i) = x(2i) ¢ y(2i).
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
is equal to 
for some natural number 
(r ≥ 2).
is −10:
, every integer
can be written uniquely as
is an integer from 0 to 
and the leading digit 
is 
(unless 
). The base 
expansion of 
is then given by the string 
.
as in base 
. For example, the numbers from 100 to 109 have the same representations in decimal and negadecimal. Similarly,
expansions of negative integers have an even number of digits, while the base 
expansions of the non-negative integers have an odd number of digits.
expansion of a number can be found by repeated division by 
, recording the non-negative remainders of 
, and concatenating those remainders, starting with the last. Note that if 
, remainder 
, then 
. For example, in negaternary:
to the quotient and remainder respectively (shown below in the Python
representation may of course be carried beyond the radix point
.
.