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.
Charlie's program got me thinking that I was giong about this all wrong and I came up with a new idea...
Using two pointers, one for the upper end of values and one for the lower end of values I retrieve a number from the Weighted_Random_Number_Generator. If the returned value is 1, then I move the upper pointer down to halfway between the previous upper and lower pointer values, if it is something other than 1 I move the lower pointer up to halfway between the upper and lower pointers. When the pointers meet, I return that value.
It works pretty well, but for some reason 1 and 37 are returned only half as often as expected. Here's the code:
Function Random2()
Dim Pointer1, Pointer2, IntArray(37) As Integer
Pointer1 = 1
Pointer2 = 37
While Pointer1 < Pointer2
If Random37() = 1 Then
Pointer2 = (Pointer1 + Pointer2) / 2
Else
Pointer1 = (Pointer1 + Pointer2) / 2
End If
Wend
Random2 = Pointer2
End Function
...and here are the results after 100,000 runs:
1 .01406 2 .02708 3 .02799 4 .02785 5 .02734 6 .0273 7 .02658 8 .02783 9 .0284 10 .02854 11 .02798 12 .02753 13 .02844 14 .02697 15 .02887 16 .02776 17 .02691 18 .02775 19 .02724 20 .02841 21 .02779 22 .02889 23 .02776 24 .0281 25 .02747 26 .02711 27 .02747 28 .02722 29 .02768 30 .02722 31 .02858 32 .02834 33 .02738 34 .02842 35 .02804 36 .0273 37 .0144
The expected value is 0.027027...

Posted by Erik O.
on 20040608 16:29:15 