1. 为什么需要自己实现随机数生成器
在C++标准库中，
首先，标准库的随机数生成器虽然功能强大，但对于初学者来说，其复杂的模板结构和抽象接口往往让人望而生畏。自己动手实现一个简单的随机数生成器，可以帮助我们深入理解伪随机数生成的数学原理。
其次，在某些特殊场景下，标准库的随机数生成器可能无法满足需求。比如在嵌入式系统中，我们可能需要一个更轻量级的实现；或者在密码学应用中，可能需要特定的随机数生成算法。了解底层实现原理后，我们可以根据具体需求进行定制。
注意：自己实现的随机数生成器通常不适合用于安全敏感的场景，如密码生成、加密密钥生成等。这些场景应该使用专门设计的加密安全伪随机数生成器(CSPRNG)。
2. 线性同余生成器(LCG)原理剖析
线性同余生成器(Linear Congruential Generator)是最简单也是最古老的伪随机数生成算法之一。它的核心思想是通过一个线性递推公式来生成伪随机数序列：
code复制Xₙ₊₁ = (a × Xₙ + c) mod m
其中：
- Xₙ是当前状态值
- a是乘数(multiplier)
- c是增量(increment)
- m是模数(modulus)
- Xₙ₊₁是下一个状态值
这个算法的质量很大程度上取决于参数a、c、m的选择。不同的选择会导致生成序列的周期长度和统计特性有很大差异。
2.1 参数选择原则
-
模数m：通常选择2的幂次或者一个大的质数。选择2的幂次时，取模运算可以用位与操作(&)来优化。
-
乘数a：应该满足a mod 8 = 5，且a应该接近于m×(1/2-√3/6)≈0.2113×m。
-
增量c：应该是一个奇数，且与m互质。
2.2 经典参数组合
历史上一些著名的LCG实现使用的参数：
-
glibc使用的参数(ANSI C)：
- a = 1103515245
- c = 12345
- m = 2³¹
-
Microsoft Visual C++使用的参数：
- a = 214013
- c = 2531011
- m = 2³¹
这些参数组合都经过了严格的统计测试，可以保证生成的伪随机数序列具有良好的统计特性。
3. 实现一个简单的LCG随机数生成器
下面我们来实现一个简单的LCG随机数生成器类。我们将使用glibc的参数组合，因为它们在大多数平台上表现良好。
3.1 类定义
cpp复制class SimpleLCG {
private:
unsigned long seed; // 当前种子值
public:
// 构造函数，可以指定初始种子
explicit SimpleLCG(unsigned long initialSeed = 1)
: seed(initialSeed) {}
// 设置新的种子
void setSeed(unsigned long newSeed) {
seed = newSeed;
}
// 生成下一个随机数
unsigned long next() {
seed = (seed * 1103515245 + 12345) & 0x7fffffff;
return seed;
}
// 生成[0,1)范围内的随机浮点数
double nextDouble() {
return next() / 2147483648.0;
}
// 生成[min,max]范围内的随机整数
int nextInt(int min, int max) {
return min + (next() % (max - min + 1));
}
};
3.2 实现解析
-
种子管理：我们使用一个成员变量
seed来保存当前状态。构造函数允许指定初始种子，也可以通过setSeed方法随时改变种子。 -
核心算法：
next()方法实现了LCG的核心递推公式。注意我们使用了位与操作& 0x7fffffff来替代取模运算，这相当于对2³¹取模，但效率更高。 -
实用方法：我们提供了
nextDouble()方法来生成[0,1)范围内的随机浮点数，以及nextInt()方法来生成指定范围内的随机整数。
3.3 使用示例
cpp复制#include <iostream>
#include <ioman