1
$\begingroup$

The obvious way to encode, with minimum entropy, choosing s out of n (equiprobable) choices when x is already encoded is to identify s with a number [0, n) and set x = n * x + s, decoded with s = x % n, x = x / n.

Is this optimal if the only constraint is that the encoded result must be a bitstring? Would *+/% still be the choice if they were not available as instructions?

I know arithmetic coding (and ANS) exists, but it also can't avoid big integer arithmetic without giving up some entropy.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Do you have a different set of allowed instructions in mind? In general, all we need is a bijection between $[n^m] \times [n]$ and $[n^{m+1}]$ for every natural $m$. $\endgroup$ – Yuval Filmus Apr 1 '20 at 21:21
  • $\begingroup$ Not in particular, though basically I have bitwise logic in mind. TBH it's not obvious to me how to even convert a [n^(m+1)] into a bitstring without operations that amount to multiplication. $\endgroup$ – sellon Apr 2 '20 at 16:57
1
$\begingroup$

You can implement ANS using only additions, masks and shifts. Take a look at Finite State Entropy (FSE), it's a performance-focused version of ANS with accurate compression.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.