114

为什么181783497276652981被8682522807148012选中Random.java？

以下是 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创建另一个种子 uniquifier 以供下次存储new Random()。

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

起初，评论给了我一个简单的线索。在线搜索该文章会产生实际文章。 8682522807148012没有出现在论文中，但181783497276652981确实出现了——作为另一个数字的子字符串，1181783497276652981，它181783497276652981带有1前缀。

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

为什么被8682522807148012选中？

在线搜索这两个数字都没有任何解释，只有这个页面也注意到1前面的181783497276652981.

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

4

3 回答 3

57

  1. 这个数字是否只是错误地复制到 Java 中？

    是的，似乎是一个错字。

  2. 181783497276652981 有可接受的优点吗？

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

  3. 为什么选择 8682522807148012？

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

  4. 是否可以选择与这两个数字一样有效的其他数字？

    并非每个数字都同样“好”。所以不行。

播种策略

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

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

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

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

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

第二个不是线程安全的。多个线程在同时初始化时可以获得相同的 RNG。此外，后续初始化的种子往往是相关的。根据系统的实际计时器分辨率，种子序列可以线性增加（n，n+1，n+2，...）。如随机种子需要有多大不同？以及参考的论文Common缺陷在伪随机数生成器的初始化中，相关种子可以在多个RNG的实际序列之间产生相关性。

第三种方法创建随机分布且因此不相关的种子，即使跨线程和后续初始化也是如此。所以当前的java文档：

此构造函数将随机数生成器的种子设置为一个很可能与此构造函数的任何其他调用不同的值。

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

种子序列质量

但播种序列的随机性仅与底层 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 标准引入了种子序列的概念，用于生成不相关的种子。

于 2013-08-07T10:14:00.127 回答
10

如果您认为用于随机数生成器的等式是：

LCGE方程

其中 X(n+1) 是下一个数，a 是乘数，X(n) 是当前数，c 是增量，m 是模数。

如果您进一步查看Random，a、c 和 m 是在类的标题中定义的

private static final long multiplier = 0x5DEECE66DL;   //= 25214903917 -- 'a'
private static final long addend = 0xBL;               //= 11          -- 'c'
private static final long mask = (1L << 48) - 1;       //= 2 ^ 48 - 1  -- 'm'

并查看方法，protected int next(int bits)这是实现等式的方法

nextseed = (oldseed * multiplier + addend) & mask;
//X(n+1) =  (X(n)   *      a     +    c  ) mod m

这意味着该方法seedUniquifier()实际上正在获取 X(n)，或者在第一种情况下，在初始化 X(0) 时，实际上是8682522807148012 * 181783497276652981，然后通过 的值进一步修改该值System.nanoTime()。该算法与上面的等式一致，但具有以下 X(0) = 8682522807148012，a = 181783497276652981，m = 2 ^ 64 和 c = 0。但是由于 mod m 是由长溢出执行的，所以上面的等式就变成了

eq2

查看论文，a = 的值1181783497276652981是 m = 2 ^ 64，c = 0。所以它似乎只是一个错字，而8682522807148012X(0) 的值似乎是从遗留代码中随机选择的数字为Random. 如此处所见。但是这些选择的数字的优点仍然有效，但正如 Thomas B. 所提到的，可能不如论文中的那个“好”。

编辑 - 以下原始想法已被澄清，因此可以忽略，但留作参考

这使我得出以下结论：

  1. 该论文的参考不是针对值本身，而是针对由于a，c和m的值不同而用于获取值的方法

  2. 仅仅是巧合，除了前导 1 之外的值是相同的，并且评论放错了位置（尽管仍然很难相信这一点）

或者

对论文中的表格存在严重误解，开发人员只是随机选择了一个值，当它乘以首先使用表格值的意义时，尤其是因为您可以提供您的以任何方式拥有种子值，在这种情况下甚至不考虑这些值

所以回答你的问题

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

是的，可以使用任何数字，事实上，如果您在实例化 Random 时指定种子值，则您正在使用任何其他值。这个值对生成器的性能没有任何影响，这是由类中硬编码的 a、c 和 m 的值决定的。

于 2013-08-07T02:58:46.040 回答
3

根据您提供的链接，他们选择了（在添加缺少的 1 之后 :)）2^64 的最佳产量，因为 long 不能有来自 2^128 的数字

于 2013-08-07T00:14:48.023 回答