%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
%%
# 简单随机数生成：rand()
在 C&C++11 之前，通过以下两个 API 生成随机数：
- `void srand(unsigned int seed);`： **初始化随机数种子**
- `int rand(void);` ：**生成 `[0, RAND_MAX]` 之间==均匀分布==的伪随机数**。
- `RAND_MAX` 取决于编译器实现，C++标准保证其至少为 32767。
使用示例：
```cpp
// 使用rand()生成[a, b)区间的随机数.
vector<int> rand_exam(int n, int a, int b) {
srand((unsigned)time(0)); // 设置随机数种子
vector<int> vec;
for (int i = 0; i < n; ++i) {
int val = rand() % (b - a) + a; // 生成[a, b)区间的随机数.
vec.push_back(val);
}
return vec;
}
```
> [!caution] 自 C++11 起，应当使用 `<random>` 头文件中提供的 "**随机数引擎类**" 与 "**随机数分布类**" 来获得更可靠的随机数生成。
> [!info] 计算机中生成的随机数是 "**伪随机数**"——给定种子 `seed`，生成的 "**随机数序列**" 是确定的。
>
> 该序列具有周期性，例如 65535，即即每次利用一个随机种子生成的随机数的周期是65535，随后重复。
#### 简单随机数生成的映射公式
生成**指定区间内均匀分布**的随机数：
| 映射公式 | 随机数区间 |
| --------------------------------- | -------------------- |
| $\text{rand()}$ | `[0, RAND_MAX]` 整数 |
| $\text{rand()}\%n$ | $[0, n)$ 整数 |
| $a+\text{rand()}\%(b-a))$ | $[a,b)$ 整数 |
| $a+\text{rand()}\%(b-a+1))$ | $[a,b]$ 整数 |
| `rand()/(double)RAND_MAX ` | $[0.0,1.0]$ 区间浮点数 |
| `a + (b-a)*rand()/RAND_MAX` | $[a, b]$ 区间浮点数 |
| `a + (b-a)*rand()/(RAND_MAX + 1)` | $[a, b)$ 区间浮点数 <br> |
#### 简单随机数生成存在的问题 🚨
- `rand()%n` 生成的 $[0,n)$ 区间随机整数实际上并不是 "**==均匀分布==**"，因为 **`[0, RAND_MAX]` 中每个数并不一定能均等映射到 `[0, n)`**。
- 例如，`[0, 4]` 映射到区间 `[0, 1]`，实际上是 `0,2,4->0` 与 `1,3->1`。
- `rand()/RAND_MAX` 生成 **`[0, 1]` 范围内随机浮点数**时，由于**随机整数的精度低于随机浮点数**，因此**一部分浮点值永远不会被生成**。
<br><br>
# random 头文件
`<random>` 头文件引入了一组协作类来提供 "**随机数生成**" 支持（since C++11）[^1]：
- （1）**==随机数引擎类==**（random-number engines）：**生成 `unsigned` 随机数序列**
- （2）**==随机数分布类==**（random-number distribution）：基于一个引擎类，生成 **==指定类型==的、==给定范围==内的、==服从特定概率分布==** 的随机数。
- 将**随机数引擎生成的随机数**映射为特定的分布，例如**均匀分布**或**正态分布**。
## 使用说明
- 随机数引擎类：提供调用运算符 `operator()` 来**返回一个==随机 `unsigned` 整数==**（原始随机数）；
- 随机数分布类：提供 "**以随机数引擎 `e` 为参数**" 的调用运算符 `operator()(e)` 来返回**该分布下的随机数**。
使用示例：
```cpp
// 生成[min,max]区间内均匀分布的随机整数.
vector<int> genRandomInt(int n, int min, int max) {
default_random_engine e(time(0));
uniform_int_distribution<> u(min, max);
vector<int> res;
for (int i = 0; i < n; ++i) {
res.push_back(u(e));
}
return res;
}
// 生成[min, max]区间内均匀分布的随机浮点数
vector<double> genRandomReal(int n, double min = 0.0, double max = 1.0) {
default_random_engine e(time(0));
uniform_real_distribution<> u(min, max);
vector<double> res;
for (int i = 0; i < n; ++i) {
res.push_back(u(e));
}
return res;
}
// 生成正太分布的随机数
void getNormalReal() {
double mean = 4, stde = 1.5;
default_random_engine e(time(0));
normal_distribution<> norm(mean, stde); // 生成均值4, 标准差1.5的正态分布.
vector<unsigned> bucket(9); // 舍入到整数, 若位于[0, 8]区间, 则统计入桶中.
for (int i = 0; i < 200; ++i) {
unsigned v = lround(norm(e)); // 舍入到最接近的整数
if (v < bucket.size()) {
++bucket[v];
}
}
for (int i = 0; i != bucket.size(); ++i) {
cout << i << ": " << string(bucket[i], '*') << endl;
}
}
int main() {
auto vec_int = genRandomInt(10, 0, 10);
auto vec_double = genRandomReal(10, 0.0, 1.0);
auto print = [](auto& vec) {
for_each(vec.begin(), vec.end(), [](auto& val) {
cout << val << " ";
});
cout << endl;
};
print(vec_int);
print(vec_double);
getNormalReal();
}
```
<br>
## 随机数引擎类
随机数引擎类是 "**函数对象**"，提供了调用运算符 `()` 来**返回一个==随机 `unsigned` 整数==**。
随机数引擎 `e` 生成的 **`unsigned` 整数范围取决于==编译器实现==**，可由引擎类对象的 `e.min()` 与 `e.max()` 成员函数获取。
随机数引擎支持的操作：
![[_attachment/02-开发笔记/01-cpp/库使用/cpp-随机数.assets/IMG-cpp-随机数-C46D0E2ACA6A8EA23F199B31DE5C6156.png|700]]
标准库提供了**三个引擎类**（采用不同算法生成随机数）以及 **三个适配器**，均为**模版**，参见 [^2]。
同时，为这些引擎或适配器提供了 "**==完全特例化==**" 的版本：
| 引擎类（模版） | 说明 | 完全特例化的类 |
| ------------------------------ | ---------------- | ----------------------------------------- |
| `linear_congruential_engine<>` | 采用 "**线性同余法**" | `std::minstd_rand`，`std::minstd_rand0` |
| `mersenne_twister_engine<>` | 采用 "**梅森旋转算法**" | `std::mt19937`、`std::mt19937_64` |
| `subtract_with_carry_engine<>` | 采用 "**借位减法生成器**" | `std::ranlux24_base`、`std::ranlux48_base` |
> [!info] `default_random_engine` 是**某个具体引擎类型的==别名==**，视为**默认引擎**，适用于大多数情况。
```cpp
int main() {
// 默认随机数引擎
default_random_engine e;
// `e()`返回一个无符号随机整数, 范围在`[e.min(), e.max()]`内.
for (int i = 0; i < 10; ++i) {
cout << e() << endl;
}
// [1, 2147483646]
cout << "[" << e.min() << ", " << e.max() << "]" << endl;
}
```
## 随机数分布类
随机数分布类用以将 "**随机数引擎生成的随机数**" 转换到**特定分布**。
除伯努利分布外，其他分布类型均为 "**模版**"，均接受 **==单个类型参数==**，指出分布生成的结果类型。
标准库提供了 20 种的**随机数分布类** 参见[^3]，包括：
- **均匀分布**
- `std::uniform_int_distribution<IntT> u(m, n)`：生成在 `[m, n]` 区间均匀分布的**整数**（`m` 默认为 0，`n`默认为`IntT` 类型可表示的最大值）。
- `std::uniform_real_distribution<RealT> u(x, y)`：生成在 `[x, y]` 区间均匀分布的**浮点数**（`x` 默认为`0.0` ，`y` 默认 `1.0`）。
- **伯努利分布**
- `std::bernoulli_distribution<IntT> g(p)`：**以给定概率 `p` 生成 `true`**（`p` 默认为`0.5`）。
- **正态分布**
- `std::normal_distribution<RealT> n(m, s)`：生成均值为 `m`，标准差为 `s` 的**正态分布浮点数**。
- **泊松分布**
- **抽样分布**
> [!info] 各个随机数分布类模版可接受的 "模版类型参数" 不同
> - `IntT` 表示只接受整型模版参数（除 `bool` 和 `char` 系列），默认模版参数是 `int` 类型。
> - `RealT` 表示只接受浮点类型，例如 `float`，`double`，`long double`，默认模版参数是 `double` 类型。
>
随机数分布类支持的操作：
![[_attachment/02-开发笔记/01-cpp/库使用/cpp-随机数.assets/IMG-cpp-随机数-67B8857B55FD1A241039F29056A0987D.png|780]]
## 随机数设备
标准库提供了一个类 `std::random_device`，用于代表一个 "**真正的随机数生成设备**"（指可用的硬件设备）。
- 当 **"非确定性源" 设备**可用时，**从该设备处获取随机值**。
- 若不可用，根据实现定义的**伪随机数引擎**来提供 `std::random_device`。该情况下，每个 `std::random_device` 对象将**生成相同的数字序列**。
> [!info] `std::random_device` 的实现
>
> Accoding to the libc++ source code for implementation of `std::random_device`, it's just a thin wrapper over `std::fopen("/dev/urandom")`。
> [!caution] `std::random_device` 通常只**用于为随机数引擎提供一个==随机 seed==**, 而不是直接用于生成随机数.
>
> 原因说明： "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".
使用示例：
```cpp
// 若设备可用，从一个真实的随机数生成设备上获得一个真正的随机数. 否则, 得到一个伪随机数.
// rd通常只用来为其它随机数生成器提供一个随机seed
std::random_device rd;
std::default_random_engine gen(rd());
std::uniform_real_distribution<> dis; // [0, 1] 均匀分布浮点数.
double random_gen_0_1_real() {
return dis(gen); // 使用`dis`将`gen`生成的unsigned int转换到[0, 1]之间的浮点数均匀分布中.
}
```
<br><br>
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
# ♾️参考资料
- [用C++的random库生成更好的随机数\_c++ random-CSDN博客](https://blog.csdn.net/henry_23/article/details/113623544)
# Footnotes
[^1]: 《C++ Primer》P660，17.4 节
[^2]: 《C++ Primer》P783，附录 A.3.2 随机数引擎
[^3]: 《C++ Primer》P781，附录 A.3.1 随机数分布