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

Home > Algorithms
Random Trial (Posted on 2016-10-02) Difficulty: 3 of 5
Consider a function capable of generating a random integer between 1 and 7 inclusively with equal probability.

Using this, devise an algorithm to generate a random number between 1 and 10 inclusively with equal probability.

Assume that using the 1-7 generator function is pretty time-consuming, so you want to minimize the number of times you are going to use it.

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
One approach | Comment 2 of 3 |
Generate two 1-7 random numbers, treat them as digits of a base 7 integer, and convert to base 10 (treat 7's as 0's for conversion) to get a number from 0 to 48.

If the number in question is >= 40, ignore it and try again. Otherwise, the desired random number is the value mod 10 (this time treating 0's as 10's.)

The probability of having to ignore a number is 9/49, so the average number of attempts needed is 1 + (9/49) + (9/49)^2 +... = 1 / (1 - 9/49) = 49/40. Since each attempt requires two random numbers, the average number of calls to the 1-7 generator is 49/20 = 2.45

I don't love the fact that this algorithm will occasionally be very unlucky, though. If it were me and I could choose between this one and another that took, say, 4 generations but always took exactly 4, I'd almost certainly prefer the latter even though it's more costly on average.


  Posted by Paul on 2016-10-03 12:46:40
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 (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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