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

问题

为什么1817834972766529818682522807148012选择了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()将获取当前的"种子无统一者",并将其与2002348321进行异或。然后它使用181783497276652981创建另一个种子uniquifier,以便在下次调用时存储new Random()

literals181783497276652981L8682522807148012L不是放在常量中,但它们不会出现在其他任何地方。

起初评论让我轻松领先。在线搜索该文章yieldthe actual article.8682522807148012并未出现在论文中,但出现了181783497276652981个 - 作为另一个数字的子字符串1181783497276652981,其为181783497276652981,带有1

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

为什么8682522807148012被选中?

在线搜索任何一个数字都不会产生任何解释,只有6724445也会注意到633327430前面的181783497276652981

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


#1 热门回答(53 赞)

  • 这个数字是否被错误地复制到Java中?是的,似乎是一个错字。
  • 181783497276652981是否有可接受的优点?这可以使用本文中提出的评估算法来确定。但"原始"数字的优点可能更高。
  • 为什么选择8682522807148012?似乎是随机的。它可能是编写代码时System.nanoTime()的结果。
  • 其他数字是否可以选择与这两个数字相同?并非每个数字都同样"好"。所以不行。

##播种策略

不同版本和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,...)。如How different do random seeds need to be?和参考文献Common defects in initialization of pseudorandom number generators中所述,相关种子可以在多个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标准引入了用于生成不相关种子的aSeed Sequence的概念。


#2 热门回答(9 赞)

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

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.但是当由于长溢出执行mod m时,上述等式变为

eq2

看看the paper,a = 1181783497276652981的值为m = 2 ^ 64,c = 0.所以它似乎只是一个拼写错误,而值为8682522807148012的X(0)似乎是遗留代码中看似随机选择的数字为Random.As seen here.但是这些所选数字的优点仍然有效,但正如Thomas B.所提到的那样,可能并不像论文中那样"好"。
编辑 - 以下原始想法已被澄清,因此可以忽略但留待参考
这导致了我的结论:

  • 对论文的引用不是针对值本身,而是针对由于a,c和m的不同值而用于获取值的方法
  • 仅仅巧合的是,除了领先的1之外,其他值是相同的,并且评论是错误的(尽管仍然难以相信这一点)

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

所以回答你的问题

其他数字是否可以选择与这两个数字相同?为什么或者为什么不?

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


#3 热门回答(3 赞)

根据你提供的链接,他们选择(在添加缺失的1 :)之后从2 ^ 64中获得最佳收益,因为长期不能有来自2 ^ 128的数字