5 ms·

Arithmetic coding. https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding

• eru 5y ago
  Arithmetic coding is the industrial strength way to do this, yes! However, you can do much simpler and still be pretty efficient (and unbiased). Suppose your range was numbers between 1 to 49 (inclusive). If you get a number between 1 to 32, you interpret that as 5 bits. If you got a number between 33 to 48, you interpret that as 4 bits (because you have 16 == 2^4 possibilities between 33 to 48). If you hit 49, you just drop everything and sample again. So if you got 42, like j7ake suggested, that would be 42 - 32 = 10 = 0b1010. You can generalize this scheme to other numbers of possibilities.