Negative base

Encyclopedia

A

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,

(base 10),

(base 3), and

(base 2).

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.

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

. Implementations since then have been rare.

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 .

Negative-base systems may thus be compared to signed-digit representation

s, 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 . 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:

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.

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

programming language):

**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 decimalDecimal

The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....

(base 10),

**negaternary**(base −3) to ternaryTernary numeral system

Ternary is the base- numeral system. Analogous to a bit, a ternary digit is a trit . One trit contains \log_2 3 bits of information...

(base 3), and

**negabinary**(base −2) to binaryBinary numeral system

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.Negabinary was implemented in the early Polish

Poland

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...

. Implementations since then have been rare.

## Notation and use

Denoting the base as , every integerInteger

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 .

Negative-base systems may thus be compared to signed-digit representation

Signed-digit representation

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...

s, such as balanced ternary

Balanced ternary

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