A particular random number generator returns positive integer n with probability 1/(2^n). (ie '1' with probability 1/2, '2' with probability 1/4, '3' with probability 1/8, etc.)

Using this random number generator, write an algorithm which chooses a random integer from 1 to 37 with equal probability.

(In reply to re(4): solution - Charlie? by Thalamus)

Sorry, I didn't notice about the "2nd half".  That calls for 47 calls to RNG to get 9 randoms from 1-37.  So that's 47/9=5.2 calls per random 1-37.

Brian reported 1,000,000 random 1-37's using 4,378,259 calls to the RNG (which I verified within statistical accuracy by running his program), so that comes out to 4.4 calls per random 1-37.

Combining the bit idea from the 2nd half of your first post, with Brian's later "bit-stream" approach, each call to RNG produces an average of 2 bits so on average it takes 47/2=23.5 calls to RNG to get the 47 bits needed for 9 random 1-37's, so that's 2.6 calls per random 1-37.

Posted by Charlie on 2004-06-16 08:58:50