1. 线性同余法（LCG）是什么？
线性同余法（LCG，Linear Congruential Generator） 是一种最简单、最常见的伪随机数生成算法。它使用一个递推公式，通过线性变换生成一系列的伪随机数。
LCG 的特点：
- 计算简单，适合快速生成伪随机数
- 适用于硬件和软件环境
- 生成的随机数序列具有周期性（如果参数选择不当，周期可能较短）
2. LCG 的数学公式
LCG 通过以下递推公式生成随机数：
3. 线性同余法的示例
(1) C++ 实现 LCG
#include <iostream>class LCG {
private:uint64_t state; // 当前随机数const uint64_t a = 1664525; // 乘数const uint64_t c = 1013904223; // 增量const uint64_t m = 1ULL << 32; // 2^32, 典型的取值public:LCG(uint64_t seed) : state(seed) {}// 生成下一个随机数uint32_t next() {state = (a * state + c) % m;return (uint32_t)state; }// 生成[0,1)范围的浮点数double nextDouble() {return (double)next() / m;}
};int main() {LCG rng(12345); // 以 12345 作为种子for (int i = 0; i < 10; i++) {std::cout << rng.next() << std::endl;}return 0;
}
输出示例：
3346282858
2428863037
2433242068
...
（数值会根据种子不同而不同）
（2）opencv的实现
state = (uint64)(unsigned)state* /*CV_RNG_COEFF*/ 4164903690U + (unsigned)(state >> 32);state：这是RNG类的一个成员变量，用于保存随机数生成器的当前状态。它是一个 64 位无符号整数（uint64类型）。(uint64)(unsigned)state：首先将state强制转换为unsigned类型（通常是 32 位无符号整数），然后再将其转换为uint64类型。这样做的目的是只取state的低 32 位进行后续计算。4164903690U：这是一个无符号整数常量，可能是作为随机数生成算法中的一个系数（注释中的CV_RNG_COEFF也暗示了这一点）。通过将state的低 32 位乘以这个系数，可以改变state的值，从而引入随机性。(unsigned)(state >> 32)：将state右移 32 位，即取state的高 32 位，然后将其转换为unsigned类型。这一步操作可以将state的高 32 位与低 32 位经过系数乘法后的结果相加。- 最后将计算结果赋值给
state，更新随机数生成器的状态。
在这段代码中：
X_n相当于state的当前值。a相当于系数4164903690U。c相当于(unsigned)(state >> 32)。m是uint64类型的最大值，因为state是uint64类型，计算结果会自动进行模运算（溢出处理）。
通过不断更新 state 的值，并返回其低 32 位作为随机数，就可以生成一系列看似随机的无符号整数。但需要注意的是，LCG 生成的随机数是伪随机的，即它们是通过确定性的算法生成的，在特定条件下可能会出现重复的序列。
4. 线性同余法的周期性
5. 常见的参数选择
为了保证长周期和较好的随机性，不同系统有推荐的参数：
OpenCV RNG 采用的是 Numerical Recipes 参数：
state = (1664525 * state + 1013904223) % (1ULL << 32);
6. LCG 的优缺点
✅ 优点
- 计算简单（只用加法、乘法和取模）
- 速度快
- 适用于硬件实现
❌ 缺点
- 随机性较差，不适合密码学
- 低维分布性不好（会在高维空间形成结构）
- 周期有限（如果参数选择不好，可能周期很短）
7. 更好的随机数生成方法
尽管 LCG 计算简单，但如果需要更高质量的随机数，推荐：
- Xorshift：更快，适用于高效随机数生成
- PCG（Permuted Congruential Generator）：高质量 + 低计算量
- Crypto-safe PRNGs（如 ChaCha20）：适用于密码学
8. 总结
- 线性同余法（LCG）是一种简单、快速的伪随机数生成算法，使用递推公式生成数列。
- LCG 的随机性取决于参数（a,c,m），OpenCV 采用的是
Numerical Recipes的参数。 - 适用于简单随机数需求，但不适用于高精度或安全性要求高的场景。
- 现代高质量随机数生成器如 Mersenne Twister, Xorshift, PCG 逐渐取代了 LCG。
➡ 结论：LCG 适用于一般场景，但更好的随机数生成方法可用于更高级应用！
