Summary of random number learning

random number

​ Before the emergence of new standards ,C and C++ All rely on a simple C Library function rand To generate random numbers .

and rand Function bounds ： stay stdlib.h There are macros in the header file **#define RAND_MAX 0x7fff**, namely rand Produce a 0~0x7fff Uniformly distributed pseudo-random integers , The range of each random number is 0 The maximum value associated with a system ( At least for 32767) Before

rand Function call ：

• rand() Before each call of a function, you will query whether it has been called srand(seed), Whether to seed Set a value , If so, it will automatically call srand(seed) One time to initialize its starting value
• If not previously called srand(seed), Then the system will automatically give seed Initial value of Fu , namely srand(1) Automatically call it once

however rand Function has some problems ： Even if not most , There are also many programs that require different ranges of random numbers

** notes ：**C++ Programs should not use library functions rand, Instead, use default_random_engine Classes and appropriately distributed class objects

It's defined in The header file random The random library solves these problems through a set of cooperative classes ： Random number engine class (random-number engines) and Random number distribution class (random-number distribution)

Composition of random number library ：

• engine — type , Generate random unsigned Sequence of integers
• Distribution — type , Use the engine to return random numbers that obey a specific probability distribution

Random number engine and distribution

​ The random number engine is a function object class , They define a call operator , This operator takes no arguments and returns a random value unsigned Integers .

​ You can generate the original random number by calling a random number engine object ：

#include<iostream>
#include<vector>
#include<random>
using namespace std;

int main()
{
	default_random_engine e;	//  Generate random unsigned number 
	for(size_t i=0;i<10;i++)
		// e()" call " Object to generate the next random number 
		cout<<e()<<ends;
	return 0; 
}

The standard library defines several random number engine classes , The difference is the quality of performance and randomness . Each compiler specifies one of the default_random_engine type . This type generally has the most common features .

Random number engine operation ：

operation	explain
Engine e;	Default constructor ; Use the default seed for this engine type
Engine e(s);	Use integer values s As a seed
e.seed(s)	Using seeds s Reset the state of the engine
e.min()	The minimum value that this engine can generate
e.max()	The maximum value that this engine can generate
Engine::result_type	Generated by this engine unsigned Integer type
e.discard(u)	Propel the engine n Step ;u The type of unsigned long long

Distribution types and engines

​ In order to get a number within a specified range , We use a distribution type object ：

#include<iostream>
#include<vector>
#include<random>
using namespace std;

int main()
{
	//  Generate 0 To 9 Before ( contain ) Uniformly distributed random numbers 
	uniform_int_distribution<unsigned> u(0,9);
	default_random_engine e; //  Generate unsigned random integers 
	for(size_t i=0;i<10;i++)
		//  take u As a random number source 
		//  Each call returns values that are within a specified range and are uniformly distributed 
		cout<<u(e)<<ends;
	cout<<endl<<"min："<<e.min()<<ends<<"max："<<e.max()<<endl;
	return 0;
}

In this program ,u(0,9) We hope to get 0 To 9 Before ( contain ) Number of numbers . The random number distribution class uses the included range , Thus we can get every possible value of a given integer type

The scope of an engine type can be defined by calling the min and max Members to get

Similar engine types , The distribution type is also a function object class . The distribution type defines a call operator , It takes a random number engine as a parameter . The distribution object uses its engine parameters to generate random numbers , And map it to the specified distribution .

** notes ：** When we say random number generator , It refers to the combination of distribution objects and engine objects

The engine generates a sequence of values

Conclusion ： ** A given random number generator will always generate the same sequence of random numbers . If a random number defines a local random number generator , It should be ( Including engines and distribution objects ) Defined as static** Of . otherwise , Each call to the function will generate the same sequence

Example ： Suppose you need a function to generate a vector, It includes 100 One is evenly distributed in 0 To 9 Random number between .

Wrong form ：

//  Almost certainly generate random integers vector Error method of 
//  Every time this function is called, the same 100 Number 
vector<unsigned> bad_randVec() {
    default_random_engine e;
    uniform_int_distribution<unsigned> u(0,9);
    vector<unsigned> ret;
    for(size_t i=0;i<100;i++)
        ret.push_back(u(e));
   	return ret;
}
//  Every time this function is called, it will return the same vector

The right form ：

//  Return to one vector, contain 100 A uniformly distributed random number 
vector<unsigned> good_randVec() {
    //  Because we want the engine and distribution objects to remain in state , So they should be 
    //  Defined as static Of , So that each call generates a new number 
    static default_random_engine e;
    static uniform_int_distribution<unsigned> u(0,9);
    vector<unsigned> ret;
    for(size_t i=0;i<100;i++)
        ret.push_back(u(e));
   	return ret;
}

Set the seed of random number generator

​ This feature is useful in generating random numbers . however , Once our program is debugged , We usually want to generate different random results every time we run the program , By providing a seeds (seed) To achieve this goal . A seed is a number , It can be used to regenerate a new position in the sequence .

There are two ways for the engine to seed ：

1. Provide seeds when creating engine objects
2. Call engine seed member

default_random_engine e1;	//  Use default seed 
default_random_engine e2(505);	//  Use the given seed value 
default_random_engine e3;	//  Use default seed 
e3.seed(505);	//  call seed Set a new seed value 

​ Choose a good seed , Like most other things that good random numbers involve , Is extremely difficult . Perhaps the most common method is to call system functions time.

time Functions are defined in the header file ctime in , It returns the number of seconds elapsed from a specific time to the current time . function time Receive a single pointer parameter , It points to the data structure used to write the time . If the time is empty , Then the function simply returns time ：

default_random_engine e(time(0));	//  A slightly random seed 

because time Returns the time in seconds , Therefore, this method is only applicable to applications where the seed generation interval is seconds or longer

** notes ：** If the program runs repeatedly as part of an automatic process , take time The method of using the return value of as a seed is invalid ; It may use the same seed many times

Other random number distributions

​ The random number engine generates unsigned Count , Every number in the range has the same probability of being generated . Applications often require random numbers of different types or distributions . The standard library meets these two requirements by defining different random number distribution objects , Distributed objects and engine objects work together , Generate the required results .

Generate random real numbers

​ Programs often need a random floating point number , In especial 0 To 1 Random number between . Use new standard library facilities , You can easily obtain random floating-point numbers .

For example, we can define a uniform_real_distribution Object of type , And let the standard library handle the mapping from random integers to random floating-point numbers .

#include<iostream>
#include<vector>
#include<random>
using namespace std;

int main()
{
	default_random_engine e; //  Generate unsigned random integers 
	// 0 To 1( contain ) Uniform distribution of 
	uniform_real_distribution<double> u(0,1);
	for(size_t i=0;i<10;i++)
		cout<<u(e)<<ends;
	return 0; 
}

Operation of distribution type ：

operation	explain
Dist d;	Default constructor ; send d Ready to be used ; Other constructors depend on Dist The type of ; The constructor of the distribution type is explicit Of
d(e)	With the same e Continuous call d Words , Will be based on d The distributed type of generates a random number sequence ;e Is a random number engine
d.min()	return d(e) The minimum value that can be generated
d.max()	return d(e) The maximum value that can be generated
d.reset()	The reconstruction d The state of , So that subsequent d The use of does not depend on d Generated value

Use the default result type of the distribution

​ All distribution types are templates , With a single template type parameter , Indicates the type of random number generated by the distribution

​ Each distribution template has a default template argument . The distribution type for generating floating-point values is generated by default double value , By default, the distribution of integer values is generated int value .

​ Because the distribution type has only one template parameter , So when we want to use the default random number type, remember to use empty angle brackets after the template

//  empty <> Indicates that we want to use the default result type 
uniform_real_distribution<> u(0,1);	//  Default generation double value 

Generate non uniformly distributed random numbers

​ In addition to correctly generating numbers within the specified range , Another advantage of the new standard library is that it can generate non uniformly distributed random numbers . Normal distribution normal_distribution class

#include<iostream>
#include<vector>
#include<random>
#include<cmath>
using namespace std;

int main()
{
	default_random_engine e;	//  Generate random integer  
	normal_distribution<> n(4,1.5);	//  mean value 4, Standard deviation 1.5
	vector<unsigned> vals(9);	// 9 All elements are 0
	for(size_t i=0;i!=200;i++) {
		unsigned v = lround(n(e));	//  Round to the nearest whole number 
		if(v<vals.size()) 
			++vals[v];	//  Count how many times each number appears  
	} 
	for(int i=0;i!=vals.size();i++) {
		cout<<i<<"："<<string(vals[i],'*')<<endl;
	} 
	return 0;
}

​

** notes ：** Because the engine returns the same sequence of random numbers , So we have to declare the engine object outside the loop . otherwise , Each step of the loop creates a new engine , Thus, each step of the loop will generate the same value . Allied , Distribution objects should also be kept in a state , Therefore, it should also be defined outside the loop

Other random number distributions

Uniform distribution ：

uniform_int_distribution<IntT> u(m,n);
uniform_real_distribution<RealT> u(x,y);

Generate the specified type of , Values within a given inclusion range .

m（ or x） Is the minimum value that can be returned ;n（ or y） Is the maximum value. .m The default is 0;n The default is type IntT The maximum value that an object can represent .x The default is 0.0,y The default is 1.0

Bernoulli distribution ：

bernoulli_distribution b(p);

At a given probability p Generate true;p The default value is 0.5

Poisson distribution ：

poisson_distribution<IntT> p(x);

The mean for double value x The distribution of

Normal distribution ：

normal_distribution<RealT> n(m,s);

The mean for m, The standard deviation is s;m The default value is 0.0,s The default value is 1.0;