The random number range extension (such as rand7) to rand10 () () (turn)

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

The title:

Known to have a rand7 () function, return 1 to 7 random numbers, so use this rand7 (rand10) 1 (random)~10.

Analysis of : rand10 () to ensure uniform distribution on the integers 1-10, can construct a 1-10*n uniform random integer interval (n for any positive integer). Suppose x is a random integer in the interval 1-10*n, integer x%10+1 is uniformly distributed in the range of 1-10. Because of (rand7) (-1) (*7+rand7) can be constructed out of uniform distribution in the random number 1-49 (reason see note below), can be 41 ~ 49 such random numbers tick away, the number of 1-40 still is uniformly distributed in the 1-40, this is because each number can be viewed as an independent event.

The following explains why (rand7) (-1) (*7+rand7) can be constructed out of uniform distribution in the random number 1-49:

The first rand7 (-1) is obtained from a discrete set of integer {0, 1, 2, 3, 4, 5, 6}, in which each integer probability is 1/7. Then (rand7) *7 (-1) is obtained from a discrete set of integer A={0, 7, 14, 21, 28, 35, 42}, in which each integer probability are 1/7. Rand7 () the set B={1, 2, 3, 4, 5, 6, the probability of each integer in 7} is 1/7. Obviously the set A and B between any two elements can be one one corresponds to an integer between 1-49, that is to say any number between 1-49, can be uniquely determined by a combination of two elements A and B, in turn set. Because the elements of A and B can be regarded as independent events, according to the independent event probability formula P (AB) =P (A) P (B), get the probability of each combination is 1/7*1/7=1/49. Therefore, (rand7) (-1) (*7+rand7) generated integers evenly distributed between 1-49, the probability of each number is 1/49.

1 int rand_10()
2 {
3     int x = 0;
4     do
5     {
6         x = 7 * (rand7() - 1) + rand7();
7     }while(x > 40);
8     return x % 10 + 1;
9 }

Note : why use while (x> 40) instead of while (x> 10)? The reason is if while (x> 10) is the probability of 40/49 circular while, probably dead circulation.

Problem description:

Known random3 () the random number generator to generate [1, the random number range of 3], use the random3 (random5) structure () function, generating [1, random number 5]?

Problem analysis:

How to construct [1-3] range from the larger number? At the same time, to meet the greater number appeared probability is the same, can think of operation includes two kinds: addition and multiplication

Consider the following expressions:

3 * (random3() – 1) + random3();

The range can be calculated by the formula is [1, 9]  and the probability of occurrence of the number is the same, namely 1/9

Now consider how to generate [1 from [1, the number of 9] range, 5] number.?

Can think of is the rejection sampling method, which generated [1, the random number 9], if the number is not within the scope of [1, 5], re sampling

Solution:


1 int random5()
2 {
3     int val = 0;
4     do
5     {
6         val = 3 * (random3() - 1) + random3();
7     }while(val > 5);
8     return val;
9 }

Summary

Will this problem further abstraction, known random_m (random number generator) range is [1, m] and random_n ([1) generation, function n] range, m <n && n <= m *m

The general solution:


 1 int random_n()
 2 {
 3     int val = 0;
 4     int t;   //T is the maximum ratio of N, t and satisfied<m*m
 5     do
 6     {
 7         val = m * (random_m() - 1) + random_m();
 8     }while(val > t);
 9     return val;
10 }




Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Leo at November 18, 2013 - 6:18 AM