随机数生成器

很久以前闲得没事逛 Justine Tunney 的 GitHub 时看到这一段代码，很奇怪为什么可以生产随机数。

commit 在此：https://github.com/jart/morton/blob/fe5fdb10b507404233ff303b8ccbcffd3ed30d27/bench.c#L30

这段代码实际上就是使用线性同余方法实现了个伪随机数生成器。

线性同余方法的递推关系式为：

$$N_{i+1} = (a \cdot N_i + c) \mod m$$

其中 $a$、$c$、$m$ 是常数，$N_i$ 是第 $i$ 个随机数。

在这段代码中，$a$、$c$、$m$ 分别是 6364136223846793005、1442695040888963407、$2^{64}$，$N_0$ 是 1。

伪随机数的一个致命缺陷是周期性，不同的参数会有不同的周期。

从Linear congruential generator-常用参数这里看，这两个参数来源于 Donald Knuth 的 MMIX。

这段代码还对随机数进行了一次截断，只取了 32 位，有两个原因：

1. 要求输出 32 位随机数
2. 一般来说，高 32 位比低 32 位的周期更长。