vendredi 4 novembre 2016

Generate random number in given range from random bytes

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:

  1. To determine the number of bytes needed to represent n, calculate

f(n):=ceiling(ln(n)/8ln(2))=ceiling(0.180337*ln(n))

  1. 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

  1. 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