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.)
Some Thoughts My approach Comment 3 of 3 |
This is my algorithm to solve this problem (written in UBASIC).  The main random number generator is in lines 100-201.  The basic idea is that the 'wasted' numbers from Paul's algorithm can be fed back into the algorithm so we don't need to make two calls to the 1-7 rng each time.

    1   randomize
   10   dim Count(10)
   20   for X=1 to 10
   30   Count(X)=0
   40   next X
   50   Trials=100000
   60   Calls=0
   61   Critical=0
   70   for Test=1 to Trials
   98   ' irnd@7+1 generates a random integer 1-7
   99   ' start our 1-10 rng
  100   R=irnd@7+1:Calls=Calls+1
  101   UpperR=7
  110   while UpperR>1
  120   N=(R-1)*7+irnd@7+1:Calls=Calls+1
  121   UpperN=UpperR*7
  130   X=UpperN@10
  140   if N>X then 200
  150   R=N:UpperR=X
  160   wend
  170   ' if we got here, start over with finding a random 1-10
  171   Critical=Critical+1
  172   goto 100
  200   ' random value generated
  201   Value=ceil((N-X)@10)+1
  210   Count(Value)=Count(Value)+1
  300   next Test
  310   for X=1 to 10
  320   print Count(X);
  330   next X
  340   print:print Calls,Critical

A sample output is:
9860 9915 9998 9892 9995 9983 10135 10254 9942 10026
219419 35

The first line shows the distribution of 1-10 values generated.  The second line shows the total number of calls to the 1-7 rng and the number of 'critical' events where the algorithm needed to reseed with two 1-7 rng numbers.  This implies this algorithm averages just under 2.2 calls per number generated.  A decent improvement over the 2.45 from the simple approach that Paul gave. 

  Posted by Brian Smith on 2016-12-31 23:33:43
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 (2)
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