Negative base numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|ALGOL 68}}: Added additional extra credit and fixed bases smaller than -10)
Line 18: Line 18:
=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<lang algol68># Conversion to/from negative base numbers #
<lang algol68># Conversion to/from negative base numbers #
# Note - no checks for valid bases or digits bases -2 .. -64 are handled #
# Note - no checks for valid bases or digits bases -2 .. -63 are handled #
# the digit 63 is represented by a space #
# 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 #
[]CHAR base digits = "01234567890ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz "[ AT 0 ];
# 01234567890123456789012345678901234567890123456789012 #
[]CHAR base digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz "[ AT 0 ];


# returns s decoded to an integer from the negative base b #
# returns s decoded to an integer from the negative base b #
Line 32: Line 35:
FOR d pos FROM UPB s BY -1 TO LWB s DO
FOR d pos FROM UPB s BY -1 TO LWB s DO
INT digit = IF s[ d pos ] = " "
INT digit = IF s[ d pos ] = " "
THEN 63
THEN 62
ELIF s[ d pos ] >= "a"
ELIF s[ d pos ] >= "a"
THEN ( ABS s[ d pos ] + 37 ) - ABS "a"
THEN ( ABS s[ d pos ] + 36 ) - ABS "a"
ELIF s[ d pos ] >= "A"
ELIF s[ d pos ] >= "A"
THEN ( ABS s[ d pos ] + 11 ) - ABS "A"
THEN ( ABS s[ d pos ] + 10 ) - ABS "A"
ELSE ABS s[ d pos ] - ABS "0"
ELSE ABS s[ d pos ] - ABS "0"
FI;
FI;
Line 83: Line 86:
# The defining document for ALGOL 68 spells the name "Algol 68" on the cover, though inside it is "ALGOL 68" #
# 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... #
# at the risk of "judging a language by it's cover", we use "Algol 68" as the name here... #
test n base( - LONG 45125304324472, -64, "Algol 68" )</lang>
test n base( - LONG 36492107981104, -63, "Algol 68" )</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 92: Line 95:
15 encodes to: 195 base -10
15 encodes to: 195 base -10
195 decodes to: 15 base -10
195 decodes to: 15 base -10
-45125304324472 encodes to: Algol 68 base -64
-36492107981104 encodes to: Algol 68 base -63
Algol 68 decodes to: -45125304324472 base -64
Algol 68 decodes to: -36492107981104 base -63
</pre>
</pre>


Revision as of 19:39, 30 January 2017

Negative base numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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.


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

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

<lang algol68># Conversion to/from negative base numbers #

  1. Note - no checks for valid bases or digits bases -2 .. -63 are handled #
  2. A-Z represent the digits 11 .. 35, a-z represent the digits 36 .. 61 #
  3. the digit 62 is represented by a space #
  1. 1 2 3 4 5 6 #
  2. 01234567890123456789012345678901234567890123456789012 #

[]CHAR base digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz "[ AT 0 ];

  1. 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;

  1. 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 # ;
  1. 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" );

  1. The defining document for ALGOL 68 spells the name "Algol 68" on the cover, though inside it is "ALGOL 68" #
  2. 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

Perl 6

Works with: Rakudo version 2016.11

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 }

}

  1. 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 ' 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 -62)

<lang rexx>/*REXX pgm converts & displays a base ten integer to a negative base number (up to -62).*/ @=' converted to base ' 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() exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ nBase: procedure; parse arg x,r; $= /*obtain args; $ is the integer result.*/ 

      @a= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'   /*symbols.*/
      _= 'abcdefghijklmnopqrstuvwxyz';    u=_;    upper u;     @a=0123456789 || u || _
                        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(@a,z+1,1) || $ /*prepend the new numeral to the 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.*/ 

      @a= '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'   /*symbols.*/
      L=length(x);    do j=L  by -1  for L      /*process each of the numerals in  X.  */
                      v=pos(substr(x,j,1),@a)-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

Sidef

Translation of: Perl 6
Translation of: Python

<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

  1. 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

  1. ↑ Negabinary on Wolfram Mathworld
  2. ↑ Negative base on Wikipedia
Retrieved from "https://rosettacode.org/wiki/Negative_base_numbers?oldid=271998"