5

简化（即，不考虑并发）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));
}

? 我已经阅读了很多关于随机数的内容，但没有理由这样做。

4

4 回答 4

5

原因是较低的位往往具有较低的周期（至少在 Java 使用的算法中）

来自维基百科 - 线性同余生成器：

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

编辑：

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

  1. c 和 m 必须是互质数

  2. a-1 能被 m 的所有素因子整除

  3. 如果 m 是 4 的倍数，则 a-1 是 4 的倍数

我唯一可以清楚地告诉我仍然满意的是＃3。＃1和＃2需要检查，我感觉其中一个（或两个）都失败了。

于 2011-04-07T23:51:01.057 回答
2

从 java.util.Random 顶部的文档中：

  • 该算法在计算机编程艺术中有所描述，
  • Donald Knuth第 2 卷，第 3.2.1 节。它是一个 48 位的种子，
  • 线性同余公式。

所以整个算法被设计为操作 48 位种子，而不是 64 位种子。我想你可以和 Knuth 先生一起讨论；p

于 2011-04-07T23:51:35.140 回答
0

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

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

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

当 m 是 2 的幂时，LCG 的低位位不应依赖于任何程度的随机性。实际上，简单地用 2n 代替模数项表明低位比特经历了非常短的周期。特别是，当 m 是 2 的幂时，任何全周期 LCG 都会交替产生奇数和偶数结果。

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

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

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

来自同一个维基百科页面：

MMIX by Donald Knuth m=2 64 a=6364136223846793005 c=1442695040888963407

有一个 64 位公式适合您。

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

于 2011-04-08T00:37:33.677 回答
0

这样做似乎没有充分的理由。使用经过验证的设计，应用掩码是一种保守的方法。将其排除在外很可能会导致更好的生成器，但是，在不了解数学的情况下，这是一个冒险的步骤。

屏蔽的另一个小优势是 8 位架构的速度增益，因为它使用 6 个字节而不是 8 个字节。

于 2011-04-20T02:55:15.190 回答