伪随机数算法生成高斯分布

伪随机数算法

平方取中法（Middle-square method）是个产生伪随机数的方法，由冯·诺伊曼在1946年提出。

算法：

即

x(i+1)=(10^(-m/2)*x(i)*x(i))mod(10^m)

平方取中法计算较快，但在实际应用时会发现该方法容易产生 周期性明显的数列，而且在某些情况下计算到一定步骤后始终产生相同的数甚至是零，或者产生的数字位数越来越小直至始终产生零。所以用平方取中法产生伪随机 数数列时不能单纯使用公式，应该在计算过程中认为加入更多变化因素，比如根据前一个数的奇偶性进行不同的运算，如果产生的数字位数减少时通过另一种运算使 其恢复成m位。

线性同余法是目前应用广泛的伪随机数生成算法，其基本思想是通过对前一个数进行线性运算并取模从而得到下一个数，递归公式为

X(n+1) = (a * X(n) + c) % m

其中，各系数为：

• 模m, m > 0
• 系数a, 0 < a < m
• 增量c, 0 <= c < m
• 原始值(种子) 0 <= X(0) < m

其中参数c, m, a比较敏感，或者说直接影响了伪随机数产生的质量。
一般而言，m是2的指数次幂(一般2³²或者2⁶⁴)，因为这样取模操作截断最右的32或64位就可以了。多数编译器的库中使用了该理论实现其伪随机数发生器rand()。

线性同余法的周期最大为m，但大部分情况都会少于m。要令线性同余法达到最大周期，应符合以下条件：

从均匀分布得到高斯分布

拒绝采样

The Box–Muller transform

The Box–Muller transform 把一对均匀分布随机数映射到一对标准正态分布随机数。