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(5): solution - Charlie? | Comment 19 of 26 |
(In reply to re(4): solution - Charlie? by Thalamus)

Sorry, I didn't notice about the "2nd half".  That calls for 47 calls to RNG to get 9 randoms from 1-37.  So that's 47/9=5.2 calls per random 1-37.

Brian reported 1,000,000 random 1-37's using 4,378,259 calls to the RNG (which I verified within statistical accuracy by running his program), so that comes out to 4.4 calls per random 1-37.

Combining the bit idea from the 2nd half of your first post, with Brian's later "bit-stream" approach, each call to RNG produces an average of 2 bits so on average it takes 47/2=23.5 calls to RNG to get the 47 bits needed for 9 random 1-37's, so that's 2.6 calls per random 1-37.

  Posted by Charlie on 2004-06-16 08:58:50
Please log in:
Remember me:
Sign up! | Forgot password

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

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