Cloud_Player's Notes
0%

C++ 产生伪随机数的一些参考

发表于 更新于
本文字数： 8.2k 阅读时长 ≈ 7 分钟

我不生产代码，我只是代码的搬运工；
我也不生产文档，只是想替官方文档宣传宣传；
其实我也不写博客，只是拿别人的博客修修改改。

C 库伪随机数发生器

定义于头文件 <cstdlib>
rand 生成伪随机数(函数)
srand 初始化伪随机数生成器(函数)
RAND_MAX std::rand 生成的最大可能值(宏常量)

rand() 函数无参数，其返回值为 ​0​ 与 RAND_MAX （包含 0 与 RAND_MAX ）的随机整数值，保证 RAND_MAX 至少为 32767，rand() 函数内部实现是用线性同余法做的，它不是真的随机数，因其周期特别长，故在一定的范围里可看成是随机的。rand() 每次执行时是相同的；若要不同，需要用函数 srand() 初始化它。srand() 函数用来设置 rand() 产生随机数时的随机数种子，参数 seed 必须是个整数，未设定随机数种子时，系统默认的随机数种子为 1。

产生随机数的用法

  1. 给 srand() 提供一个 unsigned int 类型的种子；

  2. 调用 rand()，它会根据提供给 srand() 的种子值返回一个随机数(在 0 到 RAND_MAX 之间)；

  3. 根据需要多次调用 rand()，从而不间断地得到新的随机数；

  4. 无论什么时候，都可以给 srand() 提供一个新的种子，从而进一步“随机化” rand() 的输出结果。

0~RAND_MAX之间的随机数程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

int main() {
	unsigned int seed = time(NULL);
	// time_t 向 unsigned int 作类型转换
	// time(NULL) 也可作 time(0) 或 time(nullptr)
	srand(seed);
	// 使用当前时钟作为随机数种子每一次运行程序可产生不同的随机数种子			 	
	for (int i = 0; i < 10; i++)
	{
		cout << rand() << endl;
	}
	return 0;
}

产生一定范围随机数的通用表示公式

要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。

其实现函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int RandomRangeLeftCloseRightOpen(int a, int b)
{
	return (rand() % (b - a)) + a;
}

int RandomRangeLeftCloseRightClose(int a, int b)
{
	return (rand() % (b - a + 1)) + a;
}

int RandomRangeLeftOpenRightClose(int a, int b)
{
	return (rand() % (b - a)) + a + 1;
}

int RandomIntNum(int a, int b)
{
	return a + (int)b * rand() / (RAND_MAX + 1);
}

double RandomZeroToOne()
{
	return rand() / double(RAND_MAX);
}

C++ 随机数库

在 C++11 中引入了 <random> 头文件，功能更完善，可以得到更精确和的随机数，能够更好地解决相关领域问题。这个标准库分为两大部分，分别是：

  • 生成器：定义了用来产生均匀分布的伪随机数的机制，也称为随机数引擎。
  • 分布：以生成器得到的均匀分布的随机数序列转换为某种特定数学概率分布的序列，如均匀分布、正态分布、泊松分布等。

生成器

random_device

std::random_device 是生成非确定随机数的均匀分布整数随机数生成器，是所有生成器中唯一不需要随机数种子的生成方式。在 Linux 的实现中，是读取 /dev/urandom 设备；在 Windows 的实现中是调用 rand_s。这种生成器基于随机过程来产生均匀分布的随机数序列，可以视为一个真随机数。
random_device 在某些系统中可无法使用，会在构造函数或者调用 operator() 函数时抛出异常，因此对于移植性而言需要格外注意。

成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
class random_device;
// 成员函数

/***** 构造 *****/
// (构造函数) 构造引擎

/***** 生成 *****/
// operator() 推进引擎状态并返回生成的值，即均匀分布于 [min(), max()] 的随机数

/***** 特征 *****/
// entropy 获得非确定随机数生成器的熵估计(公开成员函数)
// min[静态] 获取输出范围中的最小可能值(公开静态成员函数)
// max[静态] 获取输出范围中的最大可能值(公开静态成员函数)

示例

1
2
3
4
5
6
7
8
9
10
#include <random>
#include <iostream>
int main()
{
    std::random_device rd;
    std::cout << rd.min() << '\t' << rd.max() << std::endl;
    std::cout << rd() << '\t' << rd.entropy() << std::endl;
    std::cout << rd() << '\t' << rd.entropy() << std::endl;
    return 0;
}

可能的结果

确定的随机数生成器（例如伪随机数生成器）拥有零熵，之所以此处 rd.entropy() 的值不为 0 ，是因为此函数在一些标准库中未完全实现。例如，版本 12 前的 LLVM libc++ 始终返回零，即使设备是非确定的（对于 libstdc++ ，见 bug 67578 ）。与之相比， Microsoft Visual C++ 实现始终返回 32 ，且 boost.random 返回 10 。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <string>
#include <map>
#include <random>

int main()
{
    std::random_device rd;
    std::map<int, int> hist;
    std::uniform_int_distribution<int> dist(0, 9);
    for (int n = 0; n < 20000; ++n) {
        ++hist[dist(rd)]; // note: demo only: the performance of many 
                          // implementations of random_device degrades sharply
                          // once the entropy pool is exhausted. For practical use
                          // random_device is generally only used to seed 
                          // a PRNG such as mt19937

                          // 注意：仅用于演示：一旦熵池耗尽，
                          // 许多 random_device 实现的性能就急剧下滑
                          // 对于实践使用， random_device 通常仅用于
                          // 播种类似 mt19937 的伪随机数生成器
    }
    for (auto p : hist) {
        std::cout << p.first << " : " << std::string(p.second/100, '*') << '\n';
    }
}

可能的结果

其他

随机数引擎

1
2
3
linear_congruential_engine  //实现线性同余算法(类模板)
mersenne_twister_engine     //实现梅森缠绕器算法(类模板)
subtract_with_carry_engine  //实现带进位减（一种延迟斐波那契）算法(类模板)

随机数引擎适配器

1
2
3
discard_block_engine        //舍弃随机数引擎的某些输出(类模板)
independent_bits_engine     //将一个随机数引擎的输出打包为指定位数的块(类模板)
shuffle_order_engine        //以不同顺序发送一个随机数引擎的输出(类模板)

预定义随机数生成器

1
2
3
4
5
6
7
8
9
10
minstd_rand0
minstd_rand
mt19937
mt19937_64
ranlux24_base
ranlux48_base
ranlux24
ranlux48
knuth_b
default_random_engine

所有生成器引擎都提供如下接口供使用

  • min：返回最小值，静态函数
  • max：返回最大值，静态函数
  • seed：设置随机数生成的种子
  • operator()：产生随机数
  • void discard (unsigned long long z)：调用z次operator()函数

另外，都定义了输入输出操作符和关系运算的非成员函数。
随机数引擎接收一个整数作为种子，不提供就会使用默认值。一般可以使用 chrono 库中的时间或者 random_device 生成一个随机数作为种子。

1
2
3
4
5
6
7
using clock = std::chrono::high_resolution_clock;
clock::time_point begin = clock::now();

auto seed = begin.time_since_epoch().count();
std::minstd_rand0 rand_gen(seed);

cout << rand_gen() << endl;

分布

通过强大的生成器引擎得到了均匀分布的随机数之后，为了满足特定场景的需求，random提供的分布可以以生成器为输入，得到满足不同分布的随机数序列，广义上看，可以认为是对生成器的进一步修饰和包装。主要有三个作用：

  • 利用模版参数，改变生成值的类型
  • 利用构造函数参数，改变生成值的区间范围
  • 选择不同的分布得到满足不同分布的随机数序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
//均匀分布
uniform_int_distribution        //产生在一个范围上均匀分布的整数值。(类模板)
uniform_real_distribution       //产生在一个范围上均匀分布的实数值。(类模板)

//伯努利分布
bernoulli_distribution          //产生伯努利分布上的 bool 值。(类)
binomial_distribution           //产生二项分布上的整数值。(类模板)
negative_binomial_distribution  //产生负二项分布上的整数值。(类模板)
geometric_distribution          //产生几何分布上的整数值。(类模板)

//泊松分布
poisson_distribution            //产生泊松分布上的整数值。(类模板)
exponential_distribution        //产生指数分布上的实数值。(类模板)
gamma_distribution              //产生 Γ 分布上的实数值。(类模板)
weibull_distribution            //产生威布尔分布上的实数值。(类模板)
extreme_value_distribution      //产生极值分布上的实数值。(类模板)

//正态分布
normal_distribution             //产生标准正态（高斯）分布上的实数值。(类模板)
lognormal_distribution          //产生对数正态分布上的实数值。(类模板)
chi_squared_distribution        //产生 χ2 分布上的实数值。(类模板)
cauchy_distribution             //产生柯西分布上的实数值。(类模板)
fisher_f_distribution           //产生费舍尔 F 分布上的实数值。(类模板)
student_t_distribution          //产生学生 t 分布上的实数值。(类模板)

//采样分布
discrete_distribution           //产生离散分布上的随机整数。(类模板)
piecewise_constant_distribution //产生分布在常子区间上的实数值。(类模板)
piecewise_linear_distribution   //产生分布在定义的子区间上的实数值。(类模板)

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
#include <cmath>
 
int main()
{
    // 以随机值播种，若可能
    std::random_device r;
 
    // 选择 1 与 6 间的随机数
    std::default_random_engine e1(r());
    std::uniform_int_distribution<int> uniform_dist(1, 6);
    int mean = uniform_dist(e1);
    std::cout << "Randomly-chosen mean: " << mean << '\n';
 
    // 生成围绕平均值的正态分布
    std::seed_seq seed2{r(), r(), r(), r(), r(), r(), r(), r()}; 
    std::mt19937 e2(seed2);
    std::normal_distribution<> normal_dist(mean, 2);
 
    std::map<int, int> hist;
    for (int n = 0; n < 10000; ++n) {
        ++hist[std::round(normal_dist(e2))];
    }
    std::cout << "Normal distribution around " << mean << ":\n";
    for (auto p : hist) {
        std::cout << std::fixed << std::setprecision(1) << std::setw(2)
                  << p.first << ' ' << std::string(p.second/200, '*') << '\n';
    }
}

Random 类的写法参考

Random.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <random>
#include "Math.h"

class Random
{
public:
	static void Init();

	// Seed the generator with the specified int
	// NOTE: You should generally not need to manually use this
	static void Seed(unsigned int seed);

	// Get a float between 0.0f and 1.0f
	static float GetFloat();

	// Get a float from the specified range
	static float GetFloatRange(float min, float max);

	// Get an int from the specified range
	static int GetIntRange(int min, int max);

	// Get a random vector given the min/max bounds
	static Math::Vector2 GetVector(const Math::Vector2& min, const Math::Vector2& max);
	static Math::Vector3 GetVector(const Math::Vector3& min, const Math::Vector3& max);
private:
	static std::mt19937 sGenerator;
	/*
	mt19937是c++11中加入的新特性
	它是一种随机数算法，用法与rand()函数类似
	但是具有速度快，周期长的特点(它的名字便来自周期长度：2^19937-1)
	*/
};

Random.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include "Random.h"

void Random::Init()
{
	std::random_device rd;
	Random::Seed(rd());
}

void Random::Seed(unsigned int seed)
{
	sGenerator.seed(seed);
}

float Random::GetFloat()
{
	return GetFloatRange(0.0f, 1.0f);
}

float Random::GetFloatRange(float min, float max)
{
	std::uniform_real_distribution<float> dist(min, max);
	return dist(sGenerator);
}

int Random::GetIntRange(int min, int max)
{
	std::uniform_int_distribution<int> dist(min, max);
	return dist(sGenerator);
}

Math::Vector2 Random::GetVector(const Math::Vector2& min, const Math::Vector2& max)
{
	Math::Vector2 r = Math::Vector2(GetFloat(), GetFloat());
	return min + (max - min) * r;
}

Math::Vector3 Random::GetVector(const Math::Vector3& min, const Math::Vector3& max)
{
	Math::Vector3 r = Math::Vector3(GetFloat(), GetFloat(), GetFloat());
	return min + (max - min) * r;
}

std::mt19937 Random::sGenerator;

参考文献

[1] C++ rand,srand用法 / playbar

[2] C++标准库——random / OshynSong

[3] C++11带来的随机数生成器 / egmkang

[4] Pseudo-random number generation / C++ reference