Negative base


A negative base 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 ; 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 corresponds to decimal, negabinary to binary, negaternary to ternary, and negaquaternary to quaternary.

Example

Consider what is meant by the representation in the negadecimal system, whose base is −10:
12243

Since 10,000 + + 200 + + 3 =, the representation in negadecimal notation is equivalent to in decimal notation, while 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. 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, built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from the Mathematical Institute in Warsaw. Implementations since then have been rare.

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 is . 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.
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:
DecimalNegadecimalBinaryNegabinaryTernaryNegaternaryBalanced TernaryNega Balanced TernaryQuaternaryNegaquaternary
−1525−1111110001−1201220T11011T0−331301
⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮
−515−1011111−1221T11TT1−1123
−416−1001100−1122TT1T−1010
−317−111101−1010T010−311
−218−1010−211T111−212
−119−111−112TT−113
0000000000
1111111111
2210110221TTT22
33111111012010T033
441001001112111T110130
55101101121221TT11T11131
6611011010201101T011012132
7711111011211111T111113133
881000110002211210T10T20120
9910011100110010010010021121
1019010101111010110110110122122
1119110111111110210211T1TT23123
121921100111001102201101T030110
131931101111011112211111T131111
141941110100101122221TTTTT1T32112
151951111100111202101TT0TT1033113
1619610000100001212111TT1TT11100100
1719710001100011222121T0TTT0T101101
1819810010101102002001T10TTT0102102

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, and concatenating those remainders, starting with the last. Note that if, remainder, then and therefore. To arrive at the correct conversion, the value for must be chosen such that is non-negative and minimal. This is exemplified in the fourth line of the following example wherein –5 ÷ –3 must be chosen to equal 2 remainder 1 instead of 1 remainder 2.
For example, to convert 146 in decimal to negaternary:
Reading the remainders backward we obtain the negaternary representation of 14610: 21102–3.
Note that in most programming languages, the result 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
C++

auto to_negabinary

To negaternary

C#

static string negaternary
[Visual Basic .NET]

Private Shared Function ToNegaternary As String
Dim result As String = String.Empty
While value <> 0
Dim remainder As Integer = value Mod -3
value /= -3
If remainder < 0 Then
remainder += 3
value += 1
End If
result = remainder.ToString & result
End While
Return result
End Function
Python">Python (programming language)">Python

def negaternary -> str:
"""Decimal to negaternary."""
if i 0:
digits =
else:
digits =
while i != 0:
i, remainder = divmod
if remainder < 0:
i, remainder = i + 1, remainder + 3
digits.append
return ''.join


>>> negaternary
'2212001'
Common Lisp


"0"

)
)


)
))
digits)))

To any negative base

Java

public String negativeBase
AutoLisp
from interval:

;; NUM is any number. BAZ is any number in the interval .
;;
;; NUM and BAZ will be truncated to an integer if they're floats.



)


)))


rst ))
))
dig)

"\nWrong number and negabase.")


))
)))
PHP
The conversion from integer to some negative base:

function toNegativeBase
Visual Basic .NET

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

Shortcut calculation

The following algorithms assume that
  1. the input is available in bitstrings and coded in ,
  2. there are add and xor operations which operate on such bitstrings,
  3. the set of output digits is standard, i. e. with base,
  4. the output is coded in the same bitstring format, but the meaning of the places is another one.

    To negabinary

The conversion to negabinary allows a remarkable shortcut
:

unsigned int toNegaBinary // input in standard binary

Due to D. Librik. The bitwise XOR portion is originally due to Schroeppel.
JavaScript port for the same shortcut calculation:

function toNegaBinary

To negaquaternary

The conversion to negaquaternary allows a similar shortcut :

unsigned int toNegaQuaternary // input in standard binary

JavaScript port for the same shortcut calculation:

function toNegaQuaternary

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 carry from the previous bit. 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 and 1110100,
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 : 1 1 0 0 1 1 0 0 1
Carry: 0 1 −1 0 −1 1 −1 0 0
so the result is 110011001.

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

Negabinary full adder

A full adder circuit can be designed to add numbers in negabinary. The following logic is used to calculate the sum and carries:

Incrementing negabinary numbers

Incrementing a negabinary number can be done by using the following formula:

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 minus 1110100,
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 : 0 1 0 0 1 0 1
Carry: 0 0 1 −1 1 0 0
so the result is 100101.
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 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 : 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 and, invert each odd positioned bit of both numbers.
After this, compare and using a standard unsigned comparator.

Fractional numbers

Base 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 in negative-base systems the integers have only a single representation. However, there do exist rationals with non-unique representations. For the digits with the biggest digit and
we have
So every number with a terminating fraction added has two distinct representations.
For example, in negaternary, i.e. and, there is
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. The rationals thus non-uniquely expressible are those of form
with

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 integers. Donald Knuth proposed the quater-imaginary base in 1955.