Suppose you have a function (or a magic ball) that is capable of producing a totally random integer between 1 and 5 (inclusive).
Using this, how would you generate a random number (also an integer) between 1 and 7 (inclusive)? (Note that the for the number to be random, all integers between 1 and 7 must have an equal chance of being generated)
Assume that using your 1-5 generator is pretty time-consuming, so you want to minimize the number of times you are going to use it.
In
Quick and Dirty Solution, every time through the loop, the algorithm must generate two random numbers. However, this isn't always necessary. If the first pair of numbers doesn't generate a good result, there is still a 'wasted' random number. That is, the loop must repeat if c is calculated to be 21, 22, 23, or 24. Each of these four is equally likely, so there is a 'free' random number with four possibilities. This number can be reused in conjunction with another number from rand5 to generate more possible answers. The code could be changed so that if an iteration through the loop does not provide an answer, then we reuse the variable
a to show which of the four 'remainder' values is used. Since there are not necessarily 5 possible values for
a, we need another variable,
aSize, to show how large a pool
a is picked from. Note that if
a is picked from too small a pool (such as 1), we need to regenerate
a from scratch using rand5.
The revised solution might look like:
int a = rand5() - 1;
int aSize = 5;
while (true)
{
int groupSize = aSize * 5 / 7;
if (groupSize == 0)
{
a = rand5() - 1;
aSize = 5;
continue;
}
int b = rand5() - 1;
int c = a * aSize + b;
int result = (c % groupSize) + 1;
if (result <= 7)
return result;
int aSize = aSize * 5 - 7 * groupSize;
a = c - 7 * groupSize;
}
The number of expected calls is trickier in this case because not all iterations through the loop are equal. We can denote En to represent the number of expected calls needed when you already have a value for a, and when n is a particular value for aSize. To start off,
E = 1 + E5
because after calling rand5 once, we have an aSize of 5.
In the E5 case, we need to call rand5 once more. This leads to 25 possible combinations. If we take this result in groups of 3, there are 4 different possible remainder values. Thus,
E5 = 1 + 4/25 * E4
With E4, another call to rand5 will give 20 possible combinations. Here, we use groups of 2, which will give 6 possible remainder values. Thus,
E4 = 1 + 6/20 * E6
Continuing this pattern,
E6 = 1 + 2/30 * E2
E2 = 1 + 3/10 * E3
E3 = 1 + 1/15 * E1
Remember that if aSize is 1, it isn't useful; we have to start over. Thus,
E1 = E.
We can now start substituting backwards to obtain a single equation in terms of E.
E3 = 1 + 1/15 * E
E2 = 1 + 3/10 * (1 + 1/15 * E) = 1 + 3/10 + 3/150 * E = 13/10 + 1/50 * E
E6 = 1 + 2/30 * (13/10 + 1/50 * E) = 1 + 13/150 + 1/750 * E = 163/150 + 1/750 * E
E4 = 1 + 6/20 * (163/150 + 1/750 * E) = 1 + 163/500 + 1/2500 * E = 663/500 + 1/2500 * E
E = 2 + 0.16 * (663/500 + 1/2500 * E) = 2 + 663/3025 + 1/15625 * E = 6713/3025 + 1/15625 * E
Solving this last equation for E finally gives:
E = 6713/3025 / (1 - 1/15625)
= ~2.219
Optimal Solution
