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: Implementing Thalamus's 47-bits with Brian Smith's bit-stream. by Brian Smith)

Brian is absolutely correct.  And I believe Charlie didn't account for it in his algorithm, unless I missed it.

It amounts to throwing away the 47 bits whenever it goes higher than 37^9.  (In my original posting I wrote that this won't happen 92.3% of the time.)  In the other 7.7% of the time, we must throw away the 47 bits, and start over.

This decreases the efficiency a bit, but is still relatively efficient.

Edited on June 16, 2004, 3:06 pm

Posted by Thalamus on 2004-06-16 14:42:14