All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Random Number Generator (Posted on 2004-06-08)
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.

 See The Solution Submitted by Brian Smith Rating: 2.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re(2): This little program doesn't do the trick... | Comment 8 of 26 |
(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 IntegerDim SngJ As Single SngJ = Rnd() For I = 1 To 36    If SngJ > (1 / (2 ^ I)) Then        Random37 = I        Exit Function    End IfNext 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 arrayFor I = 1 To 37    IntArray(I) = INext 'shuffle arrayFor K = 1 To 5For I = 1 To 37    J = Random37()    Temp = IntArray(I)    IntArray(I) = IntArray(J)    IntArray(J) = TempNext INext 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

 Search: Search body:
Forums (0)