Rice coding: Difference between revisions
→{{header|jq}}
(Added Python) |
|||
Line 202:
{{out}}
<pre>Same as Phix entry.</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|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, ...].
<syntaxhighlight lang="jq">
# 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))" )
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
=={{header|Julia}}==
| |||