Java生成"随机"数字,不会重复2 ^ 48个周期

Question

基本上我想生成随机数不会重复很长时间(我不想使用序列),例如java使用的LCG:

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

据我所知,这种情况下的种子只会在2 ^ 48次调用后才重复,这是正确的吗？

所以我理解,如果我做了一个方法,如:

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

保证种子值在2 ^ 48次呼叫之前不重复？

Answer 1

为了参考,对于这些参数的线性同余发生器中实现java.util.Random如下:

a = 25214903917 = 7 x 443 x 739 x 11003
c = 11
m = 2 ⁴⁸
a - 1 = 25214903916

的周期长度为至多米当且仅当所有以下为真:

1. ✔ Ç和米和是互质

2. ✔ 一个 - 1是由所有素数因子整除米

3. ✔ 如果m是4的倍数,则a - 1是4 的倍数

是的,期限是2 ⁴⁸.问题是"低阶位经历非常短的周期." 连续值的低阶位之间的强相关性极大地限制了您可以用它们做什么.

Answer 2

不适用于该 LCG，因为每次调用它时都会修改 2^48（因此周期/状态的长度最多为 2^48）。如果你想要一个更好的随机数生成器，你可以尝试梅森扭曲器：

http://en.wikipedia.org/wiki/Mersenne_twister

标准 MT19937 的周期为 2^19937-1 (!!!) 这应该比您需要的要多。