C++ random number generation example

  • 2020-05-10 18:31:45
  • OfStack

If you were asked to use C++ to generate random Numbers between 0 and N-1, what would you do? You might say, well, that's easy. Look:


srand( (unsigned)time( NULL ) );
rand() % N;

Think about it for a second. Is this result random (of course, we don't consider the pseudo-randomness of the rand() function)?
No, because the upper limit of rand() is RAND_MAX, and in the case of 1, RAND_MAX is not an integral multiple of N, then if RAND_MAX % = r, then the probability between 0 -- r is 1 greater and r+1 -- N-1 is 1 less. And if N > RAND_MAX, what do you do?
The following is a more suitable scheme, which can generate a random number result with equal probability in any range. Finally, there is an easier way.
1. If N < RAND_MAX+1, the mantissa is removed,              


 R = RAND_MAX-(RAND_MAX+1)%N; // Remove the mantissa 
  t = rand();
  while( t > R ) t = rand();
  result = t % N; //  Random number that meets the requirements 

2. If N > RAND_MAX, you can consider segmented sampling and divide it into [n/(RNAD_MAX+1)] segments. You can get the segments with equal probability and then get a certain element in each segment. In this way, segmentation also has a mantissa problem.

The data of the selected remainder segment is taken out and selected. Firstly, the probability of the occurrence of the selected remainder segment is selected for one time, and then the data is selected separately:            


 r = N % (RAND_MAX+1); // remainder 
  if ( happened( (double)r/N ) )// The probability of picking the remainder 
  result = N-r+myrandom(r); // myrandom Available case 1 Code implementation in 
  else
  result = rand()+myrandom(N/(RAND_MAX+1))*(RAND_MAX+1); //  If the remainder can't be selected, select the segment 

Complete code:


#include<iostream.h>
#include<time.h>
#include<stdlib.h>
const double MinProb=1.0/(RAND_MAX+1);
bool happened(double probability)//probability 0~1
{
 if(probability<=0)
 {
return false;
 }
 if(probability<MinProb)
 {
 return rand()==0&&happened(probability*(RAND_MAX+1));
 }
 if(rand()<=probability*(RAND_MAX+1))
 {
 return true;
 }
 return false;
}
long myrandom(long n)// produce 0~n-1 Is equal to the probability of random Numbers between 
{
 t=0;
 if(n<=RAND_MAX)
 {
 long R=RAND_MAX-(RAND_MAX+1)%n;// mantissa 
 t = rand();
 while ( t > r )
 {
  t = rand();
 }
 return t % n;
 }
 else
 {
 long r = n%(RAND_MAX+1);// remainder 
 if( happened( (double)r/n ) )// The probability of getting the remainder 
 {
  return n-r+myrandom(r);
 }
 else
 {
  return rand()+myrandom(n/(RAND_MAX+1))*(RAND_MAX+1);
 }
 }
}
 
 There is another 1 A very simple way to do it is to use it 
random_shuffle( RandomAccessIterator _First, RandomAccessIterator _Last ).
 For example, generate 0 - N-1 I could write it this way 
#include <algorithm>
#include <vector>
long myrandom( long N )
{
 std::vector<long> vl( N ); //  define 1 A size of N the vector
 for ( long i=0; i<N; ++i )
 {
  vl[i] = i;
 }
 std::random_shuffle( vl.begin(), vl.end() );
 return (*vl.begin());
}
random_shuffle  There are 1 a 3 The overloaded version of the parameter 
random_shuffle( RandomAccessIterator _First, RandomAccessIterator _Last, RandomNumberGenerator& _Rand )

The third parameter can accept a custom random number generator to randomize the elements between the first two parameters.
The disadvantage of this method is that if you only need one random number, when N is very large, it consumes a lot of space!


Related articles: