java - 随机(Java 7)中的 181783497276652981 和 8682522807148012 是什么？

Question

为什么在 Random.java 中选择了 181783497276652981 和 8682522807148012？

以下是 Java SE JDK 1.7 的相关源代码:

/**
 * Creates a new random number generator. This constructor sets
 * the seed of the random number generator to a value very likely
 * to be distinct from any other invocation of this constructor.
 */
public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}

private static long seedUniquifier() {
    // L'Ecuyer, "Tables of Linear Congruential Generators of
    // Different Sizes and Good Lattice Structure", 1999
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}

private static final AtomicLong seedUniquifier
    = new AtomicLong(8682522807148012L);

因此，在没有任何种子参数的情况下调用 new Random() 会获取当前的“种子唯一性”并与 System.nanoTime() 进行异或。然后它使用 181783497276652981 创建另一个种子唯一标识符，以便在下次调用 new Random() 时存储。

文字 181783497276652981L 和 8682522807148012L 没有放在常量中，但它们不会出现在其他任何地方。

起初，评论给了我一个简单的线索。在线搜索该文章可得到 the actual article . 8682522807148012 没有出现在论文中，但 181783497276652981 确实出现了——作为另一个数字的子字符串，1181783497276652981，即 181783497276652981 前面带有 1。

该论文声称 1181783497276652981 是一个可以为线性同余生成器产生良好“优点”的数字。这个数字是否只是错误地复制到 Java 中？ 181783497276652981 有可接受的优点吗？

为什么选择8682522807148012？

在线搜索任何一个号码都没有解释，只有 this page这也注意到 181783497276652981 前面的 1 被丢弃。

是否可以选择与这两个数字一样有效的其他数字？为什么或为什么不？

Answer 1

1. Was this number simply mis-copied into Java?

   是的，好像打错了。

2. Does 181783497276652981 have an acceptable merit?

   这可以使用论文中介绍的评估算法来确定。但是“原始”数字的优点可能更高。

3. And why was 8682522807148012 chosen?

   似乎是随机的。可能是编写代码时 System.nanoTime() 的结果。

4. Could other numbers have been chosen that would have worked as well as these two numbers?

   并非每个数字都同样“好”。所以，没有。

播种策略

JRE 的不同版本和实现之间的默认种子模式存在差异。

public Random() { this(System.currentTimeMillis()); }

public Random() { this(++seedUniquifier + System.nanoTime()); }

public Random() { this(seedUniquifier() ^ System.nanoTime()); }

如果您连续创建多个 RNG，则第一个是 Not Acceptable 。如果它们的创建时间落在相同的毫秒范围内，它们将给出完全相同的序列。 (相同的种子 => 相同的序列)

第二个不是线程安全的。多个线程在同时初始化时可以获得相同的 RNG。此外，后续初始化的种子往往是相关的。根据系统的实际计时器分辨率，种子序列可以线性增加(n，n+1，n+2，...)。如 How different do random seeds need to be? 中所述和引用论文Common defects in initialization of pseudorandom number generators , 相关种子可以在多个 RNG 的实际序列之间产生相关性。

第三种方法创建随机分布的不相关种子，甚至跨线程和后续初始化。 所以当前的 java 文档:

This constructor sets the seed of the random number generator to a value very likely to be distinct from any other invocation of this constructor.

可以通过“跨线程”和“不相关”进行扩展

种子序列质量

但种子序列的随机性仅与底层 RNG 一样好。 此 java 实现中用于种子序列的 RNG 使用 c=0 和 m=2^64 的乘法线性同余生成器 (MLCG)。 (模数 2^64 由 64 位长整数溢出隐式给出) 由于零 c 和模数 2 的幂，“质量”(周期长度、比特相关性……)是有限的。正如论文所说，除了总周期长度之外，每个位都有自己的周期长度，对于不太重要的位，周期长度会呈指数下降。因此，较低位具有较小的重复模式。 (seedUniquifier() 的结果应该是位反转的，在实际 RNG 中被截断为 48 位之前)

但它很快!并且为了避免不必要的比较和设置循环，循环体应该很快。这可能解释了这种特定 MLCG 的用法，无需加法，无需异或，只需一次乘法。

并且上述论文提供了 c=0 和 m=2^64 的良好“乘数”列表，如 1181783497276652981。

总而言之:努力@JRE-developers ;) 但是有一个错字。 (但谁知道呢，除非有人评估，否则有可能缺失的前导1实际上提高了种子RNG。)

但有些乘数肯定更糟: “1”导致一个恒定的序列。 “2”导致单比特移动序列(以某种方式相关) ...

RNG 的序列间相关性实际上与 (Monte Carlo) 模拟相关，其中多个随机序列被实例化甚至并行化。因此，一个好的播种策略对于获得“独立”模拟运行是必要的。因此，C++11 标准引入了 Seed Sequence 的概念。用于生成不相关的种子。