What's with 181783497276652981 and 8682522807148012 in Random (Java 7)?

为什么 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);

So, invoking new Random() without any seed parameter takes the current "seed uniquifier" and XORs it with System.nanoTime(). Then it uses 181783497276652981 to create another seed uniquifier to be stored for the next time new Random() is called.

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

起初，这个评论给了我一个简单的线索。在线搜索该文章会得到 真正的文章。8682522807148012没有出现在论文中，但是 181783497276652981出现了——作为另一个数字 1181783497276652981的子串，1181783497276652981是 181783497276652981，后面加上 1。

The paper claims that 1181783497276652981 is a number that yields good "merit" for a linear congruential generator. Was this number simply mis-copied into Java? Does 181783497276652981 have an acceptable merit?

为什么选择 8682522807148012？

在线搜索任何一个数字都不会得到解释，只有 this page会注意到 181783497276652981前面丢失的 1。

Could other numbers have been chosen that would have worked as well as these two numbers? Why or why not?

4996 次浏览
小开

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

小开

如果你认为用于随机数生成器的公式是:

LCGEquation

其中 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相一致。但是当长溢出预先形成模 m 时，上述方程就变成了

eq2

看看 报纸，a = 1181783497276652981的值是 m = 2 ^ 64，c = 0。因此，它似乎只是一个输入错误和 X (0)的值 8682522807148012，这似乎是从 Random的遗留代码中随机选择的数字。但是这些选择的数字的优点可能仍然是有效的，但是正如托马斯 B 提到的那样，可能不如论文中的那个“好”。

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

这让我得出结论:

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

  2. 这仅仅是巧合，除了前面的1之外，其他值都是一样的，而且评论是错误的(尽管仍然难以相信这一点)

OR

对于这篇文章中的表格有一个严重的误解，开发人员只是随机选择了一个值，因为当这个值被乘以之后，使用表格值的初衷是什么，尤其是你可以以任何方式提供你自己的种子值，在这种情况下，这些值甚至没有被考虑进去

So to answer your question

有没有可能选择其他的数字也能像这两个数字一样有效呢? 为什么呢？

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

小开
最佳答案

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

    Yes, seems to be a typo.

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

    这可以用本文提出的评价算法来确定。但“原始”数字的价值可能更高。

  3. 为什么选择了8682522807148012？

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

  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，则第一个是不可接受的。如果它们的创造时间在相同的毫秒范围内，它们将给出完全相同的序列。(相同的种子 = > 相同的序列)

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

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

此构造函数将随机数生成器的种子设置为 value very likely to be distinct from any other invocation of this 构造函数。

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

种子序列质量

但是种子序列的随机性只能取决于底层 RNG 的随机性。 在这个 java 实现中，用于种子序列的 RNG 使用了一个 c = 0和 m = 2 ^ 64的乘法线性同余方法(mLCG)。(模2 ^ 64由64位长整数的溢出隐式给出) 由于零 c 和2模的功率，“质量”(周期长度，位相关性，...)是有限的。正如文中所说，除了整个周期长度，每个位都有自己的周期长度，对于不太重要的位，周期长度呈指数递减。因此，较低的位具有较小的重复模式。(在实际 RNG 中截断为48位之前，SeeUniquifier ()的结果应该是位反转的)

但它很快！为了避免不必要的比较和设置循环，循环体应该是快速的。这可能解释了这个特定 MLCG 的用法，没有加法，没有 xoring，只有一个乘法。

给出了 c = 0和 m = 2 ^ 64的一组好的“乘数”，即1181783497276652981。

总而言之: A for work@JRE-developers;)但是有一个输入错误。 (但是谁知道呢，除非有人对它进行评估，否则有可能缺少的前导1实际上改进了种子 RNG。)

但一些乘数无疑更糟: “1”导致一个常数序列。 “2”导致一个单位移动序列(以某种方式相关) ...

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


提交答案