有效的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的小数幂，则生成的随机数序列将在短时间后重复其自身。

这不是乔希在说什么的必然结果；相反，它只是线性同余生成器的已知属性。维基百科有以下说法：

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

Javadoc也对此进行了说明：

已知诸如此类的线性同余伪随机数生成器在其低位比特的值的序列中具有短周期。

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

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

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

问题2： 接下来，他说，如果n不是2的幂，则平均而言，某些数字将比其他数字更频繁地返回。

可以返回2 32个不同的数字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）。
• 关于crypto.SE，关于从Java的生成器预测值的有趣讨论。