[科普中国]-伪随机数发生器

概述

通过程序得到的随机数无论什么算法都一定是通过递推公式得到的序列，这本身就违反了随机的定义，所以它们都不是真正的随机数。伪随机数中一个很重要的概念就是“种子”，种子决定了随机数的固定序列，例如在C语言rand函数得到的序列每次都是相同的，如果想得到不同序列需要调用srand设置种子；同理在Java中new Random(1)的构造函数参数来设置种子1。

方法取中法i：平方取中法：

这个方法是由冯·诺伊曼在1946年提出的，思想很简单：

选择一个m位数Ni作为种子，做平方运算（记为Ni+ 1 = （Ni * Ni）...)，结果若不足2m个位，在前补0。在这个数选中间m个位的数作为Ni+1。这个算法明显又很大弊端，不仅周期短而且分布不均匀，比如10000平方取中结果就一直为00000了。

ii：常数取中法：

此方法与平方取中法稍有不同，只是把一个随机数的平方换成了随机数与常数的乘积（记为Ni+1 = （K * Ni）...)，对于随机分布等没有什么提升。

iii：乘法取中法：

此方法是对平方取中法的一定优化，公式记为Ni+1 = （Ni * Ni-1）...

同余法同余是啥不知道的同学见我《素性测试》中的wilson检测中有解释

同余法是大部分变成语言的RNG所采用的算法，线性同余方程为：Ni+1 = a Ni + C （mod m），其中a为乘子，C为增量，m为膜。产生的随机序列Rn = Ni / m。

当 a = 1 并且 C != 0时，此同余法称为加法同余法

当a != 1 并且 C = 0时，此同余法称为乘法同余法

当a != 1 并且 C != 0时，此同余法称为混合同余法

同余法当m越大，Ni的范围也就越大，随机分布的也就越均匀，Rn也就分布的更均匀，所以m取值应尽可能的大，充分利用计算机字长。对于如何获得满周期随机数是存在判定定理的，当且仅当满足下列条件时，践行同余法是满周期的：

1.C与m互质

2.对于m的每一个质因子p，（a-1）为p的倍数

3.若m可被4整除， (a-1)也可被4整除。

除此之外还有二次同余，三次同余等，原理差不多。

移位法由于计算机特有的逻辑移位运算，可以对种子N0左移n位得到M1，右移n位得到M2，将M1与M2做逻辑相加运算得到随机数N1，

公式为Ni+1 = Ni >> n + Ni