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.

Here is a solution that I believe wastes no information from any of the rand5 calls at all. What's interesting about this one is that I believe it is possible in some cases to generate a result without calling rand5 at all! However, it requires an arbitrary-precision math library (maybe something like Mathematica) to run.

The idea is similar to Charlie's large base 5 and base 7 integer ideas, and also gets some inspiration from the algorithm from Arithmetic Encoding.

Imagine a number x such that 0 ≤ x < 1. If you convert it to base 7, you have a string of digits between 0 and 6. If values of x are evenly distributed in the interval, each digit can be an integer between 0 and 6 with equal probability for each possible value. Add 1 and you have a possible return value for the function. x in base 7 represents an infinite list of random values that can be used in the solution--all you have to do is determine x.

Unfortunately, we don't have a function for generating a random real number with infinite precision. We do, however, have the rand5 function. What we do is slap down a decimal point and use a string of rand5 calls to generate x in base 5.

We can't call rand5 an infinte number of times. However, that's OK because we don't need an infinte number of results. We can use rand5 to approximate x to greater and greater precision by adding single digits one right after the other. If we call rand5 n times, we have a lower bound on x to within 5^(-n). Moreover, if you add 1 to the last digit you added (carrying 1s to keep it the number in base 5), you have an upper bound on x with similar precision.

So what you do is convert these upper and lower bounds to base 7. Compare these numbers digit by digit. If corresponding digits are equal, you have a known digit of x.

Here's the algorithm:

// BigInt - an integer type that can hold arbitrarily
// large values.
// Rational - a numeric type that supports rational
// numbers using a numerator and denominator of type BigInt
// Both types support all normal mathematical operations
// plus exponentiation.
// In addition, Rational has a member function for finding
// the nth digit after the decimal point in base b.
static Rational x(0);
static BigInt i5(0);
static BigInt i7(0);

++i7;

while (x.digit(i7, 7) != (x + 1 / BigInt(5).exp(i5).digit(i7, 7))
{
    ++i5;
    x += BigInt(rand5()) / BigInt(5).exp(i5);
}

return x.digit(i7, 7) + 1;

I think this algorithm is optimal for any number of calls, using Charlie's theoretical minimum of log(7)/log(5) calls to rand5 per number generated.

Posted by friedlinguini on 2003-07-01 06:55:26