3

这是我不明白的代码：

// Divide n by two until small enough for nextInt. On each
// iteration (at most 31 of them but usually much less),

什么？通过我对随机选择的简单模拟n，我得到了32迭代并且31是平均值。

// randomly choose both whether to include high bit in result
// (offset) and whether to continue with the lower vs upper
// half (which makes a difference only if odd).

这是有道理的。

long offset = 0;
while (n >= Integer.MAX_VALUE) {
    int bits = next(2);

为两个决定获取两个位，这是有道理的。

    long half = n >>> 1;
    long nextn = ((bits & 2) == 0) ? half : n - half;

在这里，向上或向下舍入，很好n。n/2.0

    if ((bits & 1) == 0) offset += n - nextn;
    n = nextn;

我迷路了。

}
return offset + nextInt((int) n);

我可以看到它生成了一个适当大小的数字，但它看起来很复杂而且很慢，我绝对看不出为什么结果应该是均匀分布的。1

1它不能真正均匀分布，因为状态只有 48 位，所以它可以生成不超过 2**48 个不同的数字。绝大多数longs 无法生成，但实验表明它可能需要数年时间。

4

1 回答 1

2

我认为你有点误会......让我试着用我看到的方式来描述算法：

首先，假设nextInt(big)(nextInt, not nextLong) 能够正确地在0(inclusive) 和big(exclusive) 之间生成分布良好的值范围。

此nextInt(int)功能用作nextLong(long)

因此，该算法通过循环工作，直到该值小于 Integer.MAX_INT，此时它使用nextInt(int). 更有趣的是它在这之前做了什么……

从数学上讲，如果我们取一个数字的一​​半，减去它的一半，然后减去一半的一半，然后再减去一半的一半，等等，我们这样做的次数足够多，它将趋向于零。类似地，如果你取一个数字的一​​半，并将它添加到一半的一半，等等，它将趋向于原始数字。

该算法在这里所做的是它需要一半的数字。通过进行整数除法，如果数字是奇数，则有一个“大”的一半和一个“小”的一半。该算法“随机”选择其中一半（大或小）。

然后，它随机选择将那一半添加到输出中，或者不将那一半添加到输出中。

它不断将数字减半并（可能）添加一半，直到一半小于 Integer.MAX_INT。此时，它只是计算nextInt(half)值并将其添加到结果中。

假设最初的长限制远大于Integer.MAX_VALUE那么最终结果将获得 nextInt(int) 的所有好处，因为它具有至少 32 位状态的大 int 值，以及以上所有更高位的 2 位状态Integer.MAX_VALUE.

原始限制越大（越接近 Long.MAX_VALUE），循环迭代的次数就越多。在最坏的情况下，它将经过 32 次，但对于较小的限制，它将经过更少的次数。在最坏的情况下，对于非常大的限制，您将获得用于循环的 64 位随机性，然后也是所需的任何东西nextInt(half)。

编辑：演练添加 - 计算结果的数量更难，但是，所有 long from 0to的值Long.MAX_VALUE - 1都是可能的结果。作为“证明”使用nextLong(0x4000000000000000)是一个很好的例子，因为所有的减半过程都是均匀的，并且它设置了 63 位。

因为第 63 位已设置（可用的最高有效位，因为 bit64 会使数字变为负数，这是非法的）这意味着我们将在值 <= Integer.MAX_VALUE 之前将值减半 32 次（即0x000000007fffffff- 我们half将0x0000000004000000当我们到达那里时......）。因为减半和位移是相同的过程，所以它认为有多少一半要做，就像最高位集和位 31 之间的差一样。63 - 31 是 32，所以我们将事情减半 32 次，因此我们做了 32在while循环中循环。的初始起始值0x4000000000000000意味着当我们将值减半时，在一半中只会设置一个位，并且它将“走”该值 - 每次循环都向右移动 1。

因为我仔细选择了初始值，所以很明显，在 while 循环中，逻辑本质上是决定是否设置每个位。它取输入值的一半（即 0x2000000000000000）并决定是否将其添加到结果中。让我们假设我们所有的循环都决定将一半添加到偏移量，在这种情况下，我们从偏移量 0x0000000000000000 开始，然后每次通过循环我们添加一半，这意味着每次我们添加：

0x2000000000000000
0x1000000000000000
0x0800000000000000
0x0400000000000000
.......
0x0000000100000000
0x0000000080000000
0x0000000040000000  (this is added because it is the last 'half' calculated)

在这一点上，我们的循环已经运行了 32 次，它已经“选择”将值相加 32 次，因此值中至少有 32 个状态（如果计算大/小一半决策，则为 64）。现在是实际偏移量0x3fffffffc0000000（从 62 到 31 的所有位都已设置）。

然后，我们调用 nextInt(0x40000000) ，幸运的是，它产生结果 0x3fffffff，使用 31 位状态到达那里。我们将此值添加到我们的偏移量并得到结果：

0x3fffffffffffffff

有了nextInt(0x40000000)结果的“完美”分布，我们就可以完美地覆盖这些值0x7fffffffc0000000，0x3fffffffffffffff没有任何差距。在我们的 while 循环中具有完美的随机性，我们的高位将是0x0000000000000000通过0x3fffffffc0000000组合的完美分布，从 0 到我们的限制（不包括）完全覆盖0x4000000000000000

使用来自高位的 32 位状态，以及（假设的）最小 31 位状态，nextInt(0x40000000)我们有 63 位状态（如果算上大/小一半决策，则更多）和全覆盖。

于 2013-11-03T14:38:30.287 回答