CODEWITHSUNDEEP
algorithmrandomcryptographynumeric-ranges
Eric '3ToedSloth'
Eric '3ToedSloth'

Reputation: 374

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^(8*i) end for

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

Upvotes: 2

Views: 579

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134035

This is similar to what you'd do if you wanted to generate a number from 1 to n from a random floating point number from 0 to 1, inclusive. If r is the random float:

result = (r * n) + 1

If you have arbitrary precision arithmetic, you can compute r by dividing your k-byte integer by the maximum value expressible in k bytes, + 1.

So if you have 4 bytes 87 6F BD 4A, and n = 200:

((0x876FBd4A/0x100000000) * 200) + 1

Upvotes: 3

Related Questions