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.
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.
My approach
