随机长，可以连续两次相同的数字 [英] Random long, can it be twice in a row the same number

问题描述

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

I was wondering with the current java 1.7 implementation of the Random class, is it possible for the code below to generate two times the same random long?

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源代码;

Java source for nextLong() and next();

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周期内不会重复相同的数字，因此它不会在一行中生成两个相同的数字。这是正确的吗？

I would answer this question with false because I think the random method used by java does not repeat the same numbers for a 2^48 period, so it would never generate two the same numbers in a row. Is this correct?

推荐答案

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

To come up with an "longer" answer than my previous:

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

You already linked the implementation, it looks like:

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

因此，显然，一个随机数调用2次下（32）。
这意味着，2个随机数将相等，如果 next（32）结果
为4倍相同数字，因为该函数的其余部分为硬编码。

So, obviously, ONE random number calls 2 times next(32). That means, 2 random numbers will be equal, if next(32) results in 4 times THE SAME number because the rest of the function is "hardcoded".

查看 next（）函数，我们可以看到以下内容：

Looking at the next() function, we can see the following:

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

可以简单地忽略返回部分，因为再次：SAME种子将导致
到相同的返回值 - 除此之外你的CPU坏了。

The return part can be simply ignored, because again: SAME seed would lead to the SAME return value - otherwhise your CPU is broken.

所以，总计：我们只需关注这一行

So, in total: We only need to focus on the line

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

如果这将导致SAME种子，四次，2已生成随机数，
相等。

if that will result in the SAME seed, for four times, 2 random numbers have been generated, that are equal.

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

(Note: Sequences like a,b,a,b can be excluded to produce the same result. Post is long enough, i skip that part.)

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

First, lets eliminate the << 48 part. What does that mean? The Number given (1) will be shifted left 48 times. So the binary 0...01 will turn into 1000000000000000000000000000000000000000000000000 (48 zeros) then, one is subtracted, so what you will get is 0111111111111111111111111111111111111111111111111 (47 ones)

让我们来看看第一部分等式：

Lets have a look at the first part of that equation:

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

注意，结尾[L]只会使它成为长值而不是整数。

因此，在二进制文字中，这意味着：

so, in binary words, that means:

seed * 10111011110111011001110011001101101 + 1011

毕竟，该功能看起来像

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

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

(I left out the leading zeros on the first values)

那么，& （0111111111111111111111111111111111111111111111111） do？

按位和运算符基本上比较了两个二进制数的每个位置。只有当它们中的两个都是1时，结果二进制数中的位置才为1.

The bitwise-and-operator and basically compares EVERY position of two binary numbers. And only if BOTH of them are "1", the position in the resulting binary number will be 1.

这就是说，等式（种子* 10111011110111011001110011001101101 + 1011）位置大于48的位置将忽略。

this said, EVERY bit of the equation (seed * 10111011110111011001110011001101101 + 1011) with a position GREATER than 48 from the RIGHT will be ignored.

第49位等于 2 ^ 49 或 562949953421312十进制 - 意味着& （0111111111111111111111111111111111111111111111111）基本上只是说
MAXIMUM 结果可以 562949953421312 - 1 。
所以，而不是结果 562949953421312 - 它会再次产生0， 562949953421313 会产生1等等上。

The 49th bit equals 2^49 or 562949953421312 decimal - meaning that & (0111111111111111111111111111111111111111111111111) basically just says that the MAXIMUM result can be 562949953421312 - 1. So, instead of the result 562949953421312 - it would produce 0 again, 562949953421313 would produce 1 and so on.

我上面写的所有内容都可以轻松验证：

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

While the following code will produce the random seed *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));
}

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

One can reverse engineer the seed and ALSO gets the seed 11 from a non-0 seed, using the number 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 ）重要吗？

Why is this "magic number" (562949953421312L) important?

假设我们从种子0开始。

Assuming, we are starting with Seed 0.

第一个新种子将是： 0 * 10111011110111011001110011001101101 + 1011 = 1011（dec：11）

下一粒种子将是： 1011 * 10111011110111011001110011001101101 + 1011 = 100000010010100001011011110011010111010（dec：277363943098）

下一粒种子（电话3）将是： 1000000100101001011011110011010111010 * 10111011110111011001110011001101101 + 1011 = 10000100101000000010101010100001010100010011100101100100111101（dec 2389171320405252413）

The next seed (call 3) would be: 100000010010100001011011110011010111010 * 10111011110111011001110011001101101 + 1011 = 10000100101000000010101010100001010100010011100101100100111101 (dec 2389171320405252413)

因此，<$的最大数量超过c $ c> 562949953421312L ，这将导致随机数小于上述计算值。

So, the maximum number of 562949953421312L is exceeded, which will cause the random number to be SMALLER than the above calculated value.

此外，添加 1011 将导致结果在奇数和偶数之间交替。 （不确定真正的含义 - 添加1可能也有效，imho）

Also, adding 1011 will cause the result to alternate between odd and even numbers. (Not sure about the real meaning - adding 1 could have worked as well, imho)

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

So, generating 2 seeds (NOT random numbers) ensures, that they are NOT equal, because a specific "overflow" point has been selected - and adding the MAXIMUM value (562949953421312L) is NOT enough to hit the same number within 2 generations.

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

And when 2 times the same seed is impossible, 4 times is also impossible, which means, that the nextLong() function could never return the same value for n and n+1 generations.

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

这篇关于随机长，可以连续两次相同的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！