有效的 Java 第 47 项:了解和使用您的库 - 有缺陷的随机整数方法示例

Question

在Josh给出的有缺陷的随机方法的例子中，该方法生成具有给定上限n的正随机数，我不明白他所说的两个缺陷。

书中的方法是：

private static final Random rnd = new Random();
//Common but deeply flawed
static int random(int n) {
    return Math.abs(rnd.nextInt()) % n;
}

• 他说，如果n是2的小幂，则生成的随机数序列将在短时间内重复。为什么会这样呢？Random.nextInt()的文档说Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. 那么，如果 n 是一个小整数，那么序列将自行重复，为什么这仅适用于 2 的幂？
• 接下来，他说，如果n不是2的幂，那么某些数字的平均返回频率将比其他数字高。如果Random.nextInt()生成均匀分布的随机整数，为什么会发生这种情况？（他提供了一个代码片段，清楚地证明了这一点，但我不明白为什么会这样，以及这与 n 是 2 的幂有什么关系）。

Answer 1

问题1：如果n是2的小幂，则生成的随机数序列将在短时间内重复。

这不是Josh所说的任何内容的推论;相反，它只是线性同余生成器的已知属性。维基百科有以下几点要说：

LCG 的另一个问题是，如果 m 设置为 2 的幂，则生成序列的低阶位的周期比整个序列短得多。通常，输出序列的基数 b 表示中的第 n 个最低有效数字，其中 b k = m 对于某个整数^k，最多重复周期 bⁿ。

这在Javadoc中也有说明：

线性同余伪随机数生成器（例如此类实现的发生器）已知在其低阶位的值序列中具有短周期。

该函数的另一个版本， Random.nextInt(int) ，在这种情况下通过使用不同的位来解决此问题（强调我的）：

该算法特别处理 n 是 2 的幂的情况：它从底层伪随机数生成器返回正确数量的高阶位。

这是首选Random.nextInt(int)而不是使用Random.nextInt()并进行自己的范围转换的好理由。

问题2：接下来他说，如果n不是2的幂，那么某些数字的平均返回频率将比其他数字高。

有 2³² 个不同的数字可以由 nextInt() 返回。如果您尝试使用 % n 将它们放入 n 个存储桶中，并且 n 不是 2 的幂，则某些存储桶的数字将比其他存储桶多。这意味着即使原始分布是均匀的，某些结果也会比其他结果更频繁地发生。

让我们用小数字来看一下。假设nextInt()返回了四个等概率结果，0、1、2 和 3。让我们看看如果我们对它们应用% 3会发生什么：

0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0

如您所见，该算法返回 0 的频率是返回 1 和 2 的两倍。

当 n 是 2 的幂时，不会发生这种情况，因为 2 的一个幂可以被另一个幂整除。考虑n=2：

0 maps to 0
1 maps to 1
2 maps to 0
3 maps to 1

在这里，0 和 1 以相同的频率出现。

其他资源

以下是一些与LCG相关的其他资源（如果只是切线相关）：

• 光谱测试是用于评估LCG质量的统计测试。
• 具有线性结构的经典伪随机数生成器的集合具有一些漂亮的散点图（Java中使用的生成器称为DRAND48）。
• 关于从 Java 生成器预测值的 crypto.SE 有一个有趣的讨论。

Answer 2

1）当n是2的幂时，rnd % n相当于选择了原始的几个较低的位。已知由Java使用的生成器类型生成的较低位的数字比较高的位"随机性较小"。它只是用于生成数字的公式的属性。

2） 想象一下，random() 返回的可能最大值是 10，并且n = 7 。现在做n % 7将数字 7、8、9 和 10 分别映射到 0、1、2、3。因此，如果原始数字均匀分布，则结果将严重偏向较低的数字，因为它们出现的频率是 4、5 和 6 的两倍。在这种情况下，无论n是否是 2 的幂，这都会发生，但是，如果我们选择而不是 10（即 2^4-1），那么任何n，即 2 的幂将导致均匀分布，因为在范围的末尾不会留下"多余"数字来引起偏差， 因为可能值的总数将完全可以被可能的余数数整除。