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

Home > Algorithms
Random Number Generator (Posted on 2004-06-08) Difficulty: 3 of 5
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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information