Random number 1..5 to 1..7

The task is to solve this puzzle:

_Given a function which produces a random day Kliwon, Legi, Paing,

Pon, Wage, write a function which produces a random day Sunday to

Saturday_

OK, I modified the question a bit. Read about Anno Javanico if the names of the day sound strange to you. Originally, it says:

_Given a function which produces a random integer in the range of 1 to 5,

write a function which produces a random integer in the range of 1 to 7_

This is well-known as one of the so called Microsoft/Google interview questions. There are million ways to solve it. Here is my take. Bear in my mind that my math skill is mediocre and I never studied computer science, so don’t be surprised if the next few paragraphs look bogus and stupid.

Spoiler warning: If you have passion for puzzles, go away and solve it and then come back again later. Don’t let this blog entry spoils the fun for you.

First, let’s assume the random number 1..5 is generated by the following (the randomness, or lack thereof, of stdlib’s rand() doesn’t play any significant role here):

#include <stdlib .h>
int rand5()
{
 return 1 + rand() % 5;
}
</stdlib>

Now we must write rand7() which gives an integer between 1 and 7 and which is allowed to call only the above rand5().

The trivial solution, which you should have in mind in a fraction of seconds, is:

int rand7()
{
  return rand5();
}

because nowhere it says that the original nor the new function must give a random number following a specific distribution, e.g. uniform distribution. Of course this can or can’t be the real answer, depends on how you look at it.

The next logical step is assuming that the return value of rand7() must have a uniform distribution. The probability to get one of the number in the range of 1..7 is therefore approximately 0.143.

So what comes to mind is to reduce ¹⁄₅ probability from rand5() to ¹⁄₃₅, then increase it again to ⁵⁄₃₅, which equals to ¹⁄₇. The former can be done by calling rand5() several times and treating the first result as 1..5, the second as 6..11 and so on until 31..35. The latter is easier, it’s just a modulus operator. The code for this idea (which is shorter than the explanation above):

int rand7()
{
 static int c = ;
 int x = rand5() + c;
 c = (c + 5) % 35;
 
 return (x % 7)+1;
}

(I know static variables can be evil, but that’s another chapter…)

The disadvantage is obvious, the result is not completely random. For example, the first call will not yield 1 or 7 at all. Another variant is then by making c a bit random, though now that requires two calls to rand():

int rand7()
{
 static int c = ;
 int x = rand5() + c;
 c = (c + 5*rand5()) % 35;
 
 return (x % 7)+1;
}

Another nice solution is by using rejection sampling, similar to the famous Box-Muller transform. Here we expand the range of 1…5 to 1..25 and reject anything larger than 7. The code is:

int rand7()
{
 int x = 8;
 while( x > 7)
  x = rand5() + 5*rand5() - 5;
 return x;
}

Pity that we throw away 8..25. It can be improved by reducing the rejection range to 22..25, IOW we would take anything in the range 1..21:

int rand7()
{
 int x = 22;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;
 int r = 1 + (x % 7);
 return r;
}

(or, further by going to 1…125 and rejecting 120..125).

Modulus of 7 can be “optimized” by hand, this is because 7 is a Mersenne prime. For the details, see what I wrote before on modulus with Mersenne prime. This looks useless and even obfuscates the code, but it’s harmless and you can tease your interviewer 🙂

int rand7()
{
 int x = 25;
 while( x > 21)
  x = rand5() + 5*rand5() - 5;
 
 int r = (x >> 3) + (x & 7);
 r = (r >= 7) ? r - 6 : r + 1;
 return r;
}

Care to share your solutions?