Wednesday, June 19, 2013


Given a function that outputs a coin toss (a random number from 1 to 2) describe an algorithm that outputs a die roll (a random number from 1 to 6). Each outcome should be equally likely.

One solution is tossing the coin 3 times and using the outcome as bits of a three-bit number. So our outcomes would be 000, 001, 010, 011, 100, 101, 110, 111 (0 to 7). If our outcome is 110 or 111 we would have to discard it and toss again.

I found this solution widely accepted on the web, but it seems that discarding 3 tosses is a waste. It seems like we could reuse the lastly tossed number (in the case of 110 and 111 - 0 and 1), and we would need only 2 additional tosses instead of 3. This would change the algorithm to something like this:

The toss function could reuse the random number method mentioned earlier.

No comments:

Post a Comment