Rice coding

From Rosetta Code
Rice coding 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.

Rice coding is a variant of Golomb coding where the parameter is a power of two. This makes it easier to encode the remainder of the euclidean division.

Implement Rice coding in your programming language and verify that you can consistently encode and decode a list of examples (for instance numbers from 0 to 10 or something).

Rice coding is initially meant to encode natural numbers, but since relative numbers are countable, it is fairly easy to modify Rice coding to encode them too. You can do that for extra credit.

ALGOL 68

Translation of: Julia – with output formatting similar to the Wren sample and using STRINGs to represent the bit vector
BEGIN # Rice encoding - translation of the Julia sample                       #

    # Golomb-Rice encoding of a positive number to a bit vector               #
    #                                    (string of 0s and 1s) using M of 2^k #
    # dyadic RICEENCODE, allows k to be specified                             #
    PRIO RICEENCODE = 8;
    OP   RICEENCODE = ( INT n, INT k )STRING:
         BEGIN
            IF n < 0 THEN print( ( "cannot encode negative numbers", newline ) ); stop FI;
            INT m = 2 ^ k;
            INT q = n OVER m, r = n MOD m;
            STRING result := "";
            INT v := r;
            WHILE v > 0 DO                 # set result to binary digits of n #
                IF v MOD 2 = 0 THEN "0" ELSE "1" FI +=: result;
                v OVERAB 2
            OD;
            # pad result to k digits                                          #
            FOR pad FROM ( UPB result - LWB result ) + 2 TO k DO
                "0" +=: result
            OD;
            "0" +=: result;                                 # add a leading 0 #
            FOR leading TO q DO                            # and q leading 1s #
                "1" +=: result
            OD;
            result
         END # RICEENCODE # ;
    # monadic RICEENCODE, encodes with k = 2                                  #
    OP   RICEENCODE = ( INT n )STRING: n RICEENCODE 2;

    CO extended encoding of negative numbers
       see wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers
    CO
    PRIO RICEENCODEX = 8;
    OP   RICEENCODEX = ( INT n, INT k )STRING:
         IF INT n2 = 2 * n; n < 0 THEN -n2 - 1 ELSE n2 FI RICEENCODE k;
    OP   RICEENCODEX = ( INT n )STRING: n RICEENCODEX 2;

    # Golomb-Rice decoding of a bit vector (string of 0s and 1s)              #
    #                                                           with M of 2^k #
    PRIO RICEDECODE = 8;
    OP   RICEDECODE = ( STRING a, INT k )INT:
         BEGIN
            INT m = 2 ^ k;
            INT zpos := 0;
            IF NOT char in string( "0", zpos, a ) THEN zpos := LWB a FI;
            INT r := 0;
            FOR z FROM zpos TO UPB a DO
                r *:= 2;
                IF a[ z ] = "1" THEN r +:= 1 FI
            OD;
            INT q = zpos - LWB a;
            q * m + r
         END # RICEDECODE # ;
    OP   RICEDECODE = ( STRING a )INT: a RICEDECODE 2;
    # extended to handle negative numbers                                     #
    PRIO RICEDECODEX = 8;
    OP   RICEDECODEX = ( STRING a, INT k )INT:
             IF   INT i = a RICEDECODE k;
                  ODD i
             THEN - ( ( i + 1 ) OVER 2 )
             ELSE i OVER 2
             FI # RICEDECODEX # ;
    OP   RICEDECODEX = ( STRING a )INT: a RICEDECODEX 2;

    # right pads s with blanks to w characters                                #
    PRIO PAD = 8;
    OP   PAD = ( STRING s, INT w )STRING:
         IF   INT len = ( UPB s - LWB s ) + 1;
              len >= w
         THEN s
         ELSE s + ( ( w - len ) * " " )
         FI # PAD # ;

    print( ( "Base Rice Coding:", newline ) );
    FOR n FROM 0 TO 10 DO
        STRING e = RICEENCODE n;
        print( ( whole( n, -3 ), " -> ", e PAD 10, " -> ", whole( RICEDECODE e, -3 ), newline ) )
    OD;
    print( ( "Extended Rice Coding:", newline ) );
    FOR n FROM -10 TO 10 DO
        STRING e = RICEENCODEX n;
        print( ( whole( n, -3 ), " -> ", e PAD 10, " -> ", whole( RICEDECODEX e, -3 ),  newline ) )
    OD

END
Output:
Base Rice Coding:
  0 -> 000        ->   0
  1 -> 001        ->   1
  2 -> 010        ->   2
  3 -> 011        ->   3
  4 -> 1000       ->   4
  5 -> 1001       ->   5
  6 -> 1010       ->   6
  7 -> 1011       ->   7
  8 -> 11000      ->   8
  9 -> 11001      ->   9
 10 -> 11010      ->  10
Extended Rice Coding:
-10 -> 1111011    -> -10
 -9 -> 1111001    ->  -9
 -8 -> 111011     ->  -8
 -7 -> 111001     ->  -7
 -6 -> 11011      ->  -6
 -5 -> 11001      ->  -5
 -4 -> 1011       ->  -4
 -3 -> 1001       ->  -3
 -2 -> 011        ->  -2
 -1 -> 001        ->  -1
  0 -> 000        ->   0
  1 -> 010        ->   1
  2 -> 1000       ->   2
  3 -> 1010       ->   3
  4 -> 11000      ->   4
  5 -> 11010      ->   5
  6 -> 111000     ->   6
  7 -> 111010     ->   7
  8 -> 1111000    ->   8
  9 -> 1111010    ->   9
 10 -> 11111000   ->  10

F#

// Rice coding. Nigel Galloway: September 21st., 2023
let rec fN g=[match g with 0->() |_->yield 1; yield! fN(g-1)]
let fI n=let rec fI n g=match List.head g with 1->fI (n+1) (List.tail g) |_->(n,List.foldBack(fun i (n,g)->(n*2,g+n*i)) (List.tail g) (1,0)|>snd) in fI 0 n
let rec fG n g=[match n with 1->yield g%2 |_->yield g%2; yield! fG (n-1) (g/2)]
let encode n g=let q=g/pown 2 n in [yield! fN q; yield 0; yield! fG n g|>List.rev]
let decode n g=let a,b=fI g in a*pown 2 n+b
let test=let test=encode 4 in [for n in 0..17 do yield test n] //encode 0 to 17
test|>List.iter(fun n->n|>List.iter(printf "%d"); printf " -> "; printfn "%d" (decode 4 n)) //print the encoded values and the decoded values
Output:
00000 -> 0
00001 -> 1
00010 -> 2
00011 -> 3
00100 -> 4
00101 -> 5
00110 -> 6
00111 -> 7
01000 -> 8
01001 -> 9
01010 -> 10
01011 -> 11
01100 -> 12
01101 -> 13
01110 -> 14
01111 -> 15
100000 -> 16
100001 -> 17

FreeBASIC

Translation of: Phix
Function RiceEncode(n As Integer, k As Integer = 2, extended As Boolean = False) As String
    If extended Then n = Iif(n < 0, -2*n-1, 2*n)
    Dim As Integer m = 2 ^ k
    Dim As Integer q = n \ m
    Dim As Integer r = n Mod m
    Return String(q, "1") & Right("00000000" & Bin(r), k + 1)
End Function

Function RiceDecode(a As String, k As Integer = 2, extended As Boolean = False) As Integer
    Dim As Integer m = 2 ^ k
    Dim As Integer q = Instr(a, "0") - 1
    Dim As Integer r = Val("&B" & Mid(a, q + 2))
    Dim As Integer i = q * m + r
    If extended Then i = Iif(i Mod 2, -(i +1) \ 2, i \ 2)
    Return i
End Function

Dim As Integer n
Dim As String s
Print "Base Rice Coding:"
For n = 0 To 10
    s = RiceEncode(n)
    Print Using "& -> & -> &"; n; s; RiceDecode(s)
Next n
Print "Extended Rice Coding:"
For n = -10 To 10
    s = RiceEncode(n, 2, True)
    Print Using "& -> & -> &"; n; s; RiceDecode(s, 2, True)
Next n

Sleep
Output:
Same as Phix entry.

jq

Adapted from Wren

Works with jq, the C implementation of jq

Works with gojq, the Go implementation of jq

The program presented here is written to advantage of of gojq's support for unbounded-precision integer arithmetic. With small modifications, it will also work with jaq, the Rust implementation of jq.

Note that in this entry, the polynomial SIGMA( c[$i] * x*$i ) is represented by the JSON array [c0, c1, c2, ...].

# idivide/1 is written to take advantage of gojq's support for
# unbounded-precision integer arithmetic;
# the last last line (invoking `round`) is for the sake of jaq.
def idivide($j):
  (. % $j) as $mod
  | (. - $mod) / $j
  | round  # solely for jaq
  ;

def leftshift($n):
  reduce range(0;$n) as $i (.; . * 2);

def divmod($j):
  (. % $j) as $mod
  | [((. - $mod) | idivide($j)), $mod] ;

# Emit a stream of the digits in the given non-negative integer
def digits: explode[] | . - 48;

# Bit arrays and polynomials

# Convert the input integer to a stream of 0s and 1s, least significant bit first
def bitwise:
  recurse( if . >= 2 then idivide(2) else empty end) | . % 2;

# Evaluate the input polynomial at $x
def eval($x):
  . as $p
  | reduce range(0; length) as $i ({power: 1, ans: 0};
      .ans += $p[$i] * .power
      | .power *= $x )
  | .ans;


### Rice Encoding

#  Input should be a non-negative integer
def encode($k):
  (1 | leftshift($k)) as $m
  | divmod($m) as [$q, $r]
  | ([range(0;$q) | 1] + [0])
  | ([ $r | bitwise ] | reverse) as $digits
  | ($digits|length) as $dc
  | if $dc < $k then . +  [range(0; $k - $dc) | 0] end
  | . + $digits ;

def encodeEx($k):
  if . < 0 then -2 * . - 1 else  2 * . end
  | encode($k);

def decode($k):
  (1 | leftshift($k)) as $m
  | (index(0) | if . == -1 then 0 else . end) as $q
  | ( .[$q:] | reverse| eval(2)) as $r
  | $q * $m + $r;

def decodeEx($k):
  decode($k) as $i
  | if $i % 2 == 1 then - ($i+1 | idivide(2)) else ($i | idivide(2)) end;

"Basic Rice coding (k = 2):",
(range(0;11)
 | encode(2) as $res
 | "\(.) -> \($res|join("")) => \($res|decode(2))" ),

"\nExtended Rice coding (k == 2):",
(range (-10; 11)
 | encodeEx(2) as $res
 | "\(.) -> \($res|join("")) => \($res|decodeEx(2))" ),

"\nBasic Rice coding (k == 4):",
( range (0; 18) 
  | encode(4) as $res
  | "\(.) -> \($res|join("")) => \($res|decode(4))" )
Output:
Basic Rice coding (k = 2):
0 -> 000 => 0
1 -> 001 => 1
2 -> 010 => 2
3 -> 011 => 3
4 -> 1000 => 4
5 -> 1001 => 5
6 -> 1010 => 6
7 -> 1011 => 7
8 -> 11000 => 8
9 -> 11001 => 9
10 -> 11010 => 10

Extended Rice coding (k == 2):
-10 -> 1111011 => -10
-9 -> 1111001 => -9
-8 -> 111011 => -8
-7 -> 111001 => -7
-6 -> 11011 => -6
-5 -> 11001 => -5
-4 -> 1011 => -4
-3 -> 1001 => -3
-2 -> 011 => -2
-1 -> 001 => -1
0 -> 000 => 0
1 -> 010 => 1
2 -> 1000 => 2
3 -> 1010 => 3
4 -> 11000 => 4
5 -> 11010 => 5
6 -> 111000 => 6
7 -> 111010 => 7
8 -> 1111000 => 8
9 -> 1111010 => 9
10 -> 11111000 => 10

Basic Rice coding (k == 4):
0 -> 00000 => 0
1 -> 00001 => 1
2 -> 00010 => 2
3 -> 00011 => 3
4 -> 00100 => 4
5 -> 00101 => 5
6 -> 00110 => 6
7 -> 00111 => 7
8 -> 01000 => 8
9 -> 01001 => 9
10 -> 01010 => 10
11 -> 01011 => 11
12 -> 01100 => 12
13 -> 01101 => 13
14 -> 01110 => 14
15 -> 01111 => 15
16 -> 100000 => 16
17 -> 100001 => 17

Julia

""" Golomb-Rice encoding of a positive number to bit vector using M of 2^k"""
function rice_encode(n::Integer, k = 2)
    @assert n >= 0
    m = 2^k
    q, r = divrem(n, m)
    return [fill(true, q); false; Bool.(reverse(digits(r, base=2, pad=k)))]
end
""" see wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers """
extended_rice_encode(n, k = 2) = rice_encode(n < 0 ? -2n - 1 : 2n, k)

""" Golomb-Rice decoding of a vector of bits with M of 2^k """
function rice_decode(a::Vector{Bool}, k = 2)
    m = 2^k
    zpos = something(findfirst(==(0), a), 1)
    r = evalpoly(2, reverse(a[zpos:end]))
    q = zpos - 1
    return q * m + r
end
extended_rice_decode(a, k = 2) = (i = rice_decode(a, k); isodd(i) ? -((i + 1) ÷ 2) : i ÷ 2)

println("Base Rice Coding:")
for n in 0:10
    println(n, " -> ", join(map(d -> d ? "1" : "0", rice_encode(n))), 
       " -> ", rice_decode(rice_encode(n)))
end
println("Extended Rice Coding:")
for n in -10:10
    println(n, " -> ", join(map(d -> d ? "1" : "0", extended_rice_encode(n))), 
       " -> ", extended_rice_decode(extended_rice_encode(n)))
end
Output:
Base Rice Coding:
0 -> 000 -> 0
1 -> 001 -> 1
2 -> 010 -> 2
3 -> 011 -> 3
4 -> 1000 -> 4
5 -> 1001 -> 5
6 -> 1010 -> 6
7 -> 1011 -> 7
8 -> 11000 -> 8
9 -> 11001 -> 9
10 -> 11010 -> 10
Extended Rice Coding:
-10 -> 1111011 -> -10
-9 -> 1111001 -> -9
-8 -> 111011 -> -8
-7 -> 111001 -> -7
-6 -> 11011 -> -6
-5 -> 11001 -> -5
-4 -> 1011 -> -4
-3 -> 1001 -> -3
-2 -> 011 -> -2
-1 -> 001 -> -1
0 -> 000 -> 0
1 -> 010 -> 1
2 -> 1000 -> 2
3 -> 1010 -> 3
4 -> 11000 -> 4
5 -> 11010 -> 5
6 -> 111000 -> 6
7 -> 111010 -> 7
8 -> 1111000 -> 8
9 -> 1111010 -> 9
10 -> 11111000 -> 10

Lua

Translation of: Julia – Using strings to represent the bit vector
do -- Rice encoding  - translation of the Julia sample

    -- Golomb-Rice encoding of a positive number to a bit vector (string of 0s and 1s) using M of 2^k
    local function rice_encode( n, k )
        assert( n >= 0 )
        k = k or 2
        local m = math.floor( 2^k )
        local result, q, r = {}, math.floor( n / m ), n % m
        while r > 0 do
            result[ #result + 1 ] = r % 2 == 0 and "0" or "1"
            r = math.floor( r / 2 )
        end
        while #result < k do result[ #result + 1 ] = "0" end
        result[ #result + 1 ] = "0"
        for i = 1, q do result[ #result + 1 ] = "1" end
        return string.reverse( table.concat( result, "" ) )
    end
    -- see wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers
    local function extended_rice_encode( n, k )
        k = k or 2
        local n2 = 2 * n
        return rice_encode( n < 0 and -n2 - 1 or n2, k )
    end

    -- Golomb-Rice decoding of a bit vector (string of 0s and 1s) with M of 2^k
    local function rice_decode( a, k )
        k = k or 2
        local m = math.floor( 2^k )
        local zpos, _ = a:find( "0" )
        local r = 0
        for z = zpos, #a do
            r = r * 2
            if a:sub( z, z ) == "1" then r = r + 1 end
        end
        local q = zpos - 1
        return q * m + r
    end

    local function extended_rice_decode( a, k )
        k = k or 2
        local i = rice_decode( a, k )
        return math.floor( i % 2 == 1 and - ( ( i + 1 ) / 2 ) or i / 2 )
    end

    print( "Base Rice Coding:" )
    for n = 0, 10 do
        local e = rice_encode( n )
        print( n.." -> "..e.." -> "..rice_decode( e ) )
    end
    print( "Extended Rice Coding:" )
    for n = -10, 10 do
        local e = extended_rice_encode( n )
        print( n.." -> "..e.." -> "..extended_rice_decode( e ) )
    end

end
Output:

Same as the Julia sample,

Perl

#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Rice_coding
use warnings;

sub rice # args k arrayofnumbers
  {
  my $k = shift;
  join '', map { 1 x ($_ >> $k) . 0 . sprintf "%0*b", $k, $_ % 2**$k } @_;
  }

sub derice # args k stringof0and1representingbinarydata
  {
  (my $k, local $_) = @_;
  my @answers;
  push @answers, (length($1) << $k) + oct "0b$2" while /\G(1*)0(.{$k})/g;
  return @answers;
  }

for my $k ( 2 .. 6)
  {
  print "\nk = $k\n\n";
  my $rice = rice( $k, my @input = 0 .. 17 );
  my @decoded = derice $k, $rice;
  print "  input: @input\n   rice: $rice\ndecoded: @decoded\n";
  "@input" eq "@decoded" or die "MISMATCH";
  }
Output:

k = 2

  input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
   rice: 00000101001110001001101010111100011001110101101111100011100111101011101111110001111001
decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

k = 3

  input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
   rice: 000000010010001101000101011001111000010001100101001110100101011011010111110000110001
decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

k = 4

  input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
   rice: 00000000010001000011001000010100110001110100001001010100101101100011010111001111100000100001
decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

k = 5

  input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
   rice: 000000000001000010000011000100000101000110000111001000001001001010001011001100001101001110001111010000010001
decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

k = 6

  input: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
   rice: 000000000000010000010000001100001000000101000011000001110001000000100100010100001011000110000011010001110000111100100000010001
decoded: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Phix

Translation of: Julia
with javascript_semantics
-- Golomb-Rice encoding of a positive number to bit vector using M of 2^k, with 
-- optional -ve as per wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers
function rice_encode(integer n, k=2, bool extended=false)
    if extended then n = iff(n<0 ? -2*n-1 : 2*n) end if
    assert(n>=0)
    integer m = power(2,k), q = floor(n/m), r = rmdr(n,m)
    return repeat('1',q)&sprintf(sprintf("%%0%db",k+1),r)
end function

-- Golomb-Rice decoding of a vector of bits with M of 2^k, with optional -ves
function rice_decode(string a, integer k=2, bool extended=false)
    integer m = power(2,k),
            q = find('0',a),
            r = to_integer(a[q+1..$],0,2),
            i = (q-1) * m + r
    if extended then i := iff(odd(i) ? -(i+1)/2 : i/2) end if
    return i
end function

printf(1,"Base Rice Coding:\n")
for n=0 to 10 do
    string s = rice_encode(n)
    printf(1,"%d -> %s -> %d\n",{n,s,rice_decode(s)})
end for
printf(1,"Extended Rice Coding:\n")
for n=-10 to 10 do
    string s = rice_encode(n,2,true)
    printf(1,"%d -> %s -> %d\n",{n,s,rice_decode(s,2,true)})
end for
Output:

Same as Julia. Note that rice_decode on an input stream should probably get r from a[q+1..q+k] and strip q+k bits off the head of the stream.
Then again the above is using strings for demonstration purposes, so that code is hardly production-ready.

Python

Works with: Python version 3.x
Translation of: Phix
#!/usr/bin/python

import math

def rice_encode(n, k = 2, extended = False):
    if extended:
        n = -2 * n -1 if n < 0 else 2*n
    assert n >= 0
    m = 2**k
    q = n//m
    r = n % m
    return '1' * q + format(r, '0{}b'.format(k + 1))

def rice_decode(a, k = 2, extended = False):
    m = 2**k
    q = a.find('0')
    r = int(a[q:], 2)
    i = (q) * m + r
    if extended:
        i = -(i+1)//2 if i%2 else i//2
    return i

print("Base Rice Coding:")
for n in range(11):
    s = rice_encode(n)
    print(f"{n} -> {s} -> {rice_decode(s)}")

print("Extended Rice Coding:")
for n in range(-10, 11):
    s = rice_encode(n, 2, True)
    print(f"{n} -> {s} -> {rice_decode(s, 2, True)}")
Output:
Same as Phix entry.

Raku

package Rice {

  our sub encode(Int $n, UInt :$k = 2) {
    my $d = 2**$k;
    my $q = $n div $d;
    my $b = sign(1 + sign($q));
    my $m = abs($q) + $b;
    flat
      $b xx $m, 1 - $b,
      ($n mod $d).polymod(2 xx $k - 1).reverse
  }

  our sub decode(@bits is copy, UInt :$k = 2) {
    my $d = 2**$k;
    my $b = @bits.shift;
    my $m = 1;
    $m++ while @bits and @bits.shift == $b;
    my $q = $b ?? $m - 1 !! -$m;
    $q*$d + @bits.reduce(2 * * + *);
  }

}

CHECK {
  use Test;
  constant N = 100;
  plan 2*N + 1;
  is $_, Rice::decode Rice::encode $_ for -N..N;
}

RPL

« BIN → k
  « 2 k ^ MOD "0" LASTARG / IP
    WHILE DUP REPEAT
       1 - 
       "1" ROT + SWAP
    END
    DROP 
    R→B →STR 3 OVER SIZE 1 - SUB 
    WHILE DUP SIZE k < REPEAT "0" SWAP + END
    +
» » '→RICE' STO

« BIN → n k
  « "#" n DUP SIZE DUP k - 1 + SWAP SUB "b" + + STR→ B→R
    0
    1 k FOR j
       n j DUP SUB "1" == +
    NEXT
    2 k ^ * +
» » 'RICE→' STO

« { }
  0 10 FOR j j 2 →RICE + NEXT
  DUP { }
  0 3 PICK SIZE FOR j OVER j GET 2 RICE→ + NEXT
» 'TASK' STO
Output:
2: { "000" "001" "010" "011" "1000" "1001" "1010" "1011" "11000" "11001" "11010" }
1: { 0 1 2 3 4 5 6 7 8 9 10 }

Sidef

Translation of: Perl
func rice(k, arr) {
    var t = 2**k
    arr.map {|v|
        ['1' * (v >> k), '0', '%0*s' % (k, as_bin(v % t))].join
    }.join
}

func derice(k, str) {
    gather {
        var re = Regex('\G(1*)0(.{' + Str(k) + '})', 'g')
        while (str =~ re) {|m|
            take((m[0].len << k) + Num(m[1], 2))
        }
    }
}

for k in (2 .. 6) {
    say "\nk = #{k}\n"
    var input = @(0..17).shuffle
    var enc = rice(k, input)
    var dec = derice(k, enc)
    say "  input: #{input}"
    say "   rice: #{enc}"
    say "decoded: #{dec}"
    assert_eq(dec, input)
}
Output:
k = 2

  input: [5, 6, 15, 17, 3, 9, 4, 10, 12, 2, 11, 0, 1, 13, 7, 16, 8, 14]
   rice: 10011010111011111100101111001100011010111000010110110000011110011011111100011000111010
decoded: [5, 6, 15, 17, 3, 9, 4, 10, 12, 2, 11, 0, 1, 13, 7, 16, 8, 14]

k = 3

  input: [11, 14, 16, 4, 0, 5, 12, 13, 17, 3, 6, 10, 15, 2, 9, 7, 8, 1]
   rice: 100111011011000001000000010110100101011100010011011010010101110010100010111100000001
decoded: [11, 14, 16, 4, 0, 5, 12, 13, 17, 3, 6, 10, 15, 2, 9, 7, 8, 1]

k = 4

  input: [6, 4, 2, 9, 0, 5, 1, 3, 17, 15, 10, 11, 16, 13, 8, 14, 7, 12]
   rice: 00110001000001001001000000010100001000111000010111101010010111000000110101000011100011101100
decoded: [6, 4, 2, 9, 0, 5, 1, 3, 17, 15, 10, 11, 16, 13, 8, 14, 7, 12]

k = 5

  input: [17, 11, 14, 15, 4, 10, 12, 8, 16, 5, 6, 13, 3, 7, 1, 9, 2, 0]
   rice: 010001001011001110001111000100001010001100001000010000000101000110001101000011000111000001001001000010000000
decoded: [17, 11, 14, 15, 4, 10, 12, 8, 16, 5, 6, 13, 3, 7, 1, 9, 2, 0]

k = 6

  input: [2, 3, 14, 1, 7, 11, 17, 9, 16, 8, 13, 15, 6, 10, 12, 5, 4, 0]
   rice: 000001000000110001110000000100001110001011001000100010010010000000100000011010001111000011000010100001100000010100001000000000
decoded: [2, 3, 14, 1, 7, 11, 17, 9, 16, 8, 13, 15, 6, 10, 12, 5, 4, 0]

Wren

Translation of: Julia
Library: Wren-math
Library: Wren-check
Library: Wren-fmt
import "./math" for Int, Math
import "./check" for Check
import "./fmt" for Fmt

class Rice {
    static encode(n, k) {
        Check.nonNegInt("n", n)
        var m = 1 << k
        var q = Int.quo(n, m)
        var r = n % m
        var res = List.filled(q, 1)
        res.add(0)
        var digits = Int.digits(r, 2)
        var dc = digits.count
        if (dc < k) res.addAll([0] * (k - dc))
        res.addAll(digits)
        return res
    }

    static encodeEx(n, k) { encode(n < 0 ? -2 * n - 1 : 2 * n, k) }

    static decode(a, k) {
        var m = 1 << k
        var q = a.indexOf(0)
        if (q == -1) q = 0
        var r = Math.evalPoly(a[q..-1], 2)
        return q * m + r
    }

    static decodeEx(a, k) {
        var i = decode(a, k)
        return i % 2 == 1 ? -Int.quo(i+1, 2) : Int.quo(i, 2)
    }
}

System.print("Basic Rice coding (k = 2):")
for (i in 0..10) {
    var res = Rice.encode(i, 2)
    Fmt.print("$2d -> $-6s -> $d", i, res.join(""), Rice.decode(res, 2))
}

System.print("\nExtended Rice coding (k == 2):")
for (i in -10..10) {
    var res = Rice.encodeEx(i, 2)
    Fmt.print("$3d -> $-9s -> $ d", i, res.join(""), Rice.decodeEx(res, 2))
}

System.print("\nBasic Rice coding (k == 4):")
for (i in 0..17) {
    var res = Rice.encode(i, 4)
    Fmt.print("$2d -> $-6s -> $d", i, res.join(""), Rice.decode(res, 4))
}
Output:
Basic Rice coding (k = 2):
 0 -> 000    -> 0
 1 -> 001    -> 1
 2 -> 010    -> 2
 3 -> 011    -> 3
 4 -> 1000   -> 4
 5 -> 1001   -> 5
 6 -> 1010   -> 6
 7 -> 1011   -> 7
 8 -> 11000  -> 8
 9 -> 11001  -> 9
10 -> 11010  -> 10

Extended Rice coding (k == 2):
-10 -> 1111011   -> -10
 -9 -> 1111001   -> -9
 -8 -> 111011    -> -8
 -7 -> 111001    -> -7
 -6 -> 11011     -> -6
 -5 -> 11001     -> -5
 -4 -> 1011      -> -4
 -3 -> 1001      -> -3
 -2 -> 011       -> -2
 -1 -> 001       -> -1
  0 -> 000       ->  0
  1 -> 010       ->  1
  2 -> 1000      ->  2
  3 -> 1010      ->  3
  4 -> 11000     ->  4
  5 -> 11010     ->  5
  6 -> 111000    ->  6
  7 -> 111010    ->  7
  8 -> 1111000   ->  8
  9 -> 1111010   ->  9
 10 -> 11111000  ->  10

Basic Rice coding (k == 4):
 0 -> 00000  -> 0
 1 -> 00001  -> 1
 2 -> 00010  -> 2
 3 -> 00011  -> 3
 4 -> 00100  -> 4
 5 -> 00101  -> 5
 6 -> 00110  -> 6
 7 -> 00111  -> 7
 8 -> 01000  -> 8
 9 -> 01001  -> 9
10 -> 01010  -> 10
11 -> 01011  -> 11
12 -> 01100  -> 12
13 -> 01101  -> 13
14 -> 01110  -> 14
15 -> 01111  -> 15
16 -> 100000 -> 16
17 -> 100001 -> 17