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 is equal to for some natural number ().
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).. Knuth mentions both negabinary and negadecimal.The negaternary system is discussed briefly in
Example Consider what is meant by the representation in the negadecimal system, whose base is −10:
+ Multiples of 1 2 2 4 3 The representation (which is intended to be negadecimal notation) is equivalent to in decimal notation, because 10,000 + (−2,000) + 200 + (−40) + 3 = . Remark On the other hand, in decimal would be written in negadecimal.
History Negative numerical bases were first considered by Vittorio Grünwald in an 1885 monograph published in Giornale di Matematiche di Battaglini.Vittorio Grünwald. Intorno all'aritmetica dei sistemi numerici a base negativa con particolare riguardo al sistema numerico a base negativo-decimale per lo studio delle sue analogie coll'aritmetica ordinaria (decimale), Giornale di Matematiche di Battaglini (1885), 203-221, 367 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. The only reference to negative bases is a footnote on page 610, which reads, "Positive numbers less than 1 and negative numbers may be used as bases with slight modifications of the process and suitable restrictions on the set of digits employed." 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.Marczynski, R. W., "The First Seven Years of Polish Computing" , IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980 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 , every integer can be written uniquely as
where each digit is an integer from 0 to and the leading digit (unless ). The base expansion of is then given by the string .
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 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 Balanced ternary Balanced negaternary Quaternary Negaquaternary −15 25 −1111 110001 −120 1220 T110 11T0 −33 1301 ⋮ −5 15 −101 1111 −12 21 T11 TT1 −11 23 −4 16 −100 1100 −11 22 TT 1T −10 10 −3 17 −11 1101 −10 10 T0 10 −3 11 −2 18 −10 10 −2 11 T1 11 −2 12 −1 19 −1 11 −1 12 T T −1 13 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 10 110 2 2 1T TT 2 2 3 3 11 111 10 120 10 T0 3 3 4 4 100 100 11 121 11 T1 10 130 5 5 101 101 12 122 1TT 11T 11 131 6 6 110 11010 20 110 1T0 110 12 132 7 7 111 11011 21 111 1T1 111 13 133 8 8 1000 11000 22 112 10T 10T 20 120 9 9 1001 11001 100 100 100 100 21 121 10 190 1010 11110 101 101 101 101 22 122 11 191 1011 11111 102 102 11T 1TT 23 123 12 192 1100 11100 110 220 110 1T0 30 110 13 193 1101 11101 111 221 111 1T1 31 111 14 194 1110 10010 112 222 1TTT TT1T 32 112 15 195 1111 10011 120 210 1TT0 TT10 33 113 16 196 10000 10000 121 211 1TT1 TT11 100 100 17 197 10001 10001 122 212 1T0T TT0T 101 101 18 198 10010 10110 200 200 1T00 TT00 102 102
Note that, with the exception of nega balanced ternary, 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 in , and concatenating those remainders, starting with the last. Note that if is with remainder , then and therefore . To arrive at the correct conversion, the value for must be chosen such that is non-negative and minimal. For the fourth line of the following example this means that
has to be chosen — and not nor
For example, to convert 146 in decimal to negaternary:
Reading the remainders backward we obtain the negaternary representation of 14610: 21102–3. Proof: −3 · (−3 · (−3 · (−3 · ( 2 ) + 1 ) + 1 ) + 0 ) + 2 = (((2 · (−3) + 1) · (−3) + 1) · (−3) + 0) · (−3) + 2 = 14610. Reading the remainders forward we can obtain the negaternary least-significant-digit-first representation.
Proof: 2 + ( 0 + ( 1 + ( 1 + ( 2 ) · −3 ) · −3) · −3 ) · −3 = 14610.
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. In such a case we have . Because , is the positive remainder. Therefore, to get the correct result in such case, computer implementations of the above algorithm should add 1 and to the quotient and remainder respectively.
Example implementation code To negabinary C# static string ToNegabinary(int val) { string result = string.Empty;
while (val != 0) { int remainder = val % -2; val = val / -2;
if (remainder < 0)
remainder += 2; val += 1;
result = remainder.ToString() + result;
return result; }
C++ auto to_negabinary(int value) { std::bitset<sizeof(int) * CHAR_BIT > result; std::size_t bit_position = 0;
while (value != 0)
const auto div_result = std::div(value, -2);
if (div_result.rem < 0) value = div_result.quot + 1; else value = div_result.quot;
result.set(bit_position, div_result.rem != 0);
++bit_position;
return result; }
To negaternary C# static string Negaternary(int val) { string result = string.Empty;
while (val != 0) { int remainder = val % -3; val = val / -3;
if (remainder < 0)
remainder += 3; val += 1;
result = remainder.ToString() + result;
return result; }
Python def negaternary(i: int) -> str: """Decimal to negaternary""" if i == 0: digits = ["0"] else: digits = [] while i != 0: i, remainder = divmod(i, -3) if remainder < 0: i, remainder = i + 1, remainder + 3 digits.append(str(remainder)) return "".join(digits[::-1]) >>> negaternary(1000) '2212001'
Common Lisp (defun negaternary (i) (if (zerop i) "0" (let ((digits "") (rem 0)) (loop while (not (zerop i)) do (progn (multiple-value-setq (i rem) (truncate i -3)) (when (minusp rem) (incf i) (incf rem 3)) (setf digits (concatenate 'string (write-to-string rem) digits)))) digits)))
To any negative base
Java import java.util.ArrayList; import java.util.Collections; public ArrayList<Integer> negativeBase(int input, int base) { ArrayList<Integer> result_rev = new ArrayList<>(); int number = input; while (number != 0) { int i = number % base; number /= base; if (i < 0) { i += Math.abs(base); number++;
result_rev.add(i);
return Collections.reverse(result_rev.clone()); } 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: import java.util.stream.Collectors; final String alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@_"; public String toBaseString(ArrayList<Integer> lst) { // Would throw exception if base is beyond the 64 possible characters return lst.stream().map(n -> alphabet[n]).collect(Collectors.joining("")); }
AutoLisp (defun negabase (num baz / dig rst) ;; NUM is any number. ;; BAZ is any number in the interval [-10, -2]. (This is forced by how we do string notation.)
;; NUM and BAZ will be truncated to an integer if they're floats (e.g. 14.25 ;; will be truncated to 14, -123456789.87 to -123456789, etc.). (if (and (numberp num) (numberp baz) (<= (fix baz) -2) (> (fix baz) -11)) (progn (setq baz (float (fix baz)) num (float (fix num)) dig (if (= num 0) "0" "")) (while (/= num 0) (setq rst (- num (* baz (setq num (fix (/ num baz)))))) (if (minusp rst) (setq num (1+ num) rst (- rst baz))) (setq dig (strcat (itoa (fix rst)) dig))) dig) (progn (prompt (cond ((and (not (numberp num)) (not (numberp baz))) "\nWrong number and negabase.") ((not (numberp num)) "\nWrong number.") ((not (numberp baz)) "\nWrong negabase.") (t "\nNegabase must be inside [-10 -2] interval."))) (princ))))
Shortcut calculation The following algorithms assume that the input is available in bitstrings and coded in (base +2; digits in ) (as in most of today's digital computers), there are add () and xor () operations, which operate on such bitstrings (as in most of today's digital computers), the set of output digits is standard, i. e. with base , the output is coded in the same bitstring format, but the meaning of the places is another one.
To negabinary The conversion to negabinary (base −2; digits in ) allows a remarkable shortcut (C implementation): uint32_t toNegaBinary(uint32_t value) // input in standard binary { uint32_t Schroeppel2 = 0xAAAAAAAA; // = 2/3*((2*2)^16-1) = ...1010 return (value + Schroeppel2) ^ Schroeppel2; // eXclusive OR // resulting unsigned int to be interpreted as string of elements ε {0,1} (bits) }
JavaScript port for the same shortcut calculation: function toNegaBinary(value) { const Schroeppel2 = 0xAAAAAAAA; // Convert as in C, then convert to a NegaBinary String return ( ( value + Schroeppel2 ) ^ Schroeppel2 ).toString(2); }
The algorithm is first described by Schroeppel in the HAKMEM (1972) as item 128. The Wolfram MathWorld documents a version in the Wolfram Language by D. Librik (Szudzik).See the MathWorld Negabinary link. Specifically, the references are: Szudzik, M. "Programming Challenge: A Mathematica Programming Contest". Wolfram Technology Conference, 1999. Schroeppel, R. Item 128 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 24, Feb. 1972. http://www.hakmem.org/#item128
To negaquaternary The conversion to negaquaternary (base −4; digits in ) allows a similar shortcut (C implementation): uint32_t toNegaQuaternary(uint32_t value) // input in standard binary {