Negative base
Part ofa serieson |
Numeral systems |
---|
List of numeral systems |
Anegative base(or negativeradix) may be used to construct anon-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 basebis equal to−rfor some natural numberr(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 aminus sign(or, in computer representation, asign 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 byprefixingnega-to the name of the corresponding positive-base system; for example,negadecimal(base −10) corresponds todecimal(base 10),negabinary(base −2) tobinary(base 2),negaternary(base −3) toternary(base 3), andnegaquaternary(base −4) toquaternary(base 4).[1][2]
Example[edit]
Consider what is meant by the representation12243in the negadecimal system, whose basebis −10:
(−10)4= 10,000 | (−10)3= −1,000 | (−10)2= 100 | (−10)1= −10 | (−10)0= 1 |
1 | 2 | 2 | 4 | 3 |
The representation12,243−10(which is intended to be negadecimal notation) is equivalent to8,16310in decimal notation, because 10,000 + (−2,000) + 200 + (−40) + 3 =8,163.
- Remark
On the other hand,−8,16310in decimal would be written9,977−10in negadecimal.
History[edit]
Negative numerical bases were first considered byVittorio Grünwaldin an 1885 monograph published inGiornale di Matematiche di Battaglini.[3]Grünwald gave algorithms for performing addition, subtraction, multiplication, division, root extraction, divisibility tests, and radix conversion. Negative bases were later mentioned in passing byA. J. Kempnerin 1936[4]and studied in more detail byZdzisław Pawlakand A. Wakulicz in 1957.[5]
Negabinary was implemented in the earlyPolishcomputerBINEG(andUMC), built 1957–59, based on ideas by Z. Pawlak and A. Lazarkiewicz from theMathematical InstituteinWarsaw.[6]Implementations since then have been rare.
zfp, a floating-point compression algorithm from theLawrence Livermore National Laboratory,uses negabinary to store numbers. According to zfp's documentation:[7]
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[edit]
Denoting the base as−r,everyintegeracan be written uniquely as
where each digitdkis an integer from 0 tor− 1and the leading digitdn> 0(unlessn= 0). The base−rexpansion ofais then given by the stringdndn−1...d1d0.
Negative-base systems may thus be compared tosigned-digit representations,such asbalanced 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−ras in baser.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−rexpansions of negative integers have aneven numberof digits, while the base−rexpansions of the non-negative integers have anodd numberof digits.
Calculation[edit]
The base−rexpansion of a number can be found by repeated division by−r,recording the non-negative remainders in,and concatenating those remainders, starting with the last. Note that ifa/ biscwith remainderd,thenbc+d=aand therefored=a−bc.To arrive at the correct conversion, the value forcmust be chosen such thatdis non-negative and minimal. For the fourth line of the following example this means that
has to be chosen — and notnor
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 remaindersforwardwe can obtain the negaternary least-significant-digit-first representation.
- Proof:2+ (0+ (1+ (1+ (2) · -3 ) · -3) · -3 ) · -3 = 14610.
Note that in mostprogramming 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 havea= (−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 andrto the quotient and remainder respectively.
Example implementation code[edit]
To negabinary[edit]
C#[edit]
staticstringToNegabinary(intval)
{
stringresult=string.Empty;
while(val!=0)
{
intremainder=val%-2;
val=val/-2;
if(remainder<0)
{
remainder+=2;
val+=1;
}
result=remainder.ToString()+result;
}
returnresult;
}
C++[edit]
autoto_negabinary(intvalue)
{
std::bitset<sizeof(int)*CHAR_BIT>result;
std::size_tbit_position=0;
while(value!=0)
{
constautodiv_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;
}
returnresult;
}
To negaternary[edit]
C#[edit]
staticstringNegaternary(intval)
{
stringresult=string.Empty;
while(val!=0)
{
intremainder=val%-3;
val=val/-3;
if(remainder<0)
{
remainder+=3;
val+=1;
}
result=remainder.ToString()+result;
}
returnresult;
}
Python[edit]
defnegaternary(i:int)->str:
"""Decimal to negaternary." ""
ifi==0:
digits=["0"]
else:
digits=[]
whilei!=0:
i,remainder=divmod(i,-3)
ifremainder<0:
i,remainder=i+1,remainder+3
digits.append(str(remainder))
return"".join(digits[::-1])
>>>negaternary(1000)
'2212001'
Common Lisp[edit]
(defunnegaternary(i)
(if(zeropi)
"0"
(let((digits"")
(rem0))
(loopwhile(not(zeropi))do
(progn
(multiple-value-setq(irem)(truncatei-3))
(when(minusprem)
(incfi)
(incfrem3))
(setfdigits(concatenate'string(write-to-stringrem)digits))))
digits)))
To any negative base[edit]
Java[edit]
importjava.util.ArrayList;
importjava.util.Collections;
publicArrayList<Integer>negativeBase(intinput,intbase){
ArrayList<Integer>result_rev=newArrayList<>();
intnumber=input;
while(number!=0){
inti=number%base;
number/=base;
if(i<0){
i+=Math.abs(base);
number++;
}
result_rev.add(i);
}
returnCollections.reverse(results_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:
importjava.util.stream.Collectors;
finalStringalphabet="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@_";
publicStringtoBaseString(ArrayList<Integer>lst){
// Would throw exception if base is beyond the 64 possible characters
returnlst.stream().map(n->alphabet[n]).collect(Collectors.joining(""));
}
AutoLisp[edit]
(defunnegabase(numbaz/digrst)
;; 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(numberpnum)
(numberpbaz)
(<=(fixbaz)-2)
(>(fixbaz)-11))
(progn
(setqbaz(float(fixbaz))
num(float(fixnum))
dig(if(=num0)"0"""))
(while(/=num0)
(setqrst(-num(*baz(setqnum(fix(/numbaz))))))
(if(minusprst)
(setqnum(1+num)
rst(-rstbaz)))
(setqdig(strcat(itoa(fixrst))dig)))
dig)
(progn
(prompt
(cond
((and(not(numberpnum))
(not(numberpbaz)))
"\nWrong number and negabase.")
((not(numberpnum))
"\nWrong number.")
((not(numberpbaz))
"\nWrong negabase.")
(t
"\nNegabase must be inside [-10 -2] interval.")))
(princ))))
Shortcut calculation[edit]
The following algorithms assume that
- the input is available inbitstringsand 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 setof 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[edit]
The conversion tonegabinary(base −2; digits in) allows a remarkable shortcut (C implementation):
uint32_ttoNegaBinary(uint32_tvalue)// input in standard binary
{
uint32_tSchroeppel2=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:
functiontoNegaBinary(value){
constSchroeppel2=0xAAAAAAAA;
// Convert as in C, then convert to a NegaBinary String
return((value+Schroeppel2)^Schroeppel2).toString(2);
}
The algorithm is first described bySchroeppelin theHAKMEM(1972) as item 128. TheWolfram MathWorlddocuments a version in the Wolfram Language by D. Librik (Szudzik).[8]
To negaquaternary[edit]
The conversion tonegaquaternary(base −4; digits in) allows a similar shortcut (C implementation):
uint32_ttoNegaQuaternary(uint32_tvalue)// input in standard binary
{
uint32_tSchroeppel4=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:
functiontoNegaQuaternary(value){
constSchroeppel4=0xCCCCCCCC;
// Convert as in C, then convert to NegaQuaternary String
return((value+Schroeppel4)^Schroeppel4).toString(4);
}
Arithmetic operations[edit]
The following describes the arithmetic operations for negabinary; calculations in larger bases are similar.
Addition[edit]
Adding negabinary numbers proceeds bitwise, starting from theleast 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 | |||
---|---|---|---|---|---|
Bit | Carry | ||||
−2 | 010−2 | 0 | 1 | 01−2 | −2 occurs only during subtraction. |
−1 | 011−2 | 1 | 1 | 01−2 | |
0 | 000−2 | 0 | 0 | 00−2 | |
1 | 001−2 | 1 | 0 | 00−2 | |
2 | 110−2 | 0 | −1 | 11−2 | |
3 | 111−2 | 1 | −1 | 11−2 | 3 occurs only during addition. |
The second row of this table, for instance, expresses the fact that−1=1+1× −2; the fifth row says2=0+−1× −2; etc.
As an example, to add 1010101−2(1 + 4 + 16 + 64 = 85) and 1110100−2(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−2(1 − 8 + 16 − 128 + 256 = 137).
Another method[edit]
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[edit]
Afull addercircuit can be designed to add numbers in negabinary. The following logic is used to calculate the sum and carries:[9]
Incrementing negabinary numbers[edit]
Incrementing a negabinary number can be done by using the following formula:[10]
(The operations in this formula are to be interpreted as operations on regular binary numbers. For example,is a binary left shift by one bit.)
Subtraction[edit]
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−2(1 − 8 − 32 + 64 = 25) minus 1110100−2(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−2(1 + 4 −32 = −27).
Unary negation,−x,can be computed as binary subtraction from zero,0 −x.
Multiplication and division[edit]
Shifting to the left multiplies by −2, shifting to the right divides by −2.
To multiply, multiply like normaldecimalorbinarynumbers, 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, addcarrytonumber,and divide the sum by −2, to get the newcarry,and the resulting bit as the remainder.
Comparing negabinary numbers[edit]
It is possible to compare negabinary numbers by slightly adjusting a normal unsignedbinary comparator.When comparing the numbersand,invert each odd positioned bit of both numbers. After this, compareandusing a standard unsigned comparator.[11]
Fractional numbers[edit]
Base−rrepresentation may of course be carried beyond theradix point,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[edit]
Unlike positive-base systems, where integers and terminating fractions have non-unique representations (for example, in decimal0.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} withthe biggest digit and
we have
- as well as
So every numberwith aterminating fractionadded 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 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
with
Imaginary base[edit]
Just as using a negative base allows the representation of negative numbers without an explicit negative sign, using animaginarybase allows the representation ofGaussian integers.Donald Knuthproposed thequater-imaginary base(base 2i) in 1955.[12]
See also[edit]
- Quater-imaginary base
- Binary
- Balanced ternary
- Quaternary numeral system
- Numeral systems
- 1 − 2 + 4 − 8 + ⋯(p-adic numbers)
References[edit]
- ^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 inPetkovšek, Marko(1990), "Ambiguous numbers are dense",The American Mathematical Monthly,97(5): 408–411,doi:10.2307/2324393,ISSN0002-9890,JSTOR2324393,MR1048915.
- ^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
- ^Kempner, A. J.(1936), "Anormal Systems of Numeration",American Mathematical Monthly,43(10): 610–617,doi:10.2307/2300532,JSTOR2300532,MR1523792.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."
- ^Pawlak, Z.; Wakulicz, A. (1957), "Use of expansions with a negative basis in the arithmometer of a digital computer",Bulletin de l'Académie Polonaise des Sciences,Classe III,5:233–236.
- ^Marczynski, R. W., "The First Seven Years of Polish Computing"Archived2011-07-19 at theWayback Machine,IEEE Annals of the History of Computing, Vol. 2, No 1, January 1980
- ^"Algorithm — zfp 1.0.1 documentation".zfp.readthedocs.io.
- ^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
- ^Francis, Yu; Suganda, Jutamulia; Shizuhuo, Yin (4 September 2001).Introduction to Information Optics.Academic Press. p. 498.ISBN9780127748115.
- ^"Why does the following formula increment a negabinary number (number in base -2)?".Retrieved2016-08-29.
- ^Murugesan, San (1977). "Negabinary arithmetic circuits using binary arithmetic".IEE Journal on Electronic Circuits and Systems.1(2): 77.doi:10.1049/ij-ecs.1977.0005.
- ^D. Knuth. The Art of Computer Programming. Volume 2, 3rd Edition. Addison-Wesley. pp. 205, "Positional Number Systems"
Further reading[edit]
- Warren Jr., Henry S. (2013) [2002].Hacker's Delight(2nd ed.).Addison Wesley-Pearson Education, Inc.ISBN978-0-321-84268-8.0-321-84268-5.