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 137. So that's 47/9=5.2 calls per random 137.
Brian reported 1,000,000 random 137'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 137.
Combining the bit idea from the 2nd half of your first post, with Brian's later "bitstream" 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 137's, so that's 2.6 calls per random 137.

Posted by Charlie
on 20040616 08:58:50 