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^i end for
-
To scale to 1...n without bias:
R(n,r) := n * (r / 8*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.)
Aucun commentaire:
Enregistrer un commentaire