5 ms·

Funny. I'm trying to write a base50 encoder now. No good reason, just 'cuz. Can't quite figure out what to do with the half a bit. Gotta carry it forward someho

Funny. I'm trying to write a base50 encoder now. No good reason, just 'cuz. Can't quite figure out what to do with the half a bit. Gotta carry it forward somehow until I have a full char again but haven't come up with a good scheme.

rustybolt 3y ago
What do you mean, half a bit? A typical base50 encoder would use 50 characters, so say 309 would get encoded as 69 (309 = 6 * 50 + 9 * 1).
- cjm42 3y ago
  He meant approximately half a bit. Base64 uses 64 characters, which means 6 bits per character. 50 characters gives you about 5.64 bits per character. Unlike Base64's 3-bytes-equals-4-characters, that never comes out evenly.
VMG 3y ago
write a base-n encoder and use 50 as a parameter
meindnoch 3y ago
Interesting choice. You won't be able to do it in batches because 50^n = 2^m doesn't have a solution with integer n and m. So you basically have to implement a bignum with division and modulo operations.
- charlieyu1 3y ago
  On the other hand, base91 is a real thing
  - meindnoch 3y ago
    Base91 encodes 13 bits (8192 possibilities) in two base91 symbols (8281 possibilities), so it's not 100% efficient.
- 317070 3y ago
  You could also write an arithmetic encoder for a source of 50 uniform symbols. You could implement that without bignum.
  - meindnoch 3y ago
    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).
    - 317070 3y 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.

rustybolt 3y ago

What do you mean, half a bit? A typical base50 encoder would use 50 characters, so say 309 would get encoded as 69 (309 = 6 * 50 + 9 * 1).

cjm42 3y ago
He meant approximately half a bit. Base64 uses 64 characters, which means 6 bits per character. 50 characters gives you about 5.64 bits per character. Unlike Base64's 3-bytes-equals-4-characters, that never comes out evenly.

VMG 3y ago

write a base-n encoder and use 50 as a parameter

meindnoch 3y ago

Interesting choice. You won't be able to do it in batches because 50^n = 2^m doesn't have a solution with integer n and m. So you basically have to implement a bignum with division and modulo operations.

charlieyu1 3y ago
On the other hand, base91 is a real thing
- meindnoch 3y ago
  Base91 encodes 13 bits (8192 possibilities) in two base91 symbols (8281 possibilities), so it's not 100% efficient.
317070 3y ago
You could also write an arithmetic encoder for a source of 50 uniform symbols. You could implement that without bignum.
- meindnoch 3y ago
  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).
  - 317070 3y 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.