伪随机数算法(一)
伪随机数概念在我大学一年级接触C语言基础的时候就听说过，并熟练掌握C语言中rand()函数的使用方法。不过，当时我对伪随机数的认识基本也就停留在百度百科那种小白水平，最多就知道老师说我们用的随机数是假的，是通过某种算法实现的。最近学习计算物理学讲到Monte Carlo方法时，通过课本和互联网才算真正意义上理解了什么是伪随机数。借此文好好总结一下吧！
一、随机数的分类
在计算物理学中，随机数被准确地分成了三类：真随机数、准随机数、伪随机数。那么这三种的区别是什么呢？拷贝一段书上的定义（我觉得写的挺好的⊙﹏⊙，其实是懒得想别的表述方式）：
1）真随机数：产生的数不可预计，也不可能重复产生两个相同的真随机数序列。真随机数只能通过某些随机的物理过程来产生，如放射性衰变、电子设备的热噪声等。
2）准随机数：其随机数序列不具备随机性质，仅仅是用它来处理问题能够得到正确的结果。（老实说，准随机数我目前也没准确理解，读者有好的例子请@我）
3）伪随机数：通过某种数学公式或者算法产生的数值序列。虽然在数学意义上伪随机数是不随机的，但是如果能够通过统计检验，可以当成真随机数使用。
二、伪随机数算法
伪随机数产生的方法有个逼格挺高的名字---伪随机数发生器。伪随机数产生器中最最最基础的思想是均匀分布(当然这不是唯一的思路)。一般来说，只敢说"一般来说"，因为我也不敢百分百肯定，如今主流的编程语言中使用的随机数函数基本采用这种均匀分布思想，而其中最常用的算法就是"线性同余法"（有着很多的别名，不过我喜欢用这个名字，原因你懂的→_→）。不BB别的算法，直接介绍线性同余法。
1. 什么是线性同余法？
对于计算机科学专业的学生来说，八成会接触一门课，叫作《离散数学》。里面有一章专门介绍初等数论，而线性同余法作为产生均匀型伪随机数的算法，有大概一页的论述（真是一个悲剧(-_-メ)）。当然，可能很多人在初中或者之后的数学竞赛中学过初等数论，线性同余法当然也一定是有过接触的。
线性同余法基于如下线性同余方程组
用于产生均匀型伪随机数的线性同余产生器（与上面的方程符号没有对应关系）
其中，a为"乘数"，b为"增量"，m为"模数",x0为"种子数"。
如果产生的是区间实在(0,1)之间的，则只需要每个数都除以m即可，即取
2. 线性同余法产生均匀型伪随机数需要注意什么？
2.1）种子数是在计算时随机给出的。比如C语言中用srand(time(NULL))函数进行随机数种子初始化。
2.2）决定伪随机数质量的是其余的三个参数，即a,b,m决定生成伪随机数的质量（质量指的是伪随机数序列的周期性）
2.3）一般b不为0。如果b为零，线性同余法变成了乘同余法，也是最常用的均匀型伪随机数发生器。
3. 高性能线性同余法参数取值要求？
3.1）一般选取方法：乘数a满足a=4p+1；增量b满足b=2q+1。其中p，q为正整数。 PS:不要问我为什么，我只是搬运工，没有深入研究过这个问题。
3.2）m值得话最好是选择大的，因为m值直接影响伪随机数序列的周期长短。记得Java中是取得32位2进制数吧。
3.3）a和b的值越大，产生的伪随机数越均匀
3.4）a和m如果互质，产生随机数效果比不互质好。
三、伪随机数代码实现
本文采用Java代码实现伪随机数算法（当然不是调用Java库函数，也不是抄它的代码）。产生序列的均匀性可以通过Matlab或者导入Excel作图直观检验。
1 package monteCarlo;
2
3 public class MonteCarlo {
4 private static final int MAXN = 1 << 20;
5 private int[] x;
6
7 public MonteCarlo() {
8 x = new int[MAXN];
9 }
10
11 public void rand() {
12 x[0] = (int)(Math.random()*100 + 1); // 随机种子(可以用日期产生)
13 /* 保证m与a互质 */
14 int m = MAXN;
15 int a = 9; // a = 4p + 1
16 int b = 7; // b = 2q + 1
17
18 System.out.println(x[0]);
19 /* 取前1w个数*/
20 for(int i = 1; i < 10000; ++i) {
21 x[i] = ( a * x[i-1] + b ) % m;
22 System.out.println(x[i]);
23 }
24 }
25
26 public static void main(String[] args) {
27 MonteCarlo mc = new MonteCarlo();
28 mc.rand();
29 }
30 }