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.

Okay, in the interests of answering the question (without consideration of efficiency):

Utilize the random number generator in sets of "six".

Filter the results as follows.  Every time the generator returns a 1, write "1", every time the generator returns any other integer, write "0".

The concatenation of those 6 binary digits will represent a number from 0-63 (with even distribution).

If the number falls outside the range of 1-37, throw the trial away, and do it again.  If the number falls inside the range of 1-37, that is the number you return.
___________________________________

The efficiency of this method can be calculated as 37/63 = ~ 58.7%

There are several ways of improving upon this efficiency, such as:

So, really run this for 47 bits of information.

This will generate a binary number from 0 to 2⁴⁷ - 1.

This happens to be 140737488355328 combinations.
And 37^9 happens to be 129961739795077.

Therefore, we can assign these on a 1-1 basis (as we did above) and now we are over 92.3% efficient.  (Though we are always generating 9 random numbers from 1-37, at a time.)

Edited on June 8, 2004, 1:51 pm

Posted by Thalamus on 2004-06-08 13:50:58