**Problem:**

Write a method to generate a random number between 1 and 8, given a method that generates a random number between 1 and 3. The distribution between each of the numbers must be uniform.

**Solution:**

Let’s think of this like a decision tree. Each rand3() will be a decision.

If we somehow generate integers from 1 to a-multiple-of-8 (like 8, 16, 24, …) with equal probability, we can use modulo division by 8 followed by adding 1 to get the numbers from 1 to 8 with equal probability.

We try to get maximum bunches of 8 as we can (1 – 16, 2 sets of 8). If we get any of the other values, we just try again. Since the probability of getting each of 16 values are the same every time, trying again won’t affect their probabilities.

We can generate from 1 to 16 with equal probability using the following expression.

6*rand3() + rand3() – 3

See, how this can be used?

1. For each value of first rand3(), there can be 6 possible combinations for values of second rand3(). So, there are total 18 combinations possible.

2. The range of values returned by the above equation is 1 to 18, each integer occurring exactly once.

3. If the value of the equation comes out to be less than 17, return modulo division by 8 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/8.

// returns 1 to 8 with equal probability int my_rand() { int i; while(1) { i = 6*rand3() + rand3() - 3; if (i < 17) return i%8 + 1; } }

create a 3X3 matrix and fill the numbers as 1,2,3,4,5,6,7,8,-1. Assume rand3 as dice, roll it twice for i and j in matrix and return the number on i,j th location of matrix. In case the number is -1, repeat the step. probability will be equal as it would be 1/9.

1,1 and 2,3 will give same result

integer rand8() {

result = (rand3() – 1) * 3 + rand3();

if (result != 9)

return result;

else

rand8();

}

That was my idea too. Seems like the same sort of “keep trying until it’s the result you were looking for” philosophy but a lot simpler.

its not working, here is its java code:

import java.math.*;

class Solution

{

public static int my_rand()

{

int i=(int)(3*(Math.random()%3) + (Math.random()%3 +1));

if (i!=9) return i;

else return my_rand();

}

public static void main(String[] args)

{

for(int i=1;i<=8;++i)

System.out.println(my_rand());

}

}

I really don't understand the decision tree metaphor at all. This is a just math.

First a couple nitpicky wording items. Between 1 and 3, doesn't say inclusive or exclusive. So we will assume that both of the betweens are inclusive, because just returning 2 (exclusive) isn't really random. This sort of ambiguity creates fence post errors (like the one on line 8).

The possible options for 6*rand3()+rand3() – 3 are… 4,5,6.10,11,12,16,17,18 with mod 8, gives, 4,5,6,2,3,4,0,1,2. Since the last two are ignored, because they are 17 or greater, this leaves the possible results as (4,5,6,2,3,4,0)+1. Note this is only 7 probabilities, with one duplicate. So two values will never occur.

A simpler math solution would be i = 3*(rand3()-1)+rand3(), and don't return any values over 8. However that said, since we are working with pseudo random number generators, skipping one out of 9 values will mess with the pseduorandomness and probably the distribution of these values. Better to go rewrite rand3(), to be rand8().