7.2.1. 随机数¶

随机化算法的成功取决于能否获得一个好的随机数生成器。虽然现代编译器很可能包含一个对大多数用途都足够好的随机数生成器，但理解它们如何工作仍是有帮助的，甚至在你不信任编译器提供的那一个时，能够自己构建一个也会有用。这很容易做到。

首先，让我们考虑随机序列是什么。从下面的列表看，哪个看起来像"随机"数的序列？

• 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

• 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

• 2, 7, 1, 8, 2, 8, 1, 8, 2, ...

事实上，这三个碰巧都是某个可以继续其模式以生成更多值的序列的开头。（如果你没认出，第三个是无理常数 \(e\) 的前几位数字。这使它和其他两个序列看起来一样是确定性的。）作为数字序列来看，理想情况下每个可能的序列都有相同的生成概率（即使是上面这三个看起来并不"随机" 的序列）。事实上，随机性的定义通常具有这样的特征：

• 对下一项的预测不会优于瞎猜。

• 无法用比「直接把它列出来」更简短的方式来描述该序列。 这就是 等分布性。

不存在所谓的随机数序列，只有 "足够随机"的序列。如果给定所有过去的项、未来的项都无法在多项式时间内被预测，那么这个序列就是 伪随机的。

大多数计算机系统使用确定性算法来选取伪随机数。 [1] 历史上最常用的方法是 线性同余法 （LCM）。LCM 方法非常简单。我们首先选取一个 种子 ，称之为 \(r(1)\) 。然后，我们可以按如下方式计算后续各项。

其中 \(b\) 和 \(t\) 是常数。对许多目的而言，这给出完全令人满意的随机数序列。它甚至具有这样的特点（对测试目的而言通常被认为是一个好处）：使用相同的种子可以让序列重复。

根据 \(\bmod\) 函数的定义，所有生成的数都必须在 0 到 \(t-1\) 范围内。现在，考虑当 \(r(i) = r(j)\) 对应某些值 \(i\) 和 \(j\) 时会发生什么。当然那么 \(r(i+1) = r(j+1)\)，这意味着我们有一个循环重复了。

由于随机数生成器输出的值在 0 和 \(t-1\) 之间，我们所能期望的最长循环长度为 \(t\)。事实上，由于 \(r(0) = 0\)，它甚至不可能这么长。事实证明，要获得好的结果，为 \(b\) 和 \(t\) 都选取好的值至关重要。要明白为什么，考虑下面的例子。

如果你想自己写一个简单的 LCM 随机数生成器，使用下面的公式就可以做出一个有效的。