There are similar questions, but most of them too language specific. I'm looking for a general solution. Given some way to produce k random bytes and a number n, I need to produce a random number in range 1...n (inclusive).
What I've come up with so far:
- To determine the number of bytes needed to represent n, calculate
f(n):=ceiling(ln(n)/8ln(2))=ceiling(0.180337*ln(n))
- Get a random number in range in range 1...2^8f(n) for 0-indexed bytes b[i]:
r:=0
for i=0 to k-1:
r = r + b[i] * 2^(8*i)
end for
To scale to 1...n without bias:
R(n,r) := ceiling(n * (r / 256^f(n)))
But I'm not sure this does not create a bias or some subtle one-off error. Could you check whether this sound and/or make suggestions for improvements? Is this the right way to do this?
In answers, please assume that there are no modular bit-twiddling operations available, but you can assume arbitrary precision arithmetics. (I'm programming in Scheme.)
Edit: There is definitely something wrong with my approach, because in my tests rolling a dice yielded a few cases of 0! But where is the error?
