为什么Java中的Random.nextLong不能生成所有可能的long值？

Question

Random类的nextLong()方法的Javadoc说明：

由于Random类仅使用48位种子，因此此算法将不返回所有可能的long值。（Random javadoc）

实现方式为:

return ((long)next(32) << 32) + next(32);

我认为应该这样做：要创建任何可能的long，我们应该以等概率生成64位的任意比特模式。假设调用next(int)会给我们32个随机比特，那么这些比特的串联将是一串64个随机比特，因此我们以等概率生成每个64位模式。因此可以生成所有可能的long值。

我想撰写javadoc的人更清楚，我的推理有些错误。有人能解释一下我的推理哪里不对，以及将返回哪种类型的long吗？

- miselico

---

可能是util Random类为什么使用48位种子？的重复问题。 - Engineer2021

我的猜测是，这个程序无法生成前半部分等于后半部分的数字。如果可以，那么调用next(32)时会一直生成相同的数字。这意味着每次调用它时都会生成相同的长整型数字。 - FDinoff

Answer 1

由于随机数是伪随机的，我们知道给定相同的种子它将返回相同的值。根据文档，种子有48位，这意味着最多只能打印出2^48个唯一的值。如果有更多的话，那么在位置 < 2^48 中使用过的某个值将会与上次不同。

如果我们尝试连接两个结果，我们会看到什么？

|a|b|c|d|e|f|...|(2^48)-1|

以下是一些数值，它们能组成多少对呢？如：a-b、b-c、c-d等，直到(2^48)-1-a。总共有2^48对。但我们无法仅凭这2^48对来填满所有的2^64数值。

- Paul Rubel

Answer 2

伪随机数生成器就像是一串数字的巨大环。你从某个地方开始，然后一步一步地在环上移动，每次取出一个数字。这意味着，对于给定的种子 - 初始内部状态 - 所有后续数字都是预先确定的。因此，由于内部状态只有48位宽，只有2的48次方个随机数是可能的。因为下一个数字是由前一个数字给出的，所以现在清楚了为什么nextLong的实现不能生成所有可能的长整型值。

- Chris Vest

---

严格来说，这里相关的不是种子值的长度，而是生成器内部状态的长度。对于所使用的生成器似乎也是如此（尽管我没有查过）。 - Henry

我不相信那种推理。如果我使用 n <= 种子长度 进行 next(n) 操作，那么我是否可以获得所有可能的 n 位值？你必须证明这是不可能的，否则，如果确实可能，我可以从较小的比特数中组合出任意长度的数字。 - Ingo

请注意，这里的“步骤”并不意味着值会一直增加直到环绕（通过打印几个值可以看出）。它只是意味着这些值由初始状态预先确定。 - Paul Rubel

这里的重要部分（应该用粗体或其他方式强调）是“下一个数字由前一个数字给出”。 - njzk2

Answer 3

假设一个完美的伪随机K位生成器是那种在2^K次尝试中创建所有可能的2^K个种子值。我们无法做得更好，因为只有2^K个状态，并且每个状态都完全由前一个状态确定，并决定自己的下一个状态。

假设我们以二进制形式写下48位生成器的输出。这样我们就可以得到2^48 * 48位。 现在我们可以准确地说出通过遍历列表并记录下一个64位序列（需要时回到开头）可以获得多少个64位序列。它正好是我们拥有的位数：13510798882111488。 即使我们假设所有这些64位序列都是两两不同的（这一点并不明显），我们还有很长的路要走，直到2^64：18446744073709551616。

我再次写下这些数字：

18446744073709551616 pairwise different 64 bit sequences we need
   13510798882111488 64 bit sequences we can get with a 48 bit seed.

这证明了javadoc的作者是正确的。只有1/1844的长整型值可以由随机生成器产生。

- Ingo

---

如果生成器具有48位的内部状态，那么很明显，最多只有2^48种可能的状态。因此，无论如何你抽取64位，最多只有2^48种可能的比特序列，而不是完整的2^64。 - Henry

一个伪随机K位生成器，如果在2^K次尝试中创建了所有可能的2^K个值，那么它是一个非常糟糕的生成器。实际上，它是如此糟糕以至于我们可以区分它。想一想生日悖论。 - user515430

你是对的，@Henry，现在我也看到了。我会相应地编辑我的答案。 - Ingo