Rice coding: Difference between revisions
Added Algol 68
(→{{header|Lua}}: tweak) |
(Added Algol 68) |
||
Line 5:
Rice coding is initially meant to encode [[w:natural numbers|natural numbers]], but since [[w:relative numbers|relative numbers]] are [[w:countable|countable]], it is fairly easy to modify Rice coding to encode them too. You can do that for extra credit.
=={{header|ALGOL 68}}==
{{Trans|Julia|with output formatting similar to the Wren sample}}
<syntaxhighlight lang="algol68">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|F_Sharp|F#}}==
Line 38 ⟶ 166:
100001 -> 17
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">""" Golomb-Rice encoding of a positive number to bit vector using M of 2^k"""
| |||