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.

>>2
djoasn hekl^{p h}lim!

>>2
Since everything is marked as signed, if the first randBit() is 1 and you are on a two's complement machine you'll return a number outside the range.

Fixing that, that method still won't work. Take a=0, b=3
Probabilities (for sizeof(int)==4):
0: 1431655766/4294967296
1: 1431655765/4294967296
2: 1431655765/4294967296
The result is biased towards 0.

int randnum(int a, int b) {
{
    b -= a;
    while (b--) a += randBit();
    return a;
}

That's horribly inefficient, though.

>>2
Your use of ``8'' makes the code non-portable.

>>2
U MENA CHAR_BIT

>>5
Won't that be more distributed towards the middle of the set {a,b}

It's possible if and only if 1/(b - a) has finite representation in base 2. Proof left as an exercise for the reader.

Note however that for any error epsilon, there exists an algorithm producing numbers distributed uniformly within that error in constant time.

The real problem here is the OP's aversion to rejection sampling, which is actually an extremely useful method, and is guaranteed to run faster than any bit munging ``solution''. A related problem is producing an algorithm to uniformly sample points from a circle (Although that one actually has a solution).

>>8

yes, it's like flipping a coin, B times, and counting how many times you got heads. There are more ways to get a number close to the middle, or half the number of tosses. Sometimes this is an efficient way to achieve the effect though. Some video games I've seen use it to get a distribution for damage.

you could use the randBit function to generate each bit of the number, but when you generate a bit, you only consider choices that will keep the number within the proper range. So if I had to generate a random number between 0 and 15, using a random digit function, I could choose the most significant digit first. The only valid digits are 0, or 1, so say I randomly get 1. So I have 1X, where X has not yet been determined. I then observe that 0 <= X <= 5, so I let X be a random digit in {0, 1, 2, 3, 4, 5}.

Since you are generating bits, though, you'll either be sampling from {0, 1} or from {0}, and in the later case, there is only one possible choice, so no smapling is needed then. You can just use a zero.

But lets say you are going between 0 and 17. There are 32 bit possibilities, and you can't guarantee that it will ever actually give you a number between 0 and 17.

>>10

nuyah, wait, this is wrong. It's definitely wrong if you go from the least significant digit to the most significant digit. Since, when generating a number between 00 and 10 in base 10, 10 will be chosen whenever a one is selected for the tens digit, which will be half the time. It might work going from least significant to most significant though, but maybe not. It would probably just be close to random.

You can think of the random bit function as a perfectly balanced coin you can flip, and you can think of the number you need to generate, one of n choices you can make. So using a coin, can you randomly decide to make one of n choices? It's easy to do when n is a power of two, but it'll take something fancy to get it perfect for general n.

*It's definitely wrong if you go from the most significant digit to the least significant digit.

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.

using a large power of two would make the rounding errors less significant. You could actually just take the modulus instead. This is similar to how people get random int in an interval [0, n), using a rand() function that generates random ints in [0, MAX_INT].

int r = rand() % n;

this is actually very similar to trying to create a perfectly balanced binary tree with exactly n leaf nodes. You just can't do it unless n is a power of two. You can get close though, by have a binary tree that is perfectly balanced everywhere except its lowest level.

>>14
Or the fact that any number which is not a power of 2 is not a factor of 2^p for any p.

int random(int a,int b){
   return 4;
}

I wonder how many people in /prog don't understand what is being discussed in this thread.

Yup, it looks like someone just layed the academic smackdown on the mental midgets.

>>18
What is this? Minecraft?

>>19
I wonder how many people on /prog/ are too dense to realize what sarcasm is

>>17

k would have to be a rational number

>>22
Sarcasm is difficult to convey using only text.