Negative base

Numeral systems

Hindu–Arabic numeral system
Western Arabic Eastern Arabic Bengali Gurmukhi Indian Sinhala Tamil Balinese Burmese Dzongkha Javanese Khmer Lao Mongolian Thai
East Asian
Chinese Suzhou Hokkien Japanese Korean Vietnamese Counting rods
Alphabetic
Abjad Armenian Āryabhaṭa Cyrillic Ge'ez Georgian Greek Hebrew Roman
Former
Aegean Attic Babylonian Brahmi Egyptian Etruscan Inuit Kharosthi Mayan Muisca Quipu Prehistoric
Positional systems by base
2 3 4 5 6 8 10 12 16 20 60
Non-standard positional numeral systems
Bijective numeration (1) Signed-digit representation (Balanced ternary) factorial negative Complex-base system (2i) Non-integer representation (φ) mixed
List of numeral systems

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 \geq 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), and negaternary (base −3) to ternary (base 3).^[1]^[2]

Example

Consider what is meant by the representation 12,243 in the negadecimal system, whose base $b$ is −10:

Multiples of
$(-10) 4 = 10,000$	$(-10) 3 = -1,000$	$(-10) 2 = 100$	$(-10) 1 = -10$	$(-10) 0 = 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, while −8,163₁₀ in decimal would be written 9,977₋₁₀ in negadecimal.

History

Negative numerical bases were first considered by Vittorio Grünwald in his work Giornale di Matematiche di Battaglini, published in 1885.^[3] 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^[4] and Zdzisław Pawlak and A. Wakulicz in 1959.^[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.^[6] Implementations since then have been rare.

Notation and use

Denoting the base as $-r$ , every integer $a$ can be written uniquely as

a=\sum _{{i=0}}^{{n}}d_{{i}}(-r)^{{i}}

where each digit $d k$ is an integer from 0 to $r - 1$ and the leading digit $d n$ is $> 0$ (unless $n = 0$ ). The base $-r$ expansion of $a$ is then given by the string $d n d n -1 \dots d 1 d 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.

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}

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
6	6	110	11010	20	110
7	7	111	11011	21	111
8	8	1000	11000	22	112
9	9	1001	11001	100	100
10	190	1010	11110	101	101
11	191	1011	11111	102	102
12	192	1100	11100	110	220
13	193	1101	11101	111	221
14	194	1110	10010	112	222
15	195	1111	10011	120	210
16	196	10000	10000	121	211
17	197	10001	10001	122	212

Note that 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 of $0,1,\ldots ,r-1$ , and concatenating those remainders, starting with the last. Note that if $a / b = c$ , remainder $d$ , then $bc + d = a$ . For example, in negaternary:

{\begin{aligned}146&~/~-3=&-48,&~{\mbox{remainder}}~2\\-48&~/~-3=&16,&~{\mbox{remainder}}~0\\16&~/~-3=&-5,&~{\mbox{remainder}}~1\\-5&~/~-3=&2,&~{\mbox{remainder}}~1\\2&~/~-3=&0,&~{\mbox{remainder}}~2\\\end{aligned}}

Reading the remainders backward we obtain the negaternary expression of 146: 21102.

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 $a = (- r) c + d = (- r) c + d - r + r = (- r)(c + 1) + (d + r)$ . Because $|d| < r$ , $(d + r)$ is the positive remainder. 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 (shown below in the Python programming language):

def negaternary(i):
    digits = []
    if not i:
        digits = ['0']
    else:
        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])

Negabinary C# implementation:

static string ToNegabinary(int value)
{
	string result = string.Empty;

	while (value != 0)
	{
		int remainder = value % -2;
		value = value / -2;

		if (remainder < 0)
		{
			remainder += 2;
			value += 1;
		}

		result = remainder.ToString() + result;
	}

	return result;
}

C# implementation:

static string negaternary(int value)
{
	string result = string.Empty;

	while (value != 0)
	{
		int remainder = value % -3;
		value = value / -3;

		if (remainder < 0)
		{
			remainder += 3;
			value += 1;
		}

		result = remainder.ToString() + result;
	}

	return result;
}

Common Lisp implementation:

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

Visual Basic implementation:

 1 Private Shared Function ToNegaternary(value As Integer) As String
 2 	Dim result As String = String.Empty
 3 
 4 	While value <> 0
 5 		Dim remainder As Integer = value Mod -3
 6 		value /= -3
 7 
 8 		If remainder < 0 Then
 9 			remainder += 3
10 			value += 1
11 		End If
12 
13 		result = remainder.ToString() & result
14 	End While
15 
16 	Return result
17 End Function

To negative base

PHP implementation. The conversion from integer to some negative base:

function toNegativeBase($no, $base)
{
	$digits = array();
	$base = intval($base);
	while ($no != 0) {
		$temp_no = $no;
		$no = intval($temp_no / $base);
		$remainder = ($temp_no % $base);
 
		if ($remainder < 0) {
			$remainder += abs($base);
			$no++;
		}
 
		array_unshift($digits, $remainder);
	}
 
	return $digits;
}

Visual Basic implementation:

Function toNegativeBase(Number As Integer , base As Integer) As System.Collections.Generic.List(Of Integer)

	Dim digits As New System.Collections.Generic.List(Of Integer)
	while Number <> 0
		Dim remainder As Integer= Number Mod base
		Number = CInt(Number / base)
 
		if remainder < 0 then
			remainder += system.math.abs(base)
			Number+=1
		end if
 
		digits.Insert(0, remainder)
	end while
 
	return digits
end function

To negabinary

The conversion to negabinary (base −2; digits $\in \;\{0,1\}$ ) allows a remarkable shortcut (C implementation):

unsigned int toNegaBinary(unsigned int value) // input in standard binary
{
	unsigned int 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)
}

Due to D. Librik (Szudzik). The bitwise XOR portion is originally due to Schroeppel (1972).^[7]

JavaScript port for the same shortcut calculation:

function toNegaBinary( number ) {
    var Schroeppel2 = 0xAAAAAAAA;
    // Convert to NegaBinary String
    return ( ( number + Schroeppel2 ) ^ Schroeppel2 ).toString(2);
}

To negaquaternary

The conversion to negaquaternary (base −4; digits $\in \;\{0,1,2,3\}$ ) allows a similar shortcut (C implementation):

unsigned int toNegaQuaternary(unsigned int value) // input in standard binary
{
	unsigned int Schroeppel4 = 0xCCCCCCCC; // = 4/5*((2*4)^8-1) = ...11001100 = ...3030
	return (value + Schroeppel4) ^ Schroeppel4; // eXclusive OR
	// resulting unsigned int to be interpreted as string of elements ε {0,1,2,3} (pairs of bits)
}

JavaScript port for the same shortcut calculation:

function toNegaQuaternary( number ) {
    var Schroeppel4 = 0xCCCCCCCC;
    // Convert to NegaQuaternary String
    return ( ( number + Schroeppel4 ) ^ Schroeppel4 ).toString(4);
}

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 bits; the bits from each addend are summed with the (balanced ternary) 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:

Sum		Output			Comment
Sum		Bit	Carry		Comment
−2	010₋₂	0	1	01₋₂	−2 occurs only during subtraction.
−1	011₋₂	1	1	01₋₂
0	000₋₂	0	0	00₋₂
1	001₋₂	1	0	00₋₂
2	110₋₂	0	−1	11₋₂
3	111₋₂	1	−1	11₋₂	3 occurs only during addition.

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  0  1  0  0  0     
Carry:          1  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

Incrementing negabinary numbers

Incrementing a negabinary number can be done by using the following formula:^[8]

2x\oplus ((2x\oplus x)+1)

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, $- x$ , can be computed as binary subtraction from zero, $0 - x$ .

Multiplication and division

Shifting to the left multiplies by −2, shifting to the right divides by −2.

To multiply, multiply like normal decimal or binary 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.^[9]

Fractional numbers

Base $-r$ representation may of course be carried beyond the radix point, allowing the representation of non-integral 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 {0, 1, …, t} with $\mathbf {t} :=r\!-\!\!1=-b\!-\!\!1$ the biggest digit and

T:=0.{\overline {01}}_{b}=\sum _{i=1}^{\infty }b^{-2i}={\frac {1}{b^{2}-1}}={\frac {1}{r^{2}-1}}

we have

0.{\overline {0\mathbf {t} }}_{b}=\mathbf {t} T={\frac {r\!-\!\!1}{r^{2}-1}}={\frac {1}{r+1}}

as well as

1.{\overline {\mathbf {t} 0}}_{b}=1+\mathbf {t} bT={\frac {(r^{2}-1)+(r\!-\!\!1)b}{r^{2}-1}}={\frac {1}{r+1}}.

So every number ${\frac {1}{r+1}}+z$ with a terminating fraction $z\in \mathbb {Z} r^{\mathbb {Z} }$ added has two distinct representations.

For example, in negaternary, i.e. $b=-3$ and $\mathbf {t} =2$ , there is

1.{\overline {02}}_{(-3)}={\frac {5}{4}}=2.{\overline {20}}_{(-3)}

Such non-unique representations can be found by considering the largest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integral-base system.) The rationals thus non-uniquely expressible are those of form

{\frac {z(r+1)+1}{b^{i}(r+1)}}

with $z,i\in \mathbb {Z} .$

Imaginary base

Main article: Complex-base system

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 integers. Donald Knuth proposed the quater-imaginary base (base 2i) in 1955.^[10]

Imaginary-base arithmetic is not much different from negative-base arithmetic, since an imaginary-base number may be considered as the interleave of its real and imaginary parts; using INTERCAL-72 notation,

x_(2i) + (2i)y_(2i) = x_(2i) ¢ y_(2i).

References

↑ Knuth, Donald (1998), The Art of Computer Programming, Volume 2 (3rd ed.), pp. 204–205 . Knuth mentions both negabinary and negadecimal.
↑ The negaternary system is discussed briefly in Petkovšek, Marko (1990), "Ambiguous numbers are dense", The American Mathematical Monthly, 97 (5): 408–411, doi:10.2307/2324393, ISSN 0002-9890, MR 1048915 .
↑ Vittorio Grünwald. Giornale di Matematiche di Battaglini (1885), 203-221, 367
↑ Kempner, A. J. (1936), "Anormal Systems of Numeration", American Mathematical Monthly, 43 (10): 610–617, doi:10.2307/2300532, MR 1523792 .
↑ Pawlak, Z.; Wakulicz, A. (1957), "Use of expansions with a negative basis in the arithmometer of a digital computer", Bulletin de l'Academie Polonaise des Scienses, Classe III, 5: 233–236 .
↑ Marczynski, R. W., "The First Seven Years of Polish Computing", IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980
↑ See the MathWorld Negabinary link
↑ http://math.stackexchange.com/questions/1878151/why-does-the-following-formula-increment-a-negabinary-number-number-in-base-2
↑ Murugesan, San (1977). "Negabinary arithmetic circuits using binary arithmetic". Electronic Circuits and Systems, IEE Journal on. IET. 1 (2): 77–78. |access-date= requires |url= (help)
↑ D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"

External links

Weisstein, Eric W. "Negabinary". MathWorld.

Weisstein, Eric W. "Negadecimal". MathWorld.

This article is issued from Wikipedia - version of the 11/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.