rand7 given rand5

© Parineeth M R

Question 51. Suppose you are given a random number generator that generates numbers uniformly in the range 1 to 5. How will you generate numbers uniformly in the range 1 to 7?


Let’s us say that we are provided with the rand5() function that generates values uniformly from 1 to 5. We can generate values uniformly from 0 to 4 by subtracting 1 from the result of rand5(). Now using rand5() we can uniformly generate numbers in the range 0 to 24 using the following formula

(rand5() – 1) + 5 * (rand5() – 1)

Now to generate numbers uniformly from 1 to 7, we use rejection sampling. If the above formula generates a random number in the range 0 to 20, we accept the number. If the formula generates a number in the range 21 to 24, then we reject the number and re-try the formula till we get a number in the range 0 to 20. We then find the remainder when the number in range 0 to 20 is divided with 7. The remainder will be uniformly distributed in the range 0 to 6. We then add 1 to the remainder to get the result which will be uniformly distributed in the range 1-7.

The rejection sampling in this case can be visualized with a 5 * 5 grid, where in if we throw a dart and the dart randomly lands on a cell, the number in the grid is accepted for some cells and rejected for others.

C/C++


int rand7() {
	int result;
	while(1) {
		result = (rand5() - 1) + (5 * (rand5() - 1) );
		if (result <= 20)
			break;
	}
	result = 1 + (result % 7);
	return result;
}



Java


public static int rand7() {
	int result;
	while(true) {
		result = (rand5() - 1) + (5 * (rand5() - 1));
		if (result <= 20)
			break;
	}
	result = 1 + (result % 7);
	return result;
}



Python


def rand7() :
	while(True) :
		result = (rand5() - 1) + (5 * (rand5() - 1))
		if (result <= 20):
			break

	result = 1 + (result % 7)
	return result