# Alternatives to multiplication/division/modulo for encoding choices?

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.

• 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$. – Yuval Filmus Apr 1 '20 at 21:21
• 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. – sellon Apr 2 '20 at 16:57