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), negabinary (base −2) to binary (base 2), negaternary (base −3) to ternary (base 3), and negaquaternary (base −4) to quaternary (base 4).
Example Consider what is meant by the representation 12243 in the negadecimal system, whose base b is −10:
The representation 12243−10 (which is intended to be negadecimal notation) is equivalent to 8,16310 in decimal notation, because 10,000 + (−2,000) + 200 + (−40) + 3 = 8163.
Remark
On the other hand, −816310 in decimal would be written 9977−10 in negadecimal.
History Negative numerical bases were first considered by Vittorio Grünwald in an 1885 monograph published in Giornale di Matematiche di Battaglini. Grünwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later mentioned in passing by A. J. Kempner in 1936 and studied in more detail by Zdzisław Pawlak and A. Wakulicz in 1957. 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. Implementations since then have been rare. zfp, a floating-point compression algorithm from the Lawrence Livermore National Laboratory, uses negabinary to store numbers. According to zfp's documentation:
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.
Notation and use Denoting the base as −r, every integer a can be written uniquely as
a = ∑ i = 0 n d i ( − r ) i {\displaystyle a=\sum _{i=0}^{n}d_{i}(-r)^{i}}
where each digit dk is an integer from 0 to r − 1 and the leading digit dn > 0 (unless n = 0). The base −r expansion of a is then given by the string dndn−1...d1d0. 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. Similarly,
17 = 2 4 + 2 0 = ( − 2 ) 4 + ( − 2 ) 0 {\displaystyle 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:
Note that, with the exception of nega balanced ternary, 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.
Calculation The base −r expansion of a number can be found by repeated division by −r, recording the non-negative remainders in { 0 , 1 , … , r − 1 } {\displaystyle \{0,1,\ldots ,r-1\}} , and concatenating those remainders, starting with the last. Note that if a / b is c with remainder d, then bc + d = a and therefore d = a − bc. To arrive at the correct conversion, the value for c must be chosen such that d is non-negative and minimal. For the fourth line of the following example this means that
− 5 ÷ ( − 3 ) = 2 r e m a i n d e r 1 {\displaystyle -5\div (-3)=2~\mathrm {remainder} ~1}
has to be chosen — and not = 3 r e m a i n d e r 4 {\displaystyle =3~\mathrm {remainder} ~4} nor = 1 r e m a i n d e r − 2. {\displaystyle =1~\mathrm {remainder} ~-\!2.}
For example, to convert 146 in decimal to negaternary:
… excerpt ends here. Continue reading the full article.
