为什么 java.util.Random 使用掩码？

Question

简化（即，排除并发性）Random.next(int bits) 看起来像是

protected int next(int bits) {
    seed = (seed * multiplier + addend) & mask;
    return (int) (seed >>> (48 - bits));
}

使用掩码将种子减少到 48 位。为什么它比仅仅更好

protected int next(int bits) {
    seed = seed * multiplier + addend;
    return (int) (seed >>> (64 - bits));
}

？我读过很多关于随机数的文章，但没有发现这样做的原因。

Answer 1

原因是较低的位往往具有较低的周期（至少对于 Java 使用的算法而言）

来自 Wikipedia -线性同余发生器：

如上所示，LCG 并不总是使用它们生成的值中的所有位。 Java 实现每次迭代都会生成 48 位，但仅返回这些值中的 32 个最高有效位。这是因为高阶位比低阶位具有更长的周期（见下文）。使用这种技术的 LCG 比不使用这种技术的 LCG 产生更好的值。

编辑：

进一步阅读后（方便地在维基百科上），a、c 和 m 的值必须满足这些条件才能具有完整的周期：

1. c 和 m 必须互质

2. a-1 可被 m 的所有质因数整除

3. 如果 m 是 4 的倍数，则 a-1 是 4 的倍数< /p>

我能清楚地看出唯一仍然满意的是 #3。 #1 和 #2 需要检查，我有一种感觉，其中一个（或两个）都失败了。

Answer 2

来自 java.util.Random 顶部的文档：

• 《计算机编程艺术》第 2 卷第 3.2.1 节中进行了描述




• 该算法在Donald Knuth 的 。它是一个 48 位种子、
• 线性同余公式。

因此整个算法被设计为操作 48 位种子，而不是 64 位种子。我想你可以向 Knuth 先生提出这个问题；p

Answer 3

来自 wikipedia （@helloworld922 发布的引文所暗示的引文）：

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

此外，它继续（我的斜体）：

当 m 是 2 的幂时，LCG 的低位位无论如何都不应依赖于任何程度的随机性。事实上，简单地用 2n 代替模数项就可以看出低阶位经历的周期非常短。特别是，当 m 为 2 的幂时，任何全周期 LCG 将交替产生奇数和偶数结果。

最后，原因可能是历史性的：Sun 的人们想要可靠地工作的东西，而 Knuth 公式给出了 32 个有效位。请注意 java.util.Random API 是这么说的（我的斜体）：

如果使用相同的种子创建两个 Random 实例，并且对每个实例进行相同的方法调用序列，则它们将生成并返回相同的数字序列。 为了保证这个属性，为 Random 类指定了特定的算法。为了 Java 代码的绝对可移植性，Java 实现必须使用此处为 Random 类显示的所有算法。但是，Random 类的子类允许使用其他算法，只要它们遵守通用契约即可对于所有方法。

所以我们坚持将其作为参考实现。然而，这并不意味着您不能使用另一个生成器（以及 Random 子类或创建新类）：

来自同一维基百科页面：

MMIX，作者：Donald Knuth m=2⁶⁴ a=6364136223846793005 c=1442695040888963407

有一个适合您的 64 位公式。

随机数很棘手（正如 Knuth 指出的那样），根据您的需要，如果您需要 64 位数字，您可能只需调用 java.util.Random 两次并连接这些位就可以了。如果您确实关心统计属性，请使用类似 Mersenne Twister 的东西，或者如果您关心信息泄漏/不可预测性使用java.security.SecureRandom。

Answer 4

这样做似乎没有一个充分的理由。
使用掩模是一种保守的方法，使用经过验证的设计。
忽略它很可能会产生更好的生成器，但是，在不了解数学的情况下，这是一个冒险的步骤。

掩码的另一个小优点是 8 位架构上的速度增益，因为它使用 6 个字节而不是 8 个字节。