Random 5 to Random 7
Brain Teasers
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
Say that I want to write a program that outputs a stream of uniform random numbers from1 to 25; for that I'd just return 5 * (rand5() - 1) + rand5() as in the code in the answer. Now, if I want to build a stream of uniform random numbers between 1 and 21, if I just use the first stream but filter it so that numbers in [22, 25] are rejected, I can build that stream too. Next, if I take this stream and filter it so that for each element x I output x % 7 + 1, I have a stream of uniform random numbers from 1 to 7!
int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};
int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}
How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts. REF: