Random.nextGaussian()的真实最大值和最小值是多少？

Question

Random.nextGaussian()的真实最大值和最小值是多少？

16

在理论上，nextGaussian的边界应该是正无穷和负无穷。但由于计算高斯随机数所使用的Random.nextDouble不可能无限接近0和1，因此nextGaussian也有一个实际限制。而Random.next也不是完全均匀分布。

据推测，最大值应该约为2.2042*10^17，与nextDouble的53位移位相关(参考文献)，但这可能只是一个上限。

答案可能取决于Random.next的分布以及StrictMath.sqrt和StrictMath.log的精确实现。我没有找到太多相关信息。

是的，我知道外部值极不可能出现，但这对于例如在游戏中进行RNG操作的情况可能会有影响。

- Fabian Röling

2

有趣的问题。你看过这些方法的Java源代码吗？那可能会给你答案。 - Hovercraft Full Of Eels

对于Random类而言，是的。但对于我所查看的StrictMath类，没有源代码（https://docs.oracle.com/javase/7/docs/api/java/lang/StrictMath.html）。此外，它并不仅仅给出答案，需要进行相当多的分析，其中并非所有部分我都能理解。 - Fabian Röling

4

这是由Daniel Jelinski在他的博客中进行的研究（第一部分，第二部分）。他说：“找到的最低值为：-7.844680087923773（使用种子=994892的第二次调用nextGaussian）。找到的最高值为：7.995084298635286（使用种子=14005843的第一次调用nextGaussian）。这些是Oracle Java 8实现的nextGaussian返回的真正的最大和最小值。” - Wai Ha Lee

4个回答

7

我会尽力为您翻译相关的IT技术内容。以下是需要翻译的文本：

因此，我在这里说的一切都是纯理论，我仍在开发一个GPU程序来扫描整个种子库。

nextGaussian() 方法实现如下：

private double nextNextGaussian;
private boolean haveNextNextGaussian = false;

 public double nextGaussian() {

   if (haveNextNextGaussian) {

     haveNextNextGaussian = false;
     return nextNextGaussian;

   } else {

     double v1, v2, s;

     do {
       v1 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
       v2 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
       s = v1 * v1 + v2 * v2;
     } while (s >= 1 || s == 0);

     double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
     nextNextGaussian = v2 * multiplier;
     haveNextNextGaussian = true;
     return v1 * multiplier;

   }

 }

最有趣的部分必须在结尾处，[return v1 * multiplier]。因为v1不能大于1.0D，所以我们需要找到一种增加multiplier大小的方法，实现如下。

double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);

唯一可变的是“s”，因此可以确定，“s”越小，乘数就会越大。明白了吗？那我们继续吧。

 do {
   v1 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
   v2 = 2 * nextDouble() - 1;   // between -1.0 and 1.0
   s = v1 * v1 + v2 * v2;
 } while (s >= 1 || s == 0);

这告诉我们 "s" 必须属于 ]0,1[ 数字集，并且我们要找的最小值只是略大于零。"S" 声明为 "v1" 和 "v2" 的平方和。为了获得最小的理论值，v2 需要为零，并且 v1 需要尽可能地小。为什么是“理论”值？因为它们是由 nextDouble() 调用生成的。不能保证种子基础包含这两个连续的数字。

现在让我们玩一下！

"v1" 可以容纳的最小值是 double 类型的 epsilon，即 2^(-1022)。回到前面提到的计算中，要获得这样一个数字，nextDouble 需要生成 (2^(-1022) + 1) / 2。

这非常非常令人担忧。我不是专家，但我很确定会丢失很多位，浮点错误也是预期的。

对于 nextDouble 来生成这样的值可能（几乎肯定）是不可能的，但目标是找到一个尽可能接近该数的值。

就为了好玩，让我们做完整的数学运算来找到答案。StrictMath.log() 实现为自然对数。我没有研究过其精度，但让我们假设在那个级别上没有限制。最高的 nextGaussian 将被计算为...

= (-2 * ln(v1 * v1) / (v1 * v1)) * v1 
= (-2 * ln(EPSILON^2) / (EPSILON^2)) * EPSILON

where EPSILON is equal to 2^(-1022).

信不信由你，我几乎找不到任何可以接受这么小数字的计算器，但最终我选择了这款高精度计算器。

通过输入这个方程式，

(-2 * ln((2^(-1022))^2) / ((2^(-1022))^2)) * (2^(-1022))

我得到了,

1.273479378356503041913108844696651886724617446559145569961266215283953862086306158E+311

相当大吧？嗯...它肯定不会那么大...但考虑一下也挺好。希望我的推理有道理，如果我犯了任何错误，请毫不犹豫地指出。

正如我在开头所说，我正在编写一个程序来暴力破解所有种子并找到实际最低值。我会随时更新。

编辑：

抱歉回复晚了。经过约10小时的暴力破解2^48个种子后，我发现与Earthcomputer得到了完全相同的答案。

- user11069311

2

这个账户的第一篇帖子太棒了。:D 甚至是第一次尝试（没有编辑）！我现在不会将其标记为已接受，因为那只是一个上限。考虑到骷髅头颅，我想10^311的上限并不能真正帮助证明设计是100％可靠的。如果那是一个运动值或类似的东西，它会在不到一帧的时间内飞向远方。对于其他阅读此内容的人，可能非常困惑：我们都在同一个聊天室中，这个问题也源自该聊天室。在上下文中，这一切都有意义。 - Fabian Röling

哈哈，谢谢！:D <3 我认为在这里讨论问题会更好。虽然我很确定很多人想知道实际上限的值，但我找不到任何一个尝试寻找实际上限的帖子。此外，周围还有更聪明的人可以提供帮助。 - user11069311

确实，这是一个很好的答案。但是需要更多的调查才能找到最终的真相。你说：“为了获得最小的理论值，v2需要为零，v1需要尽可能地小。”关键是：当v1很小时，最终结果也会很小。实际最大值可能需要在log(s)/s部分和v1 * ...部分之间进行争夺，这就是复杂的地方... - Marco13

你不必担心这个问题。当v1线性减小时，log(s)/s呈指数级增长。v1的值并不重要。 - user11069311

是的，我也注意到了（在我的答案中也提到了）。然而，在这里相互影响并不是微不足道的，我的答案只能被认为是一个“合理的猜测”。让我们看看是否有人能找到一条论证线路，可以实现大于约12的值。 - Marco13

4

我打赌结果是12.00727336061225。

这个推断大致沿用了KaptainWutax的答案的思路：考虑到乘数部分的log(s)/s，目标必须是让s尽可能小。这还带有额外的限制，即v1将作为结果的一部分。所以基本上：

v1必须要小，这样s才能小
v1必须要大，这样最终的结果才会大

但由于当s趋近于零时，除以s的部分会呈指数级增长，这会使因子v1的贡献被放大。

因此，总结上述思路：

Random#nextGaussian的实现的关键部分在于：

double nextGaussian() {
    double v1, v2, s;
    do {
        v1 = 2 * nextDouble() - 1; // between -1 and 1
        v2 = 2 * nextDouble() - 1; // between -1 and 1
        s = v1 * v1 + v2 * v2;
    } while (s >= 1 || s == 0);
    double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
    return v1 * multiplier;
}

< p > Random#nextDouble 方法的实现方式如下：

double nextDouble() {
    return (((long)next(26) << 27) + next(27)) / (double)(1L << 53);
}

next(n) 返回一个整数，其中最低的n位是随机设置的。

为了最大化nextGaussian的价值，可以得出以下论点：

s的值必须尽可能接近于0.0（但不能等于0.0）
因此，“最佳”v2的值将为0.0，而“最佳”v1的值将是2 * nextDouble() - 1的结果中最小的值
为了让v2==0.0，我们假设nextDouble调用中的随机位为0b10000000000000000000000000000000000000000000000000000L - 在这种情况下，nextDouble将返回0.5，v2将为0.0
导致v1最小有效值的位应为0b10000000000000000000000000000000000000000000000000001L - 只有一个烦人的位在结尾，导致nextDouble返回0.5000000000000001，从而使v1的值为2.220446049250313E-16
在给定这些值的情况下，s将是4.930380657631324E-32，乘数将是5.4075951832589016E16，最终结果将为

12.00727336061225

这里提供了一个示例，您可以在其中尝试不同的位组合，这些位组合可能由基于整个计算的Random#next调用返回。也许有人会发现一种产生更高价值的组合...？

public class LargestNextGaussian
{
    public static void main(String[] args)
    {
        // Random#nextDouble is implemented as 
        //   (((long)next(26) << 27) + next(27)) / (double)(1L << 53)
        // The "baseValue" here refers to the value that
        // is obtained by combining the results of the 
        // two calls to "next"

        long baseValueForV1 = 
            0b10000000000000000000000000000000000000000000000000001L;
        double valueForV1 = 
            baseValueForV1 / (double)(1L << 53);

        long baseValueForV2 = 
            0b10000000000000000000000000000000000000000000000000000L;
        double valueForV2 = 
            baseValueForV2 / (double)(1L << 53);

        // As of Random#nextGaussian:
        double v1, v2, s;
        do {
            v1 = 2 * valueForV1 - 1;
            v2 = 2 * valueForV2 - 1;
            s = v1 * v1 + v2 * v2;
        } while (s >= 1 || s == 0);
        double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
        double result = v1 * multiplier;

        System.out.println("baseValueForV1 " + Long.toBinaryString(baseValueForV1));
        System.out.println("baseValueForV2 " + Long.toBinaryString(baseValueForV2));
        System.out.println("valueForV1     " + valueForV1);
        System.out.println("valueForV2     " + valueForV2);
        System.out.println("v1             " + v1);
        System.out.println("v2             " + v2);
        System.out.println("s              " + s);
        System.out.println("multiplier     " + multiplier);
        System.out.println("result         " + result);
        System.out.println();
    }
}

输出结果如上所述：

baseValueForV1 10000000000000000000000000000000000000000000000000001
baseValueForV2 10000000000000000000000000000000000000000000000000000
valueForV1     0.5000000000000001
valueForV2     0.5
v1             2.220446049250313E-16
v2             0.0
s              4.930380657631324E-32
multiplier     5.4075951832589016E16
result         12.00727336061225

- Marco13

谢谢更详细的解释，我真的低估了它增长的速度。它可以完美地解释为什么是12。 - user11069311

-2

这里是：

long seed=97128757896197L; Random r= new Random(seed ); System.out.println(r.nextGaussian()); System.out.println(r.nextGaussian());

7.995084298635286 0.8744239748619776

- neil pop

2

很高兴知道那个数字是可能的，但这并不意味着它是最大值。 - Fabian Röling

让我们等待地球文章，然后我们就会看到 ^_^ - neil pop

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Earthcomputer · Accepted Answer

随机实现

本答案所需了解的最重要的事情是Random.nextGaussian方法的实现：

synchronized public double nextGaussian() {
    // See Knuth, ACP, Section 3.4.1 Algorithm C.
    if (haveNextNextGaussian) {
        haveNextNextGaussian = false;
        return nextNextGaussian;
    } else {
        double v1, v2, s;
        do {
            v1 = 2 * nextDouble() - 1; // between -1 and 1
            v2 = 2 * nextDouble() - 1; // between -1 and 1
            s = v1 * v1 + v2 * v2;
        } while (s >= 1 || s == 0);
        double multiplier = StrictMath.sqrt(-2 * StrictMath.log(s)/s);
        nextNextGaussian = v2 * multiplier;
        haveNextNextGaussian = true;
        return v1 * multiplier;
    }
}

接下来是Random.nextDouble的实现：

public double nextDouble() {
    return (double) (((long)(next(26)) << 27) + next(27)) / (1L << 53);
}

首先，我想提醒您 nextGaussian 每次生成 2 个值，而且根据您知道自上次设置种子以来调用了多少次 nextGaussian，您可以针对奇偶数次调用使用略低的最大值。从现在开始，我将称这两个最大值为 v1_max 和 v2_max，分别指代由 v1 * multiplier 或 v2 * multiplier 生成的值。

答案

现在让我们直入主题，稍后再解释：

|      |Value             |Seed*          |
|------|------------------|---------------|
|v1_max|7.995084298635286 |97128757896197 |
|v2_max|7.973782613935931 |10818416657590 |
|v1_min|-7.799011049744149|119153396299238|
|v2_min|-7.844680087923773|10300138714312 |
* Seeds for v2 need to have nextGaussian called twice before you see the value listed.

深入了解nextGaussian

@KaptainWutax和@Marco13的答案已经详细介绍了同样的内容，但我认为通过图表更容易理解。让我们关注v1_max，其他三个值具有非常相似的逻辑。我将在x轴上绘制v1，在y轴上绘制v2，在z轴上绘制v1 * multiplier。

Graph

我们的眼睛立刻跳到最大点，在v1=0，v2=0，v1 * multiplier=无穷大时。但是，如果您注意到do-while循环中，它明确禁止了这种情况。因此，从图表可以清楚地看出，实际的v1_max必须具有稍高的v1值，但不会高得多。还值得注意的是，对于任何v1值> 0，最大的v1 * multiplier在v2=0处。

我们找到v1_max的方法是从零开始计算v1（或者更具体地说，从0.5开始计算生成它的nextDouble，按2^-53的步长递增，根据nextDouble的实现）。但是，仅仅知道v1，如何获得其他变量以及该v1的v1 * multiplier呢？

反向nextDouble

事实证明，知道nextDouble调用的输出足以确定生成它的Random对象的种子。直观地说，这是因为查看nextDouble的实现，它“看起来”应该有2^54个可能的输出-但是Random的种子只有48位。此外，可以比暴力更快地恢复此种子。

我最初尝试了一种基于直接使用next(27)获取种子位的方法，然后暴力破解剩余的21位，但这被证明太慢而无法使用。然后SicksonFSJoe给了我一种从单个nextDouble调用中提取种子的更快速的方法。请注意，要理解此方法的细节，您将必须了解Random.next的实现和一些模算术。

private static long getSeed(double val) {
    long lval = (long) (val * (1L << 53));
    // let t = first seed (generating the high bits of this double)
    // let u = second seed (generating the low bits of this double)
    long a = lval >> 27; // a is the high 26 bits of t
    long b = lval & ((1 << 27) - 1); // b is the high 27 bits of u

    // ((a << 22) + c) * 0x5deece66d + 0xb = (b << 21) + d (mod 2**48)
    // after rearranging this gives
    // (b << 21) - 11 - (a << 22) * 0x5deece66d = c * 0x5deece66d - d (mod 2**48)
    // and because modular arithmetic
    // (b << 21) - 11 - (a << 22) * 0x5deece66d + (k << 48) = c * 0x5deece66d - d
    long lhs = ((b << 21) - 0xb - (a << 22) * 0x5deece66dL) & 0xffffffffffffL;

    // c * 0x5deece66d is 56 bits max, which gives a max k of 375
    // also check k = 65535 because the rhs can be negative
    for (long k = 65535; k != 376; k = k == 65535 ? 0 : k + 1) {
        // calculate the value of d
        long rem = (0x5deece66dL - (lhs + (k << 48))) % 0x5deece66dL;
        long d = (rem + 0x5deece66dL) % 0x5deece66dL; // force positive
        if (d < (1 << 21)) {
            // rearrange the formula to get c
            long c = lhs + d;
            c *= 0xdfe05bcb1365L; // = 0x5deece66d**-1 (mod 2**48)
            c &= 0xffffffffffffL;
            if (c < (1 << 22)) {
                long seed = (a << 22) + c;
                seed = ((seed - 0xb) * 0xdfe05bcb1365L) & 0xffffffffffffL; // run the LCG forwards one step
                return seed;
            }
        }
    }

    return Long.MAX_VALUE; // no seed
}

现在我们可以从nextDouble中获取种子，因此迭代v1值而不是种子是有意义的。

将所有内容汇总

算法概述如下：

将nd1（代表nextDouble 1）初始化为0.5
当上限和当前的v1_max未越过时，重复步骤3-7
将nd1增加2 ^ -53
从nd1计算seed（如果存在），并生成nd2、v1、v2和s
检查s的有效性
生成高斯分布，与v1_max进行比较
通过假设v2=0来设置新的上限

以下是Java实现。如果您想要验证我提供的值，可以自行进行验证。

public static void main(String[] args) {
    double upperBound;
    double nd1 = 0.5, nd2;
    double maxGaussian = Double.MIN_VALUE;
    long maxSeed = 0;
    Random rand = new Random();
    long seed;
    int i = 0;
    do {
        nd1 += 0x1.0p-53;
        seed = getSeed(nd1);

        double v1, v2, s;
        v1 = 2 * nd1 - 1;

        if (seed != Long.MAX_VALUE) { // not no seed
            rand.setSeed(seed ^ 0x5deece66dL);
            rand.nextDouble(); // nd1
            nd2 = rand.nextDouble();

            v2 = 2 * nd2 - 1;
            s = v1 * v1 + v2 * v2;
            if (s < 1 && s != 0) { // if not, another seed will catch it
                double gaussian = v1 * StrictMath.sqrt(-2 * StrictMath.log(s) / s);
                if (gaussian > maxGaussian) {
                    maxGaussian = gaussian;
                    maxSeed = seed;
                }
            }
        }

        upperBound = v1 * StrictMath.sqrt(-2 * StrictMath.log(v1 * v1) / (v1 * v1));
        if (i++ % 100000 == 0)
            System.out.println(maxGaussian + " " + upperBound);
    } while (upperBound > maxGaussian);
    System.out.println(maxGaussian + " " + maxSeed);
}

需要注意的最后一个问题是，此算法将为您获取Random的内部种子。要在setSeed中使用它，您必须将其与Random的乘数0x5deece66dL异或（在上面的表格中已经为您完成了）。