Negative base

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.

Negative bases were later mentioned in passing by A. J. Kempner in 1936[4] and studied in more detail by Zdzisław Pawlak and A. Wakulicz in 1957.

[5] Negabinary was implemented in the early Polish computer BINEG (and UMC), built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the Mathematical Institute in Warsaw.

zfp, a floating-point compression algorithm from the Lawrence Livermore National Laboratory, uses negabinary to store numbers.

According to zfp's documentation:[7] Unlike sign-magnitude representations, the leftmost one-bit in negabinary simultaneously encodes the sign and approximate magnitude of a number.

Moreover, unlike two’s complement, numbers small in magnitude have many leading zeros in negabinary regardless of sign, which facilitates encoding.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 > 0 (unless n = 0).

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.

(In the table below the digit of value −1 is written as the single character T.) 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.

The base −r expansion of a number can be found by repeated division by −r, recording the non-negative remainders in

To arrive at the correct conversion, the value for c must be chosen such that d is non-negative and minimal.

Reading the remainders forward we can obtain the negaternary least-significant-digit-first representation.

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

The above gives the result in an ArrayList of integers, so that the code does not have to handle how to represent a base smaller than -10.

To display the result as a string, one can decide on a mapping of base to characrters.

For example: The following algorithms assume that The conversion to negabinary (base −2; digits in

) allows a similar shortcut (C implementation): JavaScript port for the same shortcut calculation: The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.

This sum is then decomposed into an output bit and carry for the next iteration as show in the table: 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.

Consider same example as above A full adder circuit can be designed to add numbers in negabinary.

The following logic is used to calculate the sum and carries:[9] Incrementing a negabinary number can be done by using the following formula:[10] (The operations in this formula are to be interpreted as operations on regular binary numbers.

Unary negation, −x, can be computed as binary subtraction from zero, 0 − x.

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.

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.