3.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 随机数生成器， 使用下面的公式就可以做出一个有效的。