在计算机、通信系统中我们采用的随机数、随机码均为伪随机数。伪随机数，所谓“随机码”，就是无论这个码有多长都不会出现循环的现象，而“伪随机码”在码长达到一定程度时会从其第一位开始循环，由于出现的循环长度相当大，例如CDMA采用42位的伪随机码，重复的可能性为4.4万亿分之一，所以可以当成随机码使用。

    哲学概念即“没有什么是随机的。”应用到数学怎么解释？在计算机科学怎么表达？是否可在硬件底层实现？

    好吧，以我现在的知识量很难理解清楚这些问题。那就浅谈下随机数的概念吧。

    原理上，一般地，伪随机数的生成方法主要有以下3种：

（1） 直接法（Direct Method），根据分布函数的物理意义生成。缺点是仅适用于某些具有特殊分布的随机数，如二项式分布、泊松分布。

（2） 逆转法（Inversion Method），假设U服从[0，1]区间上的均匀分布，令X=F-1（U），则X的累计分布函数（CDF）为F。该方法原理简单、编程方便、适用性广。

（3）接受拒绝法（Acceptance-Rejection Method）：假设希望生成的随机数的概率密度函数（PDF）为f，则首先找到一个PDF为g的随机数发生器与常数c，使得f

（x）≤cg（x），然后根据接收拒绝算法求解。由于算法平均运算c次才能得到一个希望生成的随机数，因此c的取值必须尽可能小。显然，该算法的缺点是较难确定g与c。

因此，伪随机数生成器（PRNG）一般采用逆转法，其基础是均匀分布，均匀分布PRNG的优劣决定了整个随机数体系的优劣[7]。下文研究均匀分布的PRNG。

    算法上，有（不仅）以下几种：

　一、线性同余法

　　对于计算机科学专业的学生来说，八成会接触一门课，叫作《离散数学》。里面有一章专门介绍初等数论，而线性同余法作为产生均匀型伪随机数的算法，有大概一页的论述（真是一个悲剧(-_-メ)）。当然，可能很多人在初中或者之后的数学竞赛中学过初等数论，线性同余法当然也一定是有过接触的。

　　线性同余法基于如下线性同余方程组

　　用于产生均匀型伪随机数的线性同余产生器（与上面的方程符号没有对应关系）

　　其中，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如果互质，产生随机数效果比不互质好。

        二、平方取中法

        平方取中法是由冯·诺依曼在1946年提出的，其基本思想为：将数列中的第a(i)项（假设其有m位）平方，取得到的2m位数（若不足2m位，在最高位前补0）中间部分的m位数字，作为a(i)的下一项a(i+1)，由此产生一个伪随机数数列。即：

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

        三、马特赛特旋转演算法

        Mersenne Twister 马特赛特旋转演算法，是1997年提出的伪随机数生成算法，其修复了以往随机数生成算法的诸多缺陷，可快速生成高质量的伪随机数，且经过了广泛的统计学检验，目前在各种编程语言和库中已普遍存在或作为默认的伪随机数发生器，被认为是更可靠的伪随机数发生器。下图截自python的官方文档：

主要流程有3步是：

初始化n个状态：根据给定的种子点x0，通过移位、异或、乘法、加法等操作生成后续的n−1个状态x1到xn−1，bit位数为w

生成伪随机数：根据当前状态，通过移位、与、异或操作生成随机数

更新n个状态：每生成n个随机数后，在生成下一个随机数前，更新状态

标准实现32bit版本称之为MT19937，参数设置如下：

• (w,n,m,r)=(32,624,397,31)(w,n,m,r)=(32,624,397,31)

• a=9908B0DF16a=9908B0DF16

• (u,d)=(11,FFFFFFFF16)(u,d)=(11,FFFFFFFF16)

• (s,b)=(7,9D2C568016)(s,b)=(7,9D2C568016)

• (t,c)=(15,EFC6000016)(t,c)=(15,EFC6000016)

• l=18