## Implement rand7() using rand5()

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. (i.e., implement rand7() using rand5()).

Solution:
First, observe that we cannot do this in a guaranteed finite amount of time. Why? Let’s see by a parallel example: How would you use rand2() to create rand3()?
Observe that each call of rand2() and the corresponding decision you make can be represented by a decision tree. On each node, you have two branches. You take the left one when rand2() equals 0 (which happens with 1/2 probability). You take the right one when rand2() equals 1 (which happens with 1/2 probability). You continue branching left and right as you continue to call rand2(). When you reach a leaf, you return a result of 1, 2 or 3 (your rand3() results).

• What’s the probability of taking each branch? 1/2
• What’s the probability to reach a particular leaf node? 1/2^j (for some j).
• What the probability of returning 3 (for example)? We could compute this by summing up the probabilities of reaching each leaf node with value 3. Each of these paths has probability 1/2^j, so we know that the total probability of returning 3 must be a series of terms of reciprocal powers of 2 (e g , 1/2^x + 1/2^y + 1/2^z + …).

We also know, however, that the probability of returning 3 must be 1/3 (because rand3() should be perfectly random). Can you find a series of reciprocal powers of 2 that sum to 1/3? No, because 3 and 2 are relatively prime.
We can similarly conclude that to solve this problem, we will need to accept a small (infinitesimally small) chance that this process will repeat forever. That’s ok.
So, how do we solve this?
In order to generate a random number between 1 and 7, we just need to uniformly generate a larger range than we are looking for and then repeatedly sample until we get a number that is good for us. We will generate a base 5 number with two places with two calls to the rand5().

```	public static int rand7() {
while (true) {
int num = 5 * (rand5() - 1) + (rand5() - 1);
if (num < 21)
return (num % 7 + 1);
}
}

I personally like this post better: here
public static int rand7() {
int vals[][] = {
{ 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.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2dea3be81b9', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2dea3be81e9',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2dea3be81ec',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});