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: This little program doesn't do the trick... by Old Original Oskar!)

That's what I get for typing code in this stupid message window off the top of my head rather than actually punching into the computer then using cut-n-paste...

Here's how my RandomNumberGeneratorSimulator looks on my computer:

Function Random37() As Integer
 
Dim I As Integer
Dim SngJ As Single
 
SngJ = Rnd()
 
For I = 1 To 36
    If SngJ > (1 / (2 ^ I)) Then
        Random37 = I
        Exit Function
    End If
Next I
 
Random37 = 37

 
End Function

And here is the output after 100,000 runs:

  1  .5008-   2  .2499-   3  .12488-   4  .0612-   5  .03088-   6  .0167-   7  .00791-   8  .00347-   9  .00222-   10  .00107-   11  .0005-   12  .00022-   13  .00013-   14  .00005-   15  .00003-   16  .00004-   17  0-   18  0-   19  0-   20  0-   21  0-   22  0-   23  0-   24  0-   25  0-   26  0-   27  0-   28  0-   29  0-   30  0-   31  0-   32  0-   33  0-   34  0-   35  0-   36  0-   37  0-



This is what my algorithm to solve the given puzzle looks like on my computer:

Function Random() As Integer
 
Dim I, J, K, IntArray(37), Temp As Integer
 
' fill array
For I = 1 To 37
    IntArray(I) = I
Next
 
'shuffle array
For K = 1 To 5
For I = 1 To 37
    J = Random37()
    Temp = IntArray(I)
    IntArray(I) = IntArray(J)
    IntArray(J) = Temp
Next I
Next K
 
Random = IntArray(IntArray(Random37()))
 
End Function

And here is the output from the algorithm after 100,000 runs:

  1  .03624-   2  .03212-   3  .03133-   4  .02838-   5  .02893-   6  .02856-   7  .0288-   8  .02959-   9  .02968-   10  .02954-   11  .02997-   12  .02963-   13  .02904-   14  .03016-   15  .02906-   16  .02872-   17  .02637-   18  .0271-   19  .02545-   20  .02483-   21  .02484-   22  .02269-   23  .02209-   24  .02297-   25  .02196-   26  .02259-   27  .02237-   28  .02283-   29  .0232-   30  .0242-   31  .025-   32  .02499-   33  .02603-   34  .02805-   35  .02683-   36  .02816-   37  .0277-

The expected value is 1/37 = 0.027027...

As you might expect, the algorithm is hideously slow due to the large number of loops it has to go through.  I have a better solution which wil show up in a later post.

Posted by Erik O. on 2004-06-08 16:16:03