Rice coding: Difference between revisions
Content added Content deleted
(Added Python) |
|||
Line 202: | Line 202: | ||
{{out}} |
{{out}} |
||
<pre>Same as Phix entry.</pre> |
<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}}== |
=={{header|Julia}}== |