There is a basic algorithm problem discussed in the group before, and it has been mentioned more than once that RAND5 () generates RAND7 (). It looks very simple, but actually there are many careful machines, and it is also a very interesting and clever problem. Although there are a lot of answers on the Internet, but some are not step-by-step, so write an article, the reason for the train of thought.

So the original question was, 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.

So it’s very simple, but it does imply some basic constraints that we don’t say, but everyone assumes, that you can only use RAND5, which is a known function, and a few simple operators, and you can’t introduce other functions or encapsulate special operators. But if you think it’s really easy, you probably won’t.

I think that no naive person would achieve this

int rand7(){
    return 2+rand5();
    }

Why is that wrong? Because it’s very simple, this function doesn’t produce a 1, it doesn’t satisfy this condition.

And what if that happens?

int rand7()
{
     int i;
     i = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5();
     return i%7 + 1;
 }

Well, that looks like a good idea, if you take the least common multiple of 5 and 7, seven fives, modulo 7, each number has a probability of 1/5, which is exactly 1-7. Actually, that’s also wrong.

In line 4, 5^7 possible calculations will be generated, which will eventually map to the integer interval [7,35], but the probability of integer generation in the interval [7,35] is not equal. This is a bit confusing, but let’s use a simpler example, if we have a () function of rand3, three rand3() will generate the numbers in the interval [3-9], but the numbers in the interval [3-9] will not be uniform.

3=1,4 =3,5 =6,5,6,5,6,7,6,7,8,7,8,9 # Each number probability 3=1,4 =3,5 =6,6 =7,7 =7,7 =6,8 =3,9 =1

In fact, even those with the slightest sensitivity to numbers can immediately tell that 2+4=6, 4+2=6, and obviously there are many combinations of numbers in the middle, which are more likely to occur. This leads to a high school math probability question, “What is the probability that a couple will have two children, one of whom is a boy, and ask the other to be a girl?” . The two questions are essentially the same.

So what’s the right thing to do? So again, the whole point of RAND7 is not only to generate a number between 1 and7, but to make sure that the number is random, equal in probability. It’s only true if the probability is even. How about if I write it this way?

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; }

I’m going to make a square matrix, and I’m going to put 1 through 7 evenly, and then I’m going to use rand5 only to generate coordinates, is that right? Let’s see if the following two constraints are met: 1. Generate the seven numbers 1-7. 2.1-7 have equal probability of occurrence

The first condition, of course, is satisfied. The second condition, the numbers 1-7, each of the probability of the occurrence is 3/25, although the matrix has 0 as a purely filling number (0 or 10, it doesn’t matter), but does not interfere with the 1-7 occurrence of the equal probability constraint.

But this way of writing it is too ugly, and it takes up extra space, but another way to do it, actually, the square matrix method, converted to a simpler code, should be

int rand7() { int i; do{ i = 5 * (rand5() - 1) + rand5(); }while(I > 21);}while(I > 21); Return I %7 + 1; return I %7 + 1; // Map [1,21] to [1,7]}

In fact, this question is an introduction to the algorithm in a question, but also the Internet companies of the eight-part algorithm, is a general template. The 5 and 7 above can be replaced by any a or b that satisfies (a<b).

That is, if you are given RANDA, you can easily construct Randb in the following way, generating random numbers from 1 to B.

Randb = a * (Randa – 1) + Randa

If I have Rand7, what if I want to form Rand5? It’s very simple, if you take out the 6 and the 7, you’re going to get rand5, which means when it’s more random than 5, it’s going to random again, until it’s less than or equal to 5.

int rand5(){
    Rint result = rand7()+1;
    while (result > 5){
        result = rand7()+1;
    }
    return result;

}

Simple, but the right thing to do. In fact, it is the same idea as the above mentioned RAND5 to generate RAND7, first use RAND5 to enlarge the range, and then exclude the exceeded range, so that the range is a multiple of 7.