C language random number generation and related topics

The basic method of generating random Numbers

In this article, I will introduce the use of the random number generator provided by c language. Today's c compilers provide a pseudo-random number generator function based on an ANSI standard to generate random Numbers. Both Microsoft and Borland support this standard through the rand() and srand() functions, which work as follows:
First, give srand() a "seed" of type unsignde int with values ranging from 0 to 65,535;
Rand () is then called, which returns a random number (between 0 and 32,767) based on the "seed" value provided to srand().
Rand () is called as many times as necessary to generate new random Numbers;
At any time, you can provide srand() with a new "seed" to further "randomize" the output of rand().

This process seems simple enough, but the problem is that if you supply the same "seed" value every time you call srand(), you will get the same sequence of "random" Numbers. For example, after calling srand() with a "seed" value of 17, you get a random number of 94 when you first call rand(); On your second and third calls to rand(), you get 26,602 and 30,017, respectively. These Numbers seem fairly randomly (although this is just a small collection of data points), but in you again with 17 as "seed" value call srand (), after three times before the rand () call, get the return value is still 94, 26602 and 30017, and then get the return value is still in the first call to the rand () of the rest of the return value. Therefore, you can only get a random number again by providing srand() with a random "seed" value.

The following example USES a simple but effective method to generate a rather random "seed" value -- the time of day.

# include <stdlib. h>
# include <stdio. h>
# include <sys/types. h>
# include <sys/timeb. h>
void main (void){
  int i ;
  unsigned int seedVal;
  struct_timeb timeBuf ;
  _ftime (&timeBuf) ;
  seedVal = ( ( ( ( (unsigned int)timeBuf, time & 0xFFFF) +
          (unsigned int)timeBuf, millitm) ^
          (unsigned int)timeBuf, millitm) ;
  srand ((unsigned int)seedVal) ;
  for(i=O;i<lO;++i)
    printf (" %6dn" ,rand ( ) ) ;
}

The above example first calls _ftime() to retrieve the current time and stores its value in the structure member timebuf.time, which is calculated in seconds from January 1, 1970. After calling _ftime(), millitm, a member of the structure timeBuf, also stores the number of milliseconds that have passed in the current second, but in DOS the number is actually calculated in hundredths of a second. Then, add the number of milliseconds to the number of seconds, and then perform an xor operation with the number of milliseconds. You can apply more logic to both structure members to control the seedVal range and further enhance its randomness, but the logic used in the above example is sufficient.

Note that in the previous example, the output of rand() is not limited to a specified range. Suppose you want to build a lottery selector that ranges from 1 to 44. You can simply ignore the out-of-range values that rand() outputs, but it takes a lot of time to get all the required (say, six) lottery Numbers. Suppose you have built a satisfactory random number generator that produces random data ranging from 0 to 32,767 (as mentioned in the previous article), and you want to limit the output to 1 to 44. The following example shows how to do this:

int i ,k ,range ;
int rain, max ;
double j ;
min=1;  
max=44;  
range=max-min;  
i=rand();  


j= ((double)i/(double)RAND_MAX) ;

i= (int)(j * (double)range) ;
i+ =min;

The above example limits the output random number between 1 and 44, and the principle is as follows:
Get a random number between O and RAND_MAX(32,767). Divide it by RAND_MAX to generate a positive value between 0 and 1.
Multiply the correction value by the desired range value (in this case, 43, or 44 minus 1) to produce a value between O and 43;
Add the value to the required minimum so that the value ends up in the correct range of values from 1 to 44.

You can verify this example with different min and Max values, and you will find that it will always correctly generate a random number between the new rain and the Max value.

Let's take a look at some random number exercises

The title
Given rand7, how do I generate rand3?

Train of thought
A very intuitive idea is to keep calling rand7 until it produces something between 1 and 3 and then returns. The code is as follows :(if someone says there is no 3 here, it doesn't mean I can't judge the size of 3.)

 

  #include <stdio.h> 
   
  int rand_3() 
  { 
    int x; 
   
    while (x = rand_7()) { 
      if (x <= 3) { 
        return x; 
      } 
    } 
  } 

The next step is to determine whether rand_3 is equally likely to produce 1,2,3. In other words, we need to calculate whether the probability of producing 1,2,3 is 1/3.

First of all, rand_7 can generate 1-7 with equal probability. We take rand_3 as an example to generate 1, and assume:

      The probability of 1 being generated the first time is 1/7       The probability of surviving 1 the second time is 4/7 times 1/7, so the first time must have generated something greater than 3 like 4,5,6,7, which is 4/7       And similarly, the probability of getting a 1 the third time is 4/7 squared times 1/7

So the probability that rand_3 generates 1 is P of x=1 is equal to 1/7 +   4/7 times 1/7 plus 4/7 squared times 1/7 plus... Plus 4/7 to the n minus 1 times 1/7 over the geometric sequence
                                                                                                  =   1/7 times 1 minus 4/7 to the n over 1 minus 4/7 is equal to 1/7 times 7/3 is equal to 1/3

Similarly, the probability of verifiably generating 2 and 3 is 1/3

conclusion
The above proof shows that rand3 can produce 1,2 and3 equally. From the above analysis, we can draw a more general conclusion:

If a > B, we can definitely implement rand_b with rand_a, where rand_a is equal to 1 minus a, and rand_b is equal to 1 minus b

extension

Now, given two functions of generating random Numbers, rand_a and rand_b, rand_a and rand_b generate random Numbers of 1-a and 1-b respectively. A and b are not equal. Now, let's use rand_a to realize rand_b.

      If a > B, the above method can be directly adopted       If a < B, then rand_a^2=a * (rand_a - 1) + rand_a, which means the random number to generate 1-a^2. If a^2 is still less than b, then continue to construct rand_a^3=a * (rand_a^2-1) + rand_a

For example
The written test of ali in 2014 is given the random function rand_7 to generate 1-7, see if it can generate other random Numbers?

Let's see if we can generate 1-49 with equal probability, and construct rand_49 = 7 times rand_7-1 + rand_7

Rand_7-1 is equal to the probability of producing 0, 1,2,3,4, 5, 6, and the probability of each number is 1/7, so after *7, you can generate 0,7,14,21,28,35,42, and the probability of each number is 1/7

Since the probability of 0,7,14,21,28,35,42 is 1/7, when each number is added to +rand_7, then 1-49 is generated with equal probability, 1/7 x 1/7 = 1/49, there will be no duplicate data in the middle

So, we have rand_49 with rand_7, and with rand_49, we can of course get any random function that's less than 49 the way we originally filtered it