有效的Java项目47：了解并使用您的库 – 有缺陷的随机整数方法示例

在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()生成均匀分布的随机整数，为什么会发生这种情况呢？ （他提供了一个代码片段，清楚地certificate了这一点，但我不明白为什么会出现这种情况，以及这与n是2的权力有什么关系）。

Answer 1

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

这不是约什所说的任何必然结果; 相反，它只是线性同余生成器的已知属性。 维基百科有如下说法：

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

这在Javadoc中也有提到：

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

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

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

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

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

nextInt()可返回2 ^32个不同的数字。 如果您尝试使用% 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生成器预测值的讨论 。

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是否是n的幂，都会发生这种情况。两个与否，但是，如果不是10个，我们选择15个（即2 ^ 4-1），那么任何n ，即2的幂将导致均匀分布，因为没有“过剩“在该范围的末尾留下的数字会导致偏差，因为可能值的总数可以完全被可能的剩余数量整除。