2 hours ago I thought I had this figured out, but now I am doubting myself and want someone to validate my algorithm.
I want to take a stream of
k trusted random bits and convert it to groups of 5 digits in a uniformly distributed range from 0-99999. To do this I take
k and truncate to a multiple of 32, let's say the result now has
n bits where
n = k - k % (4*8). To create one group of 5 digits we load 32 bits into a variable we'll call
var_i. The result will be stored in
var_e. To get 5 digits from 0-99999 takes 17 bits, so we perform the loop:
for (int i = 0; i < 17; i++) var_e += ((var_i >> i) % 2) << i
this way we preserve only the first 17 bits. Then we perform
var_e = var_e % 100000 to truncate
var_e to 5 digits.
var_e is now one complete block of 5 digits.
An alternative algorithm could be to just take a 32 bit number
var_e and perform
var_i = var_e % 100000. This would take just the last 5 digits of the 32 bit number, which fall into the range 0-99999.
These algorithms both waste nearly 50% of the input data, but it would be fairly easy to change the first one to accept 17 bits of input.