Negative base numbers: Difference between revisions
(→version 2 (up to base -79): enhanced program to allow for multiple (but equal) results.) |
m (→version 2 (up to base -79): added a comment to the REXX section header, added a comment to the REXX program..) |
||
Line 365: | Line 365: | ||
<br>because the symbols (glyphs or numerals) used herein may not be in the same exact order. The symbols represented |
<br>because the symbols (glyphs or numerals) used herein may not be in the same exact order. The symbols represented |
||
<br>in this REXX program should be able to represent ''any'' programming language used on Rosetta Code. |
<br>in this REXX program should be able to represent ''any'' programming language used on Rosetta Code. |
||
This REXX version also allows for the situation that some negative values can produce the same result, making the |
|||
<br>verification a two-fold process. |
|||
<lang rexx>/*REXX pgm converts & displays a base ten integer to a negative base number (up to -79).*/ |
<lang rexx>/*REXX pgm converts & displays a base ten integer to a negative base number (up to -79).*/ |
||
@=' converted to base '; numeric digits 300 /*be able to handle ginormous numbers. */ |
@=' converted to base '; numeric digits 300 /*be able to handle ginormous numbers. */ |
||
Line 391: | Line 394: | ||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
pBase: procedure; parse arg x,r; $=0; p=0 /*get args; $ will be integer result. */ |
pBase: procedure; parse arg x,r; $=0; p=0 /*get args; $ will be integer result. */ |
||
!='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz /*+-!éáµ' |
!='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz /*+-!éáµ' /*sym*/ |
||
L=length(x); do j=L by -1 for L /*process each of the numerals in X. */ |
L=length(x); do j=L by -1 for L /*process each of the numerals in X. */ |
||
v=pos(substr(x,j,1),!) -1 /*use base R for the numeral's value.*/ |
v=pos(substr(x,j,1),!) -1 /*use base R for the numeral's value.*/ |
Revision as of 08:55, 31 January 2017
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 quaternary (-3).[1][2]
- Task
- Encode the decimal number 10 as negabinary (expect 11110)
- Encode the decimal number 146 as quaternary (expect 21102)
- Encode the decimal number 15 as negadecimal (expect 195)
- In each of the above cases, convert the encoded number back to decimal.
- extra credit
- supply an integer, that when encoded to base -62 (or something "higher"), expresses the
name of the language being used (with correct capitalization). If the computer language has
non-alphanumeric characters, try to encode them into the negatory numerals, or use other
characters instead.
ALGOL 68
<lang algol68># Conversion to/from negative base numbers #
- Note - no checks for valid bases or digits bases -2 .. -63 are handled #
- A-Z represent the digits 11 .. 35, a-z represent the digits 36 .. 61 #
- the digit 62 is represented by a space #
- 1 2 3 4 5 6 #
- 01234567890123456789012345678901234567890123456789012 #
[]CHAR base digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz "[ AT 0 ];
- returns s decoded to an integer from the negative base b #
PRIO FROMNBASE = 9; OP FROMNBASE = ( STRING s, INT b )LONG INT:
BEGIN LONG INT result := 0; LONG INT base multiplier := 1; FOR d pos FROM UPB s BY -1 TO LWB s DO INT digit = IF s[ d pos ] = " " THEN 62 ELIF s[ d pos ] >= "a" THEN ( ABS s[ d pos ] + 36 ) - ABS "a" ELIF 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 )LONG INT: STRING(c) FROMNBASE b;
- returns n encoded as a string in the negative base b #
PRIO TONBASE = 9; OP TONBASE = ( LONG INT n, INT b )STRING:
BEGIN STRING result := ""; LONG INT v := n; WHILE INT d := SHORTEN 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; base digits[ d ] +=: result; v /= 0 DO SKIP OD; result END # TONBASE # ;
- tests the TONBASE and FROMNBASE operators #
PROC test n base = ( LONG INT number, INT base, STRING expected )VOID:
BEGIN PROC expect = ( BOOL result )STRING: IF result THEN "" ELSE " INCORRECT" FI; STRING encoded = number TONBASE base; LONG 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" );
- The defining document for ALGOL 68 spells the name "Algol 68" on the cover, though inside it is "ALGOL 68" #
- at the risk of "judging a language by it's cover", we use "Algol 68" as the name here... #
test n base( - LONG 36492107981104, -63, "Algol 68" )</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 -36492107981104 encodes to: Algol 68 base -63 Algol 68 decodes to: -36492107981104 base -63
Haskell
<lang haskell>import Data.Char (chr, ord) import Numeric (showIntAtBase)
-- The remainder and quotient of n/d, where the remainder is guaranteed to be -- non-negative. The divisor, d, is assumed to be negative. quotRemP :: Integral a => a -> a -> (a, a) quotRemP n d = let (q, r) = quotRem n d
in if r < 0 then (q+1, r-d) else (q, r)
-- Convert the number n to base b, where b is assumed to be less than zero. toNegBase :: Integral a => a -> a -> a toNegBase b n = let (q, r) = quotRemP n b
in if q == 0 then r else negate b * toNegBase b q + r
-- Convert n to a string, where n is assumed to be a base b number, with b less -- than zero. showAtBase :: (Integral a, Show a) => a -> a -> String showAtBase b n = showIntAtBase (abs b) charOf n ""
where charOf m | m < 10 = chr $ m + ord '0' | m < 36 = chr $ m + ord 'a' - 10 | otherwise = '?'
-- Print a number in base b, where b is assumed to be less than zero. printAtBase :: (Integral a, Show a) => a -> a -> IO () printAtBase b = putStrLn . showAtBase b . toNegBase b
main :: IO () main = do
printAtBase (-2) 10 printAtBase (-3) 146 printAtBase (-10) 15 printAtBase (-16) 107 printAtBase (-36) 41371458</lang>
- Output:
$ ./negbase 11110 21102 195 1ab perl6
ooRexx
<lang oorexx>/* REXX ---------------------------------------------------------------
- Adapt for ooRexx (use of now invalid variable names)
- and make it work for base -63 (Algol example)
- --------------------------------------------------------------------*/
Numeric Digits 20 digits='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz ' txt=' converted to base ' n= 10; b= -2; nb=nBase(n,b); Say right(n,20) txt right(b,3) '---->' nb ok() n= 146; b= -3; nb=nBase(n,b); Say right(n,20) txt right(b,3) '---->' nb ok() n= 15; b=-10; nb=nBase(n,b); Say right(n,20) txt right(b,3) '---->' nb ok() n= -15; b=-10; nb=nBase(n,b); Say right(n,20) txt right(b,3) '---->' nb ok() n= 0; b= -5; nb=nBase(n,b); Say right(n,20) txt right(b,3) '---->' nb ok() n=-6284695; b=-62; nb=nBase(n,b); Say right(n,20) txt right(b,3) '---->' nb ok() n=-36492107981104; b=-63;nb=nBase(n,b); Say right(n,20) txt right(b,3) '---->' nb ok() Exit
nBase: Procedure Expose digits /*---------------------------------------------------------------------
- convert x (base 10) to result (base r)
- --------------------------------------------------------------------*/
Parse arg x,r result= Do While x\==0 /*keep Processing while X isn't zero.*/ z=x//r x=x%r /*calculate remainder; calculate int ÷.*/ If z<0 Then Do z=z-r /*subtract a negative R from Z ?--+ */ x=x+1 /*bump X by one. ¦ */ End result=substr(digits,z+1,1)result /*prepend the new digit */ End If result= Then result=0 Return result
pBase: Procedure Expose digits; /*---------------------------------------------------------------------
- convert x (base r) to result (base 10)
- --------------------------------------------------------------------*/
Parse arg x,r; result=0; p=0 len=length(x) Do j=len by -1 For len /*Process each of the X's digits */ v=pos(substr(x,j,1),digits)-1 /*use digit's numeric value. */ result=result+v*r**p; /*add it to result */ p=p+1 /*bump power by 1 */ End Return result
ok: /*---------------------------------------------------------------------
- check back conversion
- --------------------------------------------------------------------*/
back=pBase(nb,b) If back\=n Then r='Error backward conversion results in' back Else r='ok' Return r</lang>
- Output:
10 converted to base -2 ----> 11110 ok 146 converted to base -3 ----> 21102 ok 15 converted to base -10 ----> 195 ok -15 converted to base -10 ----> 25 ok 0 converted to base -5 ----> 0 ok -6284695 converted to base -62 ----> Rexx ok -36492107981104 converted to base -63 ----> Algol 68 ok
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) {
return 0 unless $value; return -((-$value).&base($radix)) if $value < 0; my @result = $value.polymod($radix xx *); for @result.kv -> $k, $v { if $v < 0 { @result[$k ] -= $radix; @result[$k + 1] += 1; } } @result.pop if @result.tail == 0; @result».=base($radix.abs); flip [~] @result;
}
multi sub parse-base (Str $str, Int $radix where -37 < * < -1) {
if $str.substr(0,1) eq '-' { return '-' ~ $str.substr(1).&parse-base($radix) } [+] $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
REXX
Both REXX versions use a type of assert (a function call of OK) that converts the numbers in the
negative base back to the original number in base ten (and issues an error message if not correct).
version 1 (up to base -10)
<lang rexx>/*REXX pgm converts & displays a base ten integer to a negative base number (up to -10).*/ @=' converted to base '; numeric digits 300 /*be able to handle ginormous numbers. */ n= 10; b= -2; nb=nBase(n,b); say right(n, 20) @ right(b, 3) '────►' nb ok() n=146; b= -3; nb=nBase(n,b); say right(n, 20) @ right(b, 3) '────►' nb ok() n= 15; b=-10; nb=nBase(n,b); say right(n, 20) @ right(b, 3) '────►' nb ok() n=-15; b=-10; nb=nBase(n,b); say right(n, 20) @ right(b, 3) '────►' nb ok() n= 0; b= -5; nb=nBase(n,b); say right(n, 20) @ right(b, 3) '────►' nb ok() exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ nBase: procedure; parse arg x,r; $= /*obtain args; $ is the integer result.*/
do while x\==0 /*keep processing while X isn't zero.*/ z=x//r; x=x%r /*calculate remainder; calculate int ÷.*/ if z<0 then do; z=z-r /*subtract a negative R from Z ◄──┐ */ x=x+1 /*bump X by one. │ */ end /* Funny "add" ►───┘ */ $=z || $ /*prepend new digit (numeral) to result*/ end /*while*/ return word($ 0,1) /*when $ is NULL, then return a zero.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ ok: ?=; if pBase(nb,b)\=n then ?= ' ◄──error in negative base calculation'; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ pBase: procedure; parse arg x,r; $=0; p=0 /*obtain args; $ is the integer result.*/
L=length(x); do j=L by -1 for L /*process each of the numerals in X. */ $=$ + substr(x,j,1)*r**p /*add value of a numeral to $ (result).*/ p=p+1 /*bump the power by 1. */ end /*j*/ /* [↓] process the number "bottom-up".*/ return $</lang>
output using the default inputs:
10 converted to base -2 ────► 11110 146 converted to base -3 ────► 21102 15 converted to base -10 ────► 195 -15 converted to base -10 ────► 25 0 converted to base -5 ────► 0
version 2 (up to base -79)
This REXX version supports up to negative base ─79, but it may not be compatible to other programming examples
because the symbols (glyphs or numerals) used herein may not be in the same exact order. The symbols represented
in this REXX program should be able to represent any programming language used on Rosetta Code.
This REXX version also allows for the situation that some negative values can produce the same result, making the
verification a two-fold process.
<lang rexx>/*REXX pgm converts & displays a base ten integer to a negative base number (up to -79).*/
@=' converted to base '; numeric digits 300 /*be able to handle ginormous numbers. */
n= 10; b= -2; nb=nBase(n,b); say right(n,20) @ right(b,3) '────►' nb ok()
n= 146; b= -3; nb=nBase(n,b); say right(n,20) @ right(b,3) '────►' nb ok()
n= 15; b=-10; nb=nBase(n,b); say right(n,20) @ right(b,3) '────►' nb ok()
n= -15; b=-10; nb=nBase(n,b); say right(n,20) @ right(b,3) '────►' nb ok()
n= 0; b= -5; nb=nBase(n,b); say right(n,20) @ right(b,3) '────►' nb ok()
n=-6284695; b=-62; nb=nBase(n,b); say right(n,20) @ right(b,3) '────►' nb ok()
n=-6284695; b=-79; nb=nBase(n,b); say right(n,20) @ right(b,3) '────►' nb ok()
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
nBase: procedure; parse arg x,r,,$ /*get args; $ will be integer result. */
!='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz /*+-!éáµ' /*sym*/ do while x\==0 /*keep processing while X isn't zero.*/ z=x//r; x=x%r /*calculate remainder; calculate int ÷.*/ if z<0 then do; z=z-r /*subtract a negative R from Z ◄──┐ */ x=x+1 /*bump X by one. │ */ end /* Funny "add" ►───┘ */ $=substr(!,z+1,1) || $ /*prepend the new numeral to the result*/ end /*while*/ if $== then $=0 /*when $ is NULL, then return a zero.*/ return $
/*──────────────────────────────────────────────────────────────────────────────────────*/ ok: ?=;if nBase(pBase(nb,b),b)\=nb then ?='◄──error in negative base calculation';return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ pBase: procedure; parse arg x,r; $=0; p=0 /*get args; $ will be integer result. */
!='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz /*+-!éáµ' /*sym*/ L=length(x); do j=L by -1 for L /*process each of the numerals in X. */ v=pos(substr(x,j,1),!) -1 /*use base R for the numeral's value.*/ $=$ + v * r**p; p=p+1 /*add it to $ (result); bump power by 1*/ end /*j*/ /* [↑] process the number "bottom-up".*/ return $</lang>
output using the default inputs:
10 converted to base -2 ────► 11110 146 converted to base -3 ────► 21102 15 converted to base -10 ────► 195 -15 converted to base -10 ────► 25 0 converted to base -5 ────► 0 -6284695 converted to base -62 ────► Rexx -6284695 converted to base -79 ────► DK1
Sidef
<lang ruby>func EncodeNegBase(Num n, Num b { .~~ (-36 .. -2) }) {
var out = [] var r = 0 while (n) { (n, r) = divmod(n, b) if (r < 0) { n += 1 r -= b } out << r.base(-b) } return (out.join.flip || "0")
}
func DecodeNegBase(Str s, Num b { .~~ (-36 .. -2) }) {
var total = 0 for i,c in (s.flip.chars.kv) { total += (Num(c, -b) * b**i) } return total
}
say (" 10 in base -2: ", EncodeNegBase(10, -2)) say ("146 in base -3: ", EncodeNegBase(146, -3)) say (" 15 in base -10: ", EncodeNegBase(15, -10))
say '-'*25
say ("11110 from base -2: ", DecodeNegBase("11110", -2)) say ("21102 from base -3: ", DecodeNegBase("21102", -3)) say (" 195 from base -10: ", DecodeNegBase("195", -10))
say '-'*25
- Extra
say ("25334424 in base -31: ", EncodeNegBase(25334424, -31)) say ("sidef from base -31: ", DecodeNegBase("sidef", -31))</lang>
- Output:
10 in base -2: 11110 146 in base -3: 21102 15 in base -10: 195 ------------------------- 11110 from base -2: 10 21102 from base -3: 146 195 from base -10: 15 ------------------------- 25334424 in base -31: sidef sidef from base -31: 25334424
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