techInterview Discussion

Given a function rand5() which can generate numbers 1-5 with a euqal probability, how to generate number 1-7 with equal probability using rand5()?

<XKCD>
int getRandomNumber() {
  return 4; // chosen by fair die roll.
    // guaranteed to be random.
}
</XKCD>

Use rand5 twice, then you have a number n from 1 to 25 equally likely. If n is less than or equal to 21, then return (n-1)%7+1, otherwise try again.

That's the basic idea. The optimal approach (counting expected calls to rand5()) is a bit more involved.

Call rand5 two times and then you get a number between 0 to 24..
Divide the spectrum evenly as...0-2 : 1; 3-5 : 2, ...,18-20 : 7...for the rest of the values 21,22,23,34 repeat this procedure...i think this will give you a random distribution

Hi jdk, how do you do this?
Use rand5 twice, then you have a number n from 1 to 25 equally likely?

Previously: http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=1133&ixReplies=14

jdk:
 
how you will generate a prinme number [ex: 17, 19...]with two rand5 funtion() ?

By doing 5 * (rand5() - 1) + rand5() instead of rand5() * rand5().