Base −2
   HOME

TheInfoList



OR:

A negative base (or negative
radix In a positional numeral system, the radix (radices) or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system (the most common system in use today) the radix is ten, becaus ...
) 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 The plus sign () and the minus sign () are mathematical symbols used to denote positive and negative functions, respectively. In addition, the symbol represents the operation of addition, which results in a sum, while the symbol represent ...
(or, in computer representation, a
sign bit In computer science, the sign bit is a bit in a signed number representation that indicates the sign of a number. Although only signed numeric data types have a sign bit, it is invariably located in the most significant bit position, so the term ...
); 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 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of th ...
(base 10), negabinary (base −2) to
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two values (0 and 1) for each digit * Binary function, a function that takes two arguments * Binary operation, a mathematical op ...
(base 2), negaternary (base −3) to ternary (base 3), and negaquaternary (base −4) to
quaternary The Quaternary ( ) is the current and most recent of the three periods of the Cenozoic Era in the geologic time scale of the International Commission on Stratigraphy (ICS), as well as the current and most recent of the twelve periods of the ...
(base 4).


Example

Consider what is meant by the representation in the negadecimal system, whose base is −10: 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 Vittorio Grünwald (Verona, Italy, 13 June 1855 – Florence, Italy, March 1943) was an Italian professor of mathematics and German language. His father Guglielmo (Willhelm) Grünwald (son of Aronne and Regina) was Hungarian, his mother Fortuna ...
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 Warsaw, officially the Capital City of Warsaw, is the capital and List of cities and towns in Poland, largest city of Poland. The metropolis stands on the Vistula, River Vistula in east-central Poland. Its population is officially estimated at ...
. Implementations since then have been rare. zfp, a floating-point compression algorithm from the
Lawrence Livermore National Laboratory Lawrence Livermore National Laboratory (LLNL) is a Federally funded research and development centers, federally funded research and development center in Livermore, California, United States. Originally established in 1952, the laboratory now i ...
, 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 An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
can be written uniquely as : a = \sum_^d_(-r)^ 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 representation In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers. Signed-digit representation can be used to accomplish fast addition of integers becau ...
s, such as
balanced ternary Balanced ternary is a ternary numeral system (i.e. base 3 with three Numerical digit, digits) that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the stand ...
, 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, : 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 expansions of negative integers have an
even number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...
of digits, while the base expansions of the non-negative integers have an
odd number In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers. The ...
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 : -5 \div (-3) = 2 ~\mathrm~ 1 has to be chosen — and not = 3 ~\mathrm~ 4 nor = 1 ~\mathrm~ -\!2. For example, to convert 146 in decimal to negaternary: : \begin 146 \div (-3) = & -48 ~\mathrm~ 2 \\ -48 \div (-3) = & 16 ~\mathrm~ 0 \\ 16 \div (-3) = & -5 ~\mathrm~ 1 \\ -5 \div (-3) = & 2 ~\mathrm~ 1 \\ 2 \div (-3) = & 0 ~\mathrm~ 2 \end 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 A programming language is a system of notation for writing computer programs. Programming languages are described in terms of their syntax (form) and semantics (meaning), usually defined by a formal language. Languages usually provide features ...
, 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)


= C++

= auto to_negabinary(int value)


To negaternary


= C#

= static string Negaternary(int val)


= 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 negativeBase(int input, int base) 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 lst)


= 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 -2interval."))) (princ))))


Shortcut calculation

The following algorithms assume that # the input is available in
bitstring A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level p ...
s 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 D of output digits is standard, i. e. D = \ with base b\in \, # 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 JavaScript port for the same shortcut calculation: function toNegaBinary(value) The algorithm is first described by Schroeppel in the
HAKMEM HAKMEM, alternatively known as AI Memo 239, is a February 1972 "memo" ( technical report) of the MIT AI Lab containing a wide variety of hacks, including useful and clever algorithms for mathematical computation, some number theory and schemat ...
(1972) as item 128. The
Wolfram MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Dig ...
documents a version in the Wolfram Language by D. Librik (Szudzik).


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 JavaScript port for the same shortcut calculation: function toNegaQuaternary(value)


Arithmetic operations

The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.


Addition

Adding negabinary numbers proceeds bitwise, starting from the
least significant bit In computing, bit numbering is the convention used to identify the bit positions in a binary number. Bit significance and indexing In computing, the least significant bit (LSb) is the bit position in a binary integer representing the lowes ...
s; the bits from each addend are summed with the (
balanced ternary Balanced ternary is a ternary numeral system (i.e. base 3 with three Numerical digit, digits) that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the stand ...
) carry from the previous bit (0 at the LSB). 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. As an example, to add 1010101 (1 + 4 + 16 + 64 = 85) and 1110100 (4 + 16 − 32 + 64 = 52), Carry: 1 −1 0 −1 1 −1 0 0 0 First addend: 1 0 1 0 1 0 1 Second addend: 1 1 1 0 1 0 0 + -------------------------- Number: 1 −1 2 0 3 −1 2 0 1 Bit (result): 1 1 0 0 1 1 0 0 1 Carry: 0 1 −1 0 −1 1 −1 0 0 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 1 0 1 0 0 0 Carry: 0 1 1 0 1 0 0 0 First addend: 1 0 1 0 1 0 1 Second addend: 1 1 1 0 1 0 0 + -------------------------- Answer: 1 1 0 0 1 1 0 0 1


Negabinary full adder

A
full adder An adder, or summer, is a digital circuit that performs addition of numbers. In many computers and other kinds of processors, adders are used in the arithmetic logic units (ALUs). They are also used in other parts of the processor, where they ar ...
circuit can be designed to add numbers in negabinary. The following logic is used to calculate the sum and carries: : s_i = a_i \oplus b_i \oplus c_i^+ \oplus c_i^- : c_^+ = \overline\overline\overlinec_i^- : c_^- = a_i b_i \overline + (a_i \oplus b_i)c_i^+ \overline


Incrementing negabinary numbers

Incrementing a negabinary number can be done by using the following formula: : 2x \oplus ((2x \oplus x) + 1) (The operations in this formula are to be interpreted as operations on regular binary numbers. For example, 2x is a binary left shift by one bit.)


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), Carry: 0 1 −1 1 0 0 0 First number: 1 1 0 1 0 0 1 Second number: −1 −1 −1 0 −1 0 0 + -------------------- Number: 0 1 −2 2 −1 0 1 Bit (result): 0 1 0 0 1 0 1 Carry: 0 0 1 −1 1 0 0 so the result is 100101 (1 + 4 −32 = −27). Unary negation, , can be computed as binary subtraction from zero, .


Multiplication and division

Shifting to the left multiplies by −2, shifting to the right divides by −2. To multiply, multiply like normal
decimal The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of th ...
or
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two values (0 and 1) for each digit * Binary function, a function that takes two arguments * Binary operation, a mathematical op ...
numbers, but using the negabinary rules for adding the carry, when adding the numbers. First number: 1 1 1 0 1 1 0 Second number: 1 0 1 1 0 1 1 × ------------------------------------- 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 + ------------------------------------- Carry: 0 −1 0 −1 −1 −1 −1 −1 0 −1 0 0 Number: 1 0 2 1 2 2 2 3 2 0 2 1 0 Bit (result): 1 0 0 1 0 0 0 1 0 0 0 1 0 Carry: 0 −1 0 −1 −1 −1 −1 −1 0 −1 0 0 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.


Comparing negabinary numbers

It is possible to compare negabinary numbers by slightly adjusting a normal unsigned binary comparator. When comparing the numbers A and B, invert each odd positioned bit of both numbers. After this, compare A and B using a standard unsigned comparator.


Fractional numbers

Base representation may of course be carried beyond the
radix point alt=Four types of separating decimals: a) 1,234.56. b) 1.234,56. c) 1'234,56. d) ١٬٢٣٤٫٥٦., Both a full_stop.html" ;"title="comma and a full stop">comma and a full stop (or period) are generally accepted decimal separators for interna ...
, allowing the representation of non-integer 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 the digits with \mathbf:=r - 1 = -b - 1 the biggest digit and : T:=0.\overline_b = \sum_^ b^ = \frac1 = \frac1 we have : 0.\overline_b=\mathbfT=\frac=\frac1     as well as : 1.\overline_b = 1+\mathbfbT = \frac= \frac1. So every number \frac1+z with a terminating fraction z\in \Z r^ added has two distinct representations. For example, in negaternary, i.e. b=-3 and \mathbf=2, there is : 1.\overline_ = \frac = 2.\overline_. Such non-unique representations can be found by considering the largest and smallest possible representations with integer parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integer-base system.) The rationals thus non-uniquely expressible are those of form : \frac with z,i\in \Z.


Imaginary base

Just as using a negative base allows the representation of negative numbers without an explicit negative sign, using an imaginary base allows the representation of
Gaussian integer In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as \mathbf ...
s.
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
proposed the
quater-imaginary base The quater-imaginary numeral system is a numeral system, first proposed by Donald Knuth in 1960. Unlike standard numeral systems, which use an integer (such as 10 in decimal, or 2 in binary) as their bases, it uses the imaginary number 2i (such ...
(base 2i) in 1955.D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"


See also

*
Quater-imaginary base The quater-imaginary numeral system is a numeral system, first proposed by Donald Knuth in 1960. Unlike standard numeral systems, which use an integer (such as 10 in decimal, or 2 in binary) as their bases, it uses the imaginary number 2i (such ...
*
Binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two values (0 and 1) for each digit * Binary function, a function that takes two arguments * Binary operation, a mathematical op ...
*
Balanced ternary Balanced ternary is a ternary numeral system (i.e. base 3 with three Numerical digit, digits) that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the stand ...
*
Quaternary numeral system Quaternary is a numeral system with four as its base. It uses the digits 0, 1, 2, and 3 to represent any real number. Conversion from binary is straightforward. Four is the largest number within the subitizing range and one of two numbers ...
*
Numeral system A numeral system is a writing system for expressing numbers; that is, a mathematical notation for representing numbers of a given set, using digits or other symbols in a consistent manner. The same sequence of symbols may represent differe ...
s *
1 − 2 + 4 − 8 + ⋯ In mathematics, is the infinite series whose terms are the successive powers of two with alternating signs. As a geometric series, it is characterized by its first term, 1, and its common ratio, −2. : \sum_^ (-2)^k As a series of real numbers, ...
(
p-adic numbers In number theory, given a prime number , the -adic numbers form an extension of the rational numbers which is distinct from the real numbers, though with some similar properties; -adic numbers can be written in a form similar to (possibly infin ...
)


References


Further reading

*


External links

* * {{MathWorld, title=Negadecimal, urlname=Negadecimal Non-standard positional numeral systems Computer arithmetic