随机长，可以连续两次相同的数字

random java

2022-09-03 13:12:02

我想知道对于Random类的当前java 1.7实现，下面的代码是否有可能生成两倍相同的随机长度？

Random rand = new Random((long) "some seed".hashCode());
while(rand.nextLong() != rand.nextLong()){

}

System.out.println("Will this text ever be on the console?");

nextLong（）和 next（）的 Java 源代码;

public long nextLong(){
    return ((long) next(32) << 32) + next(32);
}

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >>> (48 - bits));
}

我会用false来回答这个问题，因为我认为java使用的随机方法不会在2 ^ 48周期内重复相同的数字，因此它永远不会连续生成两个相同的数字。这是正确的吗？

答案 1

想出一个比我之前“更长”的答案：

您已经链接了该实现，它看起来像这样：

public long nextLong(){
    return ((long) next(32) << 32) + next(32);
}

因此，显然，一个随机数调用了2次。这意味着，如果结果是相同数字的4倍，则2个随机数将相等，因为函数的其余部分是“硬编码的”。next(32)next(32)

查看函数，我们可以看到以下内容：next()

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >>> (48 - bits));
}

返回部分可以简单地忽略，因为同样：相同的种子将导致相同的返回值 - 否则你的CPU坏了。

所以，总的来说：我们只需要专注于这条线

seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);

如果这将导致相同的种子，则四次生成2个相等的随机数。

(注意：可以排除 a，b，a，b 等序列以产生相同的结果。帖子足够长，我跳过了那部分。

首先，让我们消除该部分。那是什么意思？给定的数字（1）将向左移动 48 次。所以二进制文件会变成（48个零），然后，一个被减去，所以你得到的是（47个）<< 480...0110000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111

让我们看一下这个等式的第一部分：

(seed * 0x5DEECE66D[L] + 0xB[L])

请注意，结尾的 [L] 只会导致它是长整型值，而不是整数。

所以，在二进制词中，这意味着：

seed * 10111011110111011001110011001101101 + 1011

毕竟，该功能看起来像

seed = (seed * 10111011110111011001110011001101101 + 1011) & (0111111111111111111111111111111111111111111111111)

（我省略了第一个值的前导零）

那么，有什么作用呢？& (0111111111111111111111111111111111111111111111111)

按位和运算符，基本上比较两个二进制数的每个位置。只有当它们都是“1”时，生成的二进制数中的位置才会是1。

也就是说，等式中位置大于右侧48的每一位都将被忽略。(seed * 10111011110111011001110011001101101 + 1011)

第 49 位等于 or - 这意味着 &基本上只是说最大结果可以是。因此，而不是结果 - 它将再次产生0，将产生1，依此类推。2^49562949953421312 decimal(0111111111111111111111111111111111111111111111111)562949953421312 - 1562949953421312562949953421313

我上面写的所有内容都可以很容易地验证：

而以下代码将生成随机种子 *11*：

private Long seed = 0L;

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    System.out.println(seed);
    return (int) (seed >>> (48 - bits));
}

可以对种子进行逆向工程，也可以使用数字从非0种子中获取种子11。562949953421312L

private Long seed = 562949953421312L - 0xBL / 0x5DEECE66DL;

protected synchronized int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    System.out.println(seed);
    return (int) (seed >>> (48 - bits));
}

所以，你看：种子562949953421312等于种子0。

更简单的证明：

Random r = new Random(0L);
Random r2 = new Random(562949953421312L);

if (r.nextLong()==r2.nextLong()){
    System.out.println("Equal"); //You WILL get this!
}

当然，它是连续的：

Random r3 = new Random(1L);
Random r4 = new Random(562949953421313L);

if (r3.nextLong()==r4.nextLong()){
    System.out.println("Equal");
}

为什么这个“幻数”（）很重要？562949953421312L

假设我们从种子 0 开始。

第一个新种子将是：0 * 10111011110111011001110011001101101 + 1011 = 1011 (dec: 11)

下一个种子将是：1011 * 10111011110111011001110011001101101 + 1011 = 100000010010100001011011110011010111010 (dec: 277363943098)

下一个种子（调用 3）将是：100000010010100001011011110011010111010 * 10111011110111011001110011001101101 + 1011 = 10000100101000000010101010100001010100010011100101100100111101 (dec 2389171320405252413)

因此，超过了的最大数目，这将导致随机数小于上述计算值。562949953421312L

此外，加法将导致结果在奇数和偶数之间交替。（不确定真正的含义 - 添加1也可以工作，恕我直言）1011

因此，生成2个种子（不是随机数）可确保它们不相等，因为已经选择了特定的“溢出”点 - 并且添加最大值（562949953421312L）不足以在2代内达到相同的数字。

当 2 倍相同的种子是不可能的，4 倍也是不可能的，这意味着 nextLong（）函数永远不会为 n 和 n+1 代返回相同的值。

我不得不说，我想证明相反的情况。从统计学的角度来看，2倍相同的数字是可能的 - 但也许这就是为什么它被称为伪随机性:)

答案 2

不，使用此算法连续获得两个相同的长线是不可能的。

当人们写关于数学和其他巫术的长篇文章时，我走了代码猴子路线，并在周末强行了2 ^ 48个可能的种子。对于任何种子，连续产生的两条长镜头都不会相等。

long int seed = 0;

int next(int bits){
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
    return (int) (seed >> (48 - bits));
}
long int nextLong(){
    return ((long int) next(32) << 32) + next(32);
}

int main(int argc, char** argv) {
  long int step = atoi(argv[1]);
  long int i = step << 32;
  long int end = (step+1) << 32;
  while(i < end) {
    seed = i;
    if(nextLong() == nextLong()) {
      printf("Found seed %ld\n", i);
      return 0;
    }
    ++i;
  }
  printf("No seed in %ld\n", step);
  return 1;
}

然后

echo {0..65535} | xargs -n 1 -P 12 ./executable