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.)
 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 = 1Pointer2 = 37 While Pointer1 < Pointer2    If Random37() = 1 Then        Pointer2 = (Pointer1 + Pointer2) / 2    Else        Pointer1 = (Pointer1 + Pointer2) / 2    End IfWend 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

 Search: Search body:
Forums (0)