随机长,可以连续两次相同的数字
我想知道当前java 1.7的Random类实现,下面的代码是否有可能生成相同随机长度的两倍?
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 - bits)); }
我会用false来回答这个问题,因为我认为java使用的随机方法在2 ^ 48周期内不会重复相同的数字,所以它永远不会在一行中生成两个相同的数字。 它是否正确?
想出一个比我之前更“长”的答案:
您已经链接了实现,它看起来像:
public long nextLong(){ return ((long) next(32) << 32) + next(32); }
所以,显然,一个随机数next(32)
调用2次next(32)
。 这意味着,如果next(32)
导致4次相同的数字,则2个随机数将相等,因为该函数的其余部分是“硬编码的”。
查看next()
函数,我们可以看到以下内容:
protected synchronized int next(int bits){ seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); return (int) (seed >>> (48 - bits)); }
可以简单地忽略返回部分,因为再次:SAME种子会导致SAME返回值 - 否则你的CPU就会被破坏。
所以,总的来说:我们只需关注这条线
seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
如果这将导致SAME种子四次 ,则生成2个相等的随机数。
( 注意:可以排除类似a,b,a,b的序列以产生相同的结果。post足够长,我跳过那部分。)
首先,让我们消除<< 48
部分。 那是什么意思? 给定的数字(1)将向左移动48次。 所以二进制0...01
将变为1000000000000000000000000000000000000000000000000
(48个零)然后,减去一个,所以你得到的是0111111111111111111111111111111111111111111111111
(47个)
让我们看一下这个等式的第一部分:
(seed * 0x5DEECE66D[L] + 0xB[L])
注意,结尾[L]只会使它成为长值而不是整数。
所以,用二进制的话来说,这意味着:
seed * 10111011110111011001110011001101101 + 1011
毕竟,function看起来像
seed = (seed * 10111011110111011001110011001101101 + 1011) & (0111111111111111111111111111111111111111111111111)
(我在第一个值上省略了前导零)
那么, & (0111111111111111111111111111111111111111111111111)
做什么?
按位和运算符基本上比较了两个二进制数的每个位置。 并且只有当它们中的两个都是“1”时,结果二进制数中的位置将为1。
这(seed * 10111011110111011001110011001101101 + 1011)
,从RIGHT开始,位置大于48的等式(seed * 10111011110111011001110011001101101 + 1011)
将被忽略 。
第49位等于2^49
或562949953421312 decimal
- 意味着& (0111111111111111111111111111111111111111111111111)
基本上只是说MAXIMUM结果可以是562949953421312 - 1
。 所以,而不是结果562949953421312
- 它将再次产生562949953421313
将产生1,依此类推。
我上面写的所有内容都可以轻松validation:
以下代码将生成随机种子 * 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)); }
人们可以对种子进行逆向工程,并使用数字562949953421312L
从非0种子获得种子11。
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 。
更容易certificate:
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
,这将导致随机数小于上述计算值。
此外,添加1011
将导致结果在奇数和偶数之间交替。 (不确定真正的含义 - 添加1可能也有效,imho)
因此,生成2个种子(非随机数)可确保它们不相等,因为已选择了特定的“溢出”点 - 并且添加MAXIMUM值(562949953421312L)不足以在2代内达到相同的数字。
当2次相同的种子不可能时,4次也是不可能的,这意味着nextLong()函数永远不会为n和n + 1代返回相同的值。
我不得不说,我想certificate相反的情况。 从统计的角度来看,相同数量的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
这取决于你问的问题。
正如其他人所说:伪随机数生成器的标准公式在重复之前充分探索它们的价值空间。
但是:在大多数应用中,我们不使用PRNG的全部输出。 我们通过将其除以或截断到与我们试图解决的问题相匹配的范围来减少它。 事实上,我们这样做的大多数方式都会产生一系列数字,包括即时重复。
即使您只是在基础公式使用更多位进行计算时使用整数随机数,这也可能是真的。
所以:从理论上讲,如果你直接看PRNG的输出,答案是“可能不是”。 实际上,答案是“不要指望它。”
我不这么认为。 我相信生成器使用下一个数字作为后续数字的种子。 因此,如果您获得一次值,并且如果它重复,则您的数字生成器将陷入循环。
然而,许多应用正在寻找一定范围内的数字,这使得重复成为可能,因为后续数字可以具有以该范围为模的相同值。
编辑 :由于您包含了next
的源代码,您可以看到,如果它返回相同的数字,它将始终返回相同的数字。 因此,你会被困在一个值的循环中。