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(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

 Search: Search body:
Forums (0)