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?

Do your own damn homework.

Using C and assuming that we get eight bits to the char (and further that randBit is evenly distributed),

int randNum(int a, int b)
{
    int out = 0;
    for (int i = 0; i < sizeof(int)*8; i++)
        out = (out << 1) | randBit();
    out = (out % (b - a)) + a;
    return out;
}

Otherwise you could use randBit to generate a seed for an LCG or some other PRNG.