有效的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输出序列的表示,其中对于某些整数k,b ^k = m,以至多周期b ⁿ重复.

这在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生成器预测值的讨论.

Answer 2

1)当n2的幂时,rnd % n相当于选择原始的几个低位.由java使用的生成器类型生成的较低位数已知比较高位"较不随机".它只是用于生成数字的公式的属性.

2)想象一下,返回的最大可能值random()是10,和n = 7.现在n % 7将地图编号7,8,9和10分别分为0,1,2,3.因此,如果原始数字均匀分布,结果将严重偏向较低的数字,因为它们将出现两倍于4,5和6的情况.在这种情况下,无论是否n为2的幂,都会发生这种情况.是否,但是,如果我们选择15而不是10(即2 ^ 4-1),那么任何2 n的幂将导致均匀分布,因为不存在"多余"数字留在范围的末尾以引起偏差,因为可能值的总数可以被可能的剩余部分的数量完全整除.