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

Question

为什么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.

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

Answer 1

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,...).如随机种子需要的不同之处所述？参考文献伪随机数发生器初始化中的常见缺陷,相关种子可以在多个RNG的实际序列之间产生相关性.

第三种方法创建随机分布且因此不相关的种子,甚至跨线程和随后的初始化.那么目前的java文档:

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

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

种子序列质量

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

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

并且所提到的论文给出了c = 0和m = 2 ^ 64的良好"乘数"列表,如1181783497276652981.

总而言之:为了努力@JRE-开发人员;)但是有一个错字.(但谁知道,除非有人对其进行评估,否则缺失的前导1实际上可能会改善播种RNG.)

但是一些乘数肯定更糟:"1"导致一个恒定的序列."2"导致单位移动序列(以某种方式相关)......

RNG的序列间相关实际上与(蒙特卡罗)模拟相关,其中多个随机序列被实例化甚至并行化.因此,需要良好的播种策略来进行"独立"模拟运行.因此,C++ 11标准引入了种子序列的概念,用于生成不相关的种子.

Answer 2

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

其中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时,上述等式变为

看一下这篇论文,a =的值1181783497276652981是m = 2 ^ 64,c = 0.所以它似乎只是一个拼写错误,8682522807148012而X(0)的值似乎是遗留代码中看似随机选择的数字对Random.如此处所见.但是这些所选数字的优点仍然可以有效,但正如Thomas B.所提到的那样,可能并不像论文中那样"好".

编辑 - 以下原始思想已被澄清,因此可以忽略不计,但留待参考

这导致我的结论:

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

2. 仅仅巧合的是,除了领先的1之外,其他值是相同的,并且评论是错误的(尽管仍然在努力相信这一点)

要么

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

所以回答你的问题

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

是的,任何数字都可以使用,实际上如果您在实例化随机时指定种子值,则使用任何其他值.该值对发生器的性能没有任何影响,这由在类中硬编码的a,c和m的值确定.