Random

You are given a function randBit() that returns {0,1}

You want to write a function randNum(start,stop) {a,b} where the function will return a number between a and b with even distribution.


The function is required to run in a guaranteed time, so you can't just use binary representation. ex) you want a number between 0 and 10, the closest bit combination is 16, so a bin representation will fail 6 out 16 times.  What is the best way to do this?

I think might work though:

pick a number k, such that k times n is 2^p, for some power p.

Use the random bit function to generate a random number between 0 and 2^p - 1.

Divide this number by k.

now you have a sort of random number between 0 and n - 1...

The only thing I could imagine going wrong would be rounding issues with the division.