2 ms·
In the limit, that’s arithmetic decoding (https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding). An intuitively simp
by Someone 6y ago
In the limit, that’s arithmetic decoding (https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding).
An intuitively simple way (but likely not the way this is done in real life) to do this is
- treat your stream of random bits as a binary float F in [0,1)
- when you need an integer in [0,n), do:
F = nF # F is in [0,n) now
r = floor(F) # desired integer in [0,n)
F = F - r # restores the invariant that F is in [0,1)
return r
Since F is infinitely long, you have to do this lazily. You can cheat by only do the multiplication up to the bits you need now*, and fill in others by random bits later (that’s an error in the multiplication, but doesn’t matter for this algorithm)