Park-Miller LCG：伪随机数生成器的原理与优化

1. Park-Miller LCG：伪随机数生成器的经典实现

在计算机科学领域，伪随机数生成器(PRNG)是许多应用的基础组件。Park-Miller线性同余生成器(LCG)因其简洁性和良好的统计特性，成为最广泛使用的算法之一。这个算法由Stephen K. Park和Keith W. Miller在1988年提出，作为"最小标准"随机数生成器被广泛采用。

1.1 LCG算法原理

线性同余生成器的基本公式为：
Xₙ₊₁ = (a × Xₙ + c) mod m

Park-Miller变体是一种特殊的LCG，其中c=0，因此被称为"乘性同余生成器"(MCG)。其递推公式简化为：
Xₙ₊₁ = a × Xₙ mod m

这种简化带来了几个优势：周期长度可能达到m-1（当m是素数且a是模m的原根时），且实现更高效。Park和Miller推荐的参数是：

• 模数m = 2³¹ - 1 = 2147483647（梅森素数M31）
• 乘数a = 16807（模M31的原根）

注意：后来发现a=48271具有更好的统计特性，成为新的"最小标准"推荐值。C++11的minstd_rand0使用16807，而minstd_rand使用48271。

1.2 算法特性分析

Park-Miller LCG具有几个关键特性：

1. 周期长度：2³¹-2 ≈ 21亿，对许多应用足够
2. 计算高效：仅需一次乘法和一次模运算
3. 可移植性：在所有平台上产生相同序列
4. 统计特性：通过大多数随机性测试

然而它也有局限性：

• 低位随机性较差（LCG的通病）
• 高维空间中点分布不均匀
• 预测下一个数容易（安全性低）

2. 实现细节与优化技巧

2.1 基础实现方法

最直接的C语言实现如下：

c复制uint32_t park_miller(uint32_t *state) {
    const uint64_t m = 2147483647;
    const uint64_t a = 48271;
    uint64_t product = (uint64_t)*state * a;
    *state = product % m;
    return *state;
}

这种方法简单但效率不高，因为6