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.)
A faster solution than my earlier one... | Comment 9 of 26 |

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 2004-06-08 16:29:15
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 (7)
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