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?

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