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.