java - 有效 Java 项目 47 : Know and use your libraries - Flawed random integer method example

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() 的文档说 从这个随机数生成器的序列中返回下一个伪随机、均匀分布的 int 值。 所以如果 n 是小整数，那么序列会重复，为什么这只适用于 2 的幂？
• 接下来他说，如果 n 不是 2 的幂，则某些数字的平均返回频率会比其他数字高。如果 Random.nextInt() 生成均匀分布的随机整数，为什么会出现这种情况？ (他提供了一个代码片段，清楚地证明了这一点，但我不明白为什么会这样，以及这与 n 是 2 的幂有什么关系)。

Answer 1

Question 1: if n is a small power of 2, the sequence of random numbers that are generated will repeat itself after a short period of time.

这不是乔希所说的任何事情的必然结果；相反，它只是 linear congruential generators 的已知属性。 .维基百科有以下说法:

A further problem of LCGs is that the lower-order bits of the generated sequence have a far shorter period than the sequence as a whole if m is set to a power of 2. In general, the n-th least significant digit in the base b representation of the output sequence, where b^k = m for some integer k, repeats with at most period bⁿ.

这在 Javadoc 中也有说明。 :

Linear congruential pseudo-random number generators such as the one implemented by this class are known to have short periods in the sequence of values of their low-order bits.

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

The algorithm treats the case where n is a power of two specially: it returns the correct number of high-order bits from the underlying pseudo-random number generator.

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

Question 2: Next he says that if n is not a power of 2, some numbers will be returned on average more frequently than others.

nextInt() 可以返回 2³² 个不同的数字。如果您尝试使用 % 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 质量的统计测试。阅读更多 here和 here .
• A collection of classical pseudorandom number generators with linear structures有一些漂亮的散点图(Java 中使用的生成器称为 DRAND48)。
• 有一个有趣的discussion在 crypto.SE 上关于预测来自 Java 生成器的值。