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

 Random Trial (Posted on 2016-10-02)
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.)
 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

 Search: Search body:
Forums (0)