有效 Java 第 47 项：了解并使用你的库 - 有缺陷的随机整数方法示例
Effective Java Item 47: Know and use your libraries - Flawed random integer method example
在 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 的幂有何关系）。
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 bk = m for some integer k, repeats with at most period bn.
这在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() 可以 return 编辑 232 个不同的数字。如果您尝试使用 % n 将它们放入 n 个桶中，并且 n 不是 2 的幂，则某些桶的数量将多于其他桶。这意味着即使原始分布是均匀的，某些结果也会比其他结果更频繁地出现。
让我们用小数字来看一下。假设 nextInt() return 得到了四个等概率结果，0、1、2 和 3。让我们看看如果我们对它们应用 % 3 会发生什么：
0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0
如您所见，该算法 return 0 的频率是 return 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 and here.
- A collection of classical pseudorandom number generators with linear structures has some pretty scatterplots (the generator used in Java is called DRAND48).
- crypto.SE 上有一个有趣的 discussion 关于从 Java 的生成器预测值。
1）当n是2的幂时，rnd % n相当于选择了原来的低几位。 java 使用的生成器类型生成的数字的低位比高位已知为 "less random"。它只是用于生成数字的公式的 属性。
2) 想象一下，random() 返回的最大可能值是 10，而 n = 7。现在做 n % 7 将数字 7、8、9 和 10 分别映射到 0、1、2、3。因此，如果原始数字是均匀分布的，结果将严重偏向较低的数字，因为它们出现的频率是 4、5 和 6 的两倍。在这种情况下，无论 n是或不是二的幂，但是，如果我们选择 15 而不是 10（即 2^4-1），那么任何 n，即二的幂将导致均匀分布，因为在范围末尾不会留下 "excess" 个数字来引起偏差，因为可能值的总数将被可能余数的数量整除。
在 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 的幂有何关系）。
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 bk = m for some integer k, repeats with at most period bn.
这在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() 可以 return 编辑 232 个不同的数字。如果您尝试使用 % n 将它们放入 n 个桶中，并且 n 不是 2 的幂，则某些桶的数量将多于其他桶。这意味着即使原始分布是均匀的，某些结果也会比其他结果更频繁地出现。
让我们用小数字来看一下。假设 nextInt() return 得到了四个等概率结果，0、1、2 和 3。让我们看看如果我们对它们应用 % 3 会发生什么：
0 maps to 0
1 maps to 1
2 maps to 2
3 maps to 0
如您所见，该算法 return 0 的频率是 return 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 and here.
- A collection of classical pseudorandom number generators with linear structures has some pretty scatterplots (the generator used in Java is called DRAND48).
- crypto.SE 上有一个有趣的 discussion 关于从 Java 的生成器预测值。
1）当n是2的幂时，rnd % n相当于选择了原来的低几位。 java 使用的生成器类型生成的数字的低位比高位已知为 "less random"。它只是用于生成数字的公式的 属性。
2) 想象一下，random() 返回的最大可能值是 10，而 n = 7。现在做 n % 7 将数字 7、8、9 和 10 分别映射到 0、1、2、3。因此，如果原始数字是均匀分布的，结果将严重偏向较低的数字，因为它们出现的频率是 4、5 和 6 的两倍。在这种情况下，无论 n是或不是二的幂，但是，如果我们选择 15 而不是 10（即 2^4-1），那么任何 n，即二的幂将导致均匀分布，因为在范围末尾不会留下 "excess" 个数字来引起偏差，因为可能值的总数将被可能余数的数量整除。