CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

Negative base numbers

From Rosetta Code
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 alternate 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[edit]

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32
# 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" )
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[edit]

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
Output:
$ ./negbase 
11110
21102
195
1ab
perl6

ooRexx[edit]

Translation of: REXX
/* 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
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[edit]

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.

As a stretch goal, rather than implement something that can "Spell the name of the language with correct capitalization" (which is silly, trivial, and has absolutely nothing to do with negative base numbers,) we'll implement routines that correctly work with any Real number, not just integers.

The Real candidate has a 'precision' parameter, default -15, (15 places after the decimal point,) to limit the length of the fractional portion of the converted value. Change it if you need or want different precision. The Integer only routine is kept here as a multi-dispatch candidate since it is potentially much faster than the Real capable routine. The dispatcher will automatically use the most appropriate (fastest) routine.

Note that the parse-base routine will handle 'illegal' negative negative-base values without blowing up.

multi sub base ( Int $value is copy, Int $radix where -37 < * < -1) {
my $result;
while $value {
my $r = $value mod $radix;
$value div= $radix;
if $r < 0 {
$value++;
$r -= $radix
}
$result ~= $r.base(-$radix);
}
flip $result || ~0;
}
 
multi sub base ( Real $num, Int $radix where -37 < * < -1, :$precision = -15 ) {
return '0' unless $num;
my $value = $num;
my $result = '';
my $place = 0;
my $upper-bound = 1 / (-$radix + 1);
my $lower-bound = $radix * $upper-bound;
 
$value = $num / $radix ** ++$place until $lower-bound <= $value < $upper-bound;
 
while ($value or $place > 0) and $place > $precision {
my $digit = ($radix * $value - $lower-bound).Int;
$value = $radix * $value - $digit;
$result ~= '.' unless $place or $result.contains: '.';
$result ~= $digit == -$radix ?? ($digit-1).base(-$radix)~'0' !! $digit.base(-$radix);
$place--
}
$result
}
 
multi sub parse-base (Str $str, Int $radix where -37 < * < -1) {
return -1 * $str.substr(1).&parse-base($radix) if $str.substr(0,1) eq '-';
my ($whole, $frac) = $str.split: '.';
my $fraction = 0;
$fraction = [+] $frac.comb.kv.map: { $^v.parse-base(-$radix) * $radix ** -($^k+1) } if $frac;
$fraction + [+] $whole.flip.comb.kv.map: { $^v.parse-base(-$radix) * $radix ** $^k }
}
 
# TESTING
for <4 -4 0 -7 10 -2 146 -3 15 -10 -19 -10 107 -16
41371458 -36 227.65625 -16 2.375 -4 -1.3e2 -8> -> $v, $r {
my $nbase = $v.&base($r);
printf "%13s.&base\(%3d\) = %-6s : %8s.&parse-base\(%3d\) = %s\n",
$v, $r, $nbase, "'$nbase'", $r, $nbase.&parse-base($r);
}
 
# 'Illegal' negative-base value
say q| '-21'.&parse-base(-10) = |, '-21'.&parse-base(-10);
Output:
            4.&base( -4) = 130    :    '130'.&parse-base( -4) = 4
            0.&base( -7) = 0      :      '0'.&parse-base( -7) = 0
           10.&base( -2) = 11110  :  '11110'.&parse-base( -2) = 10
          146.&base( -3) = 21102  :  '21102'.&parse-base( -3) = 146
           15.&base(-10) = 195    :    '195'.&parse-base(-10) = 15
          -19.&base(-10) = 21     :     '21'.&parse-base(-10) = -19
          107.&base(-16) = 1AB    :    '1AB'.&parse-base(-16) = 107
     41371458.&base(-36) = PERL6  :  'PERL6'.&parse-base(-36) = 41371458
    227.65625.&base(-16) = 124.68 : '124.68'.&parse-base(-16) = 227.65625
        2.375.&base( -4) = 3.32   :   '3.32'.&parse-base( -4) = 2.375
       -1.3e2.&base( -8) = 1616   :   '1616'.&parse-base( -8) = -130
  '-21'.&parse-base(-10) = 19

Python[edit]

#!/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")
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[edit]

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)[edit]

/*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.*/
if r<-10 | r>-2 then do; say 'base' r "must be in range: -2 ───► -10"; exit 13; end
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.*/
if r<-10 | r>-2 then do; say 'base' r "must be in range: -2 ───► -10"; exit 13; end
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 $

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 -71)[edit]

This REXX version supports up to negative base   ─71,   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.

/*REXX pgm converts & displays a base ten integer to a negative base number (up to -71).*/
@=' 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()
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
nBase: procedure; parse arg x,r,,$ /*get args; $ will be integer result. */
 !='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz /*+-!éáµ' /*sym*/
m=length(!)
if r<-m | r>-2 then do; say 'base' r "must be in range: -2 ───► -"m; exit 13; end
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 pBase(nb, b)\=n then ?=' ◄──error in negative base calculation'; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
pBase: procedure; parse arg x,r; $=0; p=0 /*get args; $ will be integer result. */
 !='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz /*+-!éáµ' /*sym*/
m=length(!)
if r<-m | r>-2 then do; say 'base' r "must be in range: -2 ───► -"m; exit 13; end
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 $

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[edit]

Translation of: Perl 6
Translation of: Python
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))
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[edit]

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());
}
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)));
}
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[edit]

  1. Negabinary on Wolfram Mathworld
  2. Negative base on Wikipedia