undefined | Better HN

0 points3170702y ago0 comments

You could also write an arithmetic encoder for a source of 50 uniform symbols. You could implement that without bignum.

0 comments

2 comments · 1 top-level

meindnoch2y ago· 1 in thread

You can't represent 1/50 exactly in binary, thus arithmetic coding can't be equal to the usual numeric base conversion.

Arithmetic coding will produce an encoding from binary to 50-ary symbols. But then again, there are much simpler ways to do that if exact base conversion is not a requirement (e.g. choose a good enough approximate solution for 2^n = 50^m and do the conversion in n-bit chunks).

317070OP2y ago

> You can't represent 1/50 exactly in binary

You can though? You represent the encoder state in fractions of 50. In practice, it means the encoder state will not use all possible binary strings. But you don't need to trade-off in approximation size.

I am not 100% certain, but pretty convinced you can work with much smaller encoder states of only a few bytes, achieving the same compression performance of chunk approximations requiring kilobytes in size of memory.

j / k navigate · click thread line to collapse