Random number in range 0 to n

Question

Given a function R which produces true random 32 bit numbers, I would like a function that returns random integers in the range 0 to n, where n is arbitrary (less than 2^32).

The function must produce all values 0 to n with equal probability.

I would like a function that executes in constant time with no if statements or loops, so something like the Java Random.nextInt(n) function is out.

I suspect that a simple modulus will not do the job unless n is a power of 2 -- am I right?

---

I have accepted Jason's answer, despite it requiring a loop of undetermined duration, since it appears to be the best method to use in practice and essentially answers my question. However I am still interested in any algorithms (even if less efficient) which would be deterministic in nature and be guaranteed to terminate, such as Mark Byers has pointed to.

Answer 1

What you're asking for is impossible. You can't partition 2**32 numbers into three sets of exactly equal size.

If you want to guarantee an absolutely perfect uniform distribution in 0 <= x < n, where n is not a power of 2 then you have to be prepared to call R potentially an infinite number of times. In reality you will typically need only one or two calls, but the code has to in theory be able call R any number of times otherwise it can't be completely uniform.

Answer 2

I don't understand why modulus wouldn't do what you want? Since R is a function that produces true random 32 bit numbers, that means that each number has the same probability to be produced, right? So, if you use a modulus n:

randomNumber = R() % (n + 1) //EDITED: n+1 to return values from 0-n

then each number from 0 to n has the same probability!

Answer 3

Without discarding some of the values from the source, you can not do this. For example, a set of size 2^32 can not be partitioned into three equally sized sets. Therefore, it is impossible to do this without discarding some of the values and iterating until a non-discarded value is produced.

So, just use this (pseudocode):

rng is random number generator produces uniform integers from [0, max)
compute m = max modulo (n + 1)
do {
    draw a random number r from rng
} while(r >= max - m)
return r modulo (n + 1)

Effectively I am throwing out the top part of the distribution that causes problems. If rng is uniform on [0, max), then this algorithm will be uniform on [0, n]

Answer 4

You can generate two 32 bit numbers and put them together to form 64 bit number. Worst case scenario can be than biased by 0.99999999976716936 if you do not discharge numbers (if you need number whit no more than 32 bits) that mean that some number have by this factor lower probability than other.

But if you still want to remove this small bias you will have low ration "out of range" hits and in that case more that 1 discharge.

Answer 5

Depending upon your problem/use of the random numbers, maybe you could pre-allocate your random numbers using a slow method and put them into a simple array. Then getNextRnd() can just return the next in the array.

Quick, fixed time call, no branches, just wasting memory (which is usually pretty cheap) and process initialization time.