伪随机数笔记和洗牌算法

LCG(Linear Congruential Generator)因其简单且容易实现，成为了最常用的伪随机数产生器算法。其缺点是不能用于对随机性要求较高的场合，比如Monte Carlo模拟或加密应用。下面是一个简单的例子。

生成这种周期序列的魔术公式像这样

下面是几个编译器实现的参数值

如果需要更高质量的伪随机数，可以试试1997年开发的Mersenne twister算法。其序列周期通常取Mersenne质数，可长达2的19937次方，且序列关联比较小，能通过很多随机性测试。

伪随机数的一个应用是洗牌算法。例如Fisher–Yates shuffle。

测试洗牌算法的随机性很简单，比如有100个数字，调用算法100次，把结果记录100x100的矩阵，然后统计每个数字在每个行或列的出现次数，其分布中心越靠近100，方差越小越好。