这次主要介绍伪随机数生成算法，顺便介绍一个在2018-2019年的伪随机数研究成果，就是 xoshiro/xoroshiro 随机数生成算法。
历史 在较早的时候，甚至到现在，伪随机数的生成元老级别算法“线性同余伪随机数生成算法”可谓无处不在，像现在的C/C++的rand函数就是使用线性同余实现的伪随机数生成。所谓的线性同余法，就是这个迭代方程 $S_n = (aS_{n-1} + c)\mod m$，其中，$S_0$ 称为这个随机序列的种子，a,c,m是三个常数，不过这三个数不能随意选，m的大小决定随机数的周期，最大周期等于m，为了便于在计算机里实现，通常m选取$2^{32}$或$2^{64}$。在m已经确定为这两的时候，为了让周期尽可能大，常数a,c还至少要满足以下条件：
若 c 非 0，那么 c 与 m 互质；若 c 为 0，那么 a 与 m 互质 m 所有的素因子均能整除 a-1 若 m 是4的倍数，那么 a-1 也是 4 的倍数 a 和 c 都是正整数且小于 m 一些典型的常数取值可以参见wiki上的线性同余条目。
更高的需求 我们之所以使用线性同余，就是因为它实现简单，在对随机数质量要求较低的时候，例如用来作为treap的随机数，那么线性同余完全够用，但建议不要使用rand，因为在windows下不少编译器的最大值太小了，导致效果下降，自己写一个用参数a=69069,c=1,m=2^32比rand好，我在那篇关于treap的文章就是用了这组参数。线性同余法最大的缺陷是低位随机性特别差，如果使用类似next() % k的方式来获得区间在$[0,k-1]$的随机数，那么当线性同余迭代方程的m是2的幂且k也是2的幂的时候，灾难就发生了，特别地当k是2的时候，你将得到一个0101的循环序列。为了避免这种情况，通常会取线性同余结果的高位，而且低位去掉得越多，%2的周期就越长。例如结果是64位，取高32位作为最终结果，那么%2的周期就是 $2^{33}$ ，但这样会导致有效位减少，而且问题也没有根本地解决。另一种解决办法是选取一个素数作为m，例如2147483647正是一个素数，但如此一来，线性同余的计算速度就会慢不少，周期也没有前一个的长。两种基本实现如下：