Negative base numbers
Negative base numbers are an alternatively way to encode numbers without the need for a minus sign. Various negative bases may be used including negadecimal (base -10), negabinary (-2) and negaternary (-3).[1][2]
- Task
- Encode the decimal number 10 as negabinary (expect 11110)
- Encode the decimal number 146 as negaternary (expect 21102)
- Encode the decimal number 15 as negadecimal (expect 195)
- In each of the above cases, convert the encoded number back to decimal.
ALGOL 68
<lang algol68># Conversion to/from negative base numbers #
- Note - no checks for valid bases or digits (bases -2 .. -36 are handled) #
- returns s decoded to an integer from the negative base b #
PRIO FROMNBASE = 9; OP FROMNBASE = ( STRING s, INT b )INT:
BEGIN
INT result := 0;
INT base multiplier := 1;
FOR d pos FROM UPB s BY -1 TO LWB s DO
INT digit = IF s[ d pos ] >= "A"
THEN ( ABS s[ d pos ] + 10 ) - ABS "A"
ELSE ABS s[ d pos ] - ABS "0"
FI;
result +:= base multiplier * digit;
base multiplier *:= b
OD;
result
END # FROMNBASE # ;
OP FROMNBASE = ( CHAR c, INT b )INT: STRING(c) FROMNBASE b;
- returns n encoded as a string in the negative base b #
PRIO TONBASE = 9; OP TONBASE = ( INT n, b )STRING:
BEGIN
STRING result := "";
INT v := n;
WHILE
INT d := IF v < 0 THEN - ( ABS v MOD b ) ELSE v MOD b FI;
v OVERAB b;
IF d < 0
THEN
d -:= b;
v +:= 1
FI;
IF d < 10 THEN REPR ( d + ABS "0" ) ELSE REPR ( ( d - 10 ) + ABS "A" ) FI +=: result;
v /= 0
DO SKIP OD;
result
END # TONBASE # ;
- tests the TONBASE and FROMNBASE operators #
PROC test n base = ( INT number, base, STRING expected )VOID:
BEGIN
PROC expect = ( BOOL result )STRING: IF result THEN "" ELSE " INCORRECT" FI;
STRING encoded = number TONBASE base;
INT decoded = encoded FROMNBASE base;
print( ( whole( number, 0 ), " encodes to: ", encoded ) );
print( ( " base ", whole( base, 0 ), expect( encoded = expected ), newline ) );
print( ( encoded, " decodes to: ", whole( decoded, 0 ) ) );
print( ( " base ", whole( base, 0 ), expect( decoded = number ), newline ) )
END # test n base # ;
test n base( 10, -2, "11110" ); test n base( 146, -3, "21102" ); test n base( 15, -10, "195" )</lang>
- Output:
10 encodes to: 11110 base -2 11110 decodes to: 10 base -2 146 encodes to: 21102 base -3 21102 decodes to: 146 base -3 15 encodes to: 195 base -10 195 decodes to: 15 base -10
Perl 6
Perl 6 provides built-in methods / routines base and parse-base to convert to and from bases 2 through 36. We'll just shadow the core routines with versions that accept negative bases. We'll simplify things by only accepting integer values to convert.
<lang perl6>multi sub base (Int $value, Int $radix where -37 < * < -1) {
my @result = $value.polymod($radix xx *);
for @result.kv -> $k, $v {
if $v < 0 {
@result[$k ] -= $radix;
@result[$k + 1] += 1;
}
}
@result.pop while @result.tail == 0;
@result».=base($radix.abs);
flip [~] @result;
}
multi sub parse-base (Str $str, Int $radix where -37 < * < -1) {
[+] $str.flip.comb.kv.map: { $^v.parse-base($radix.abs) * $radix ** $^k }
}
- TESTING
say ' 10.&base( -2) = ', 10.&base(-2); say ' 146.&base( -3) = ', 146.&base(-3); say ' 15.&base(-10) = ', 15.&base(-10); say ' 107.&base(-16) = ', 107.&base(-16); say ' 41371458.&base(-36) = ', 41371458.&base(-36);
say '"11110".&parse-base( -2) = ', "11110".&parse-base(-2); say '"21102".&parse-base( -3) = ', "21102".&parse-base(-3); say ' "195".&parse-base(-10) = ', "195".&parse-base(-10); say ' "1AB".&parse-base(-16) = ', "1AB".&parse-base(-16); say '"Perl6".&parse-base(-36) = ', "Perl6".&parse-base(-36);</lang>
- Output:
10.&base( -2) = 11110
146.&base( -3) = 21102
15.&base(-10) = 195
107.&base(-16) = 1AB
41371458.&base(-36) = PERL6
"11110".&parse-base( -2) = 10
"21102".&parse-base( -3) = 146
"195".&parse-base(-10) = 15
"1AB".&parse-base(-16) = 107
"Perl6".&parse-base(-36) = 41371458
Python
<lang python>#!/bin/python from __future__ import print_function
def EncodeNegBase(n, b): #Converts from decimal if n == 0: return "0" out = [] while n != 0: n, rem = divmod(n, b) if rem < 0: n += 1 rem -= b out.append(rem) return "".join(map(str, out[::-1]))
def DecodeNegBase(nstr, b): #Converts to decimal if nstr == "0": return 0
total = 0 for i, ch in enumerate(nstr[::-1]): total += int(ch) * b**i return total
if __name__=="__main__":
print ("Encode 10 as negabinary (expect 11110)") result = EncodeNegBase(10, -2) print (result) if DecodeNegBase(result, -2) == 10: print ("Converted back to decimal") else: print ("Error converting back to decimal")
print ("Encode 146 as negaternary (expect 21102)") result = EncodeNegBase(146, -3) print (result) if DecodeNegBase(result, -3) == 146: print ("Converted back to decimal") else: print ("Error converting back to decimal")
print ("Encode 15 as negadecimal (expect 195)") result = EncodeNegBase(15, -10) print (result) if DecodeNegBase(result, -10) == 15: print ("Converted back to decimal") else: print ("Error converting back to decimal")</lang>
- Output:
Encode 10 as negabinary (expect 11110) 11110 Converted back to decimal Encode 146 as negaternary (expect 21102) 21102 Converted back to decimal Encode 15 as negadecimal (expect 195) 195 Converted back to decimal
zkl
<lang zkl>fcn toNBase(n,radix){
var [const] cs=[0..9].chain(["a".."z"]).pump(String); //"0123456789abcd..z"
_assert_(-37 < radix < -1,"invalid radix");
digits:=List();
while(n){ reg r;
n,r=n.divr(radix); // C compiler semantics
if(r<0){ n+=1; r-=radix; }
digits.append(r);
}
digits.reverse().pump(String,cs.get);
}
fcn toInt(str,radix){ // the toInt(radix) method radix is 2..36
str.reduce('wrap(s,d,rdx){ s*radix + d.toInt(rdx); },0,radix.abs());
}</lang> <lang zkl>ns:=T( T(10,-2), T(146,-3), T(15,-10), T(107,-16), T(41371458,-36), T(44661,-36) ); results:=ns.pump(List,Void.Xplode,toNBase); foreach nb,r in (ns.zip(results)){
_,b:=nb;
println("%10d.base(%3d) = \"%s\" --> %d".fmt(nb.xplode(),r,toInt(r,b)));
}</lang>
- Output:
10.base( -2) = "11110" --> 10
146.base( -3) = "21102" --> 146
15.base(-10) = "195" --> 15
107.base(-16) = "1ab" --> 107
41371458.base(-36) = "perl6" --> 41371458
44661.base(-36) = "zkl" --> 44661
References
- ↑ Negabinary on Wolfram Mathworld
- ↑ Negative base on Wikipedia