9

在用 Java 制作地图生成器时，我发现他们的随机数生成器存在一个相当令人不安的问题，具体来说，当两个 RNG 具有非常相似的种子（以小整数不同）时，它们的第一个输出值将变得非常相似！

示例代码：

Random r = new Random();
long n = 100000; //Choose any number
r.setSeed(n);  
System.out.println(r.nextInt());
r.setSeed(n+1);
System.out.println(r.nextInt());

这几乎打破了我对原始 Java RNG 的信心，因为我使用坐标来生成地图生成器。有人可以建议重新定义该Random.next(int bits)方法，或针对此问题进行其他修复吗？

感谢您的帮助！

4

4 回答 4

9

您是否比较了从 100000 和 100001 获得的前 20 个值的序列？

这些是种子 100000 和 100001 的前 20 个 nextInts。在第三列中是不同位的数量（2 之间的 xor 的位数）

最后一列应该保持在 16 左右

-1986972922 -1987357671 13
-1760380366 -604895790  16
-1057894078 -329706441  15
-363772240  -1218064509 15
1545317691  -300240831  14
271304166   -900428132  21
1208561582  273461468   16
-1257783052 1069490639  16
-1549884799 40157720    15
-1514737808 -1818800021 17
-1030569735 1859508545  15
1310070992  880402584   18
-1513092400 971613287   19
-1993219517 354161779   16
-10847170   -204018237  15
-965377044  1488135032  14
802471291   1094582308  22
-539776032  -1021376555 15
2088199751  2070302462  12
-1271582124 64627614    19

在 3-5 次迭代后不太相似，他

除了标准的 Random 实现了一个线性同余 RNG，它被认为不是现有的最好的伪随机实现，但内存效率最高（一段时间只有一个 64 位字2^48）

对于感兴趣的乘数是0x5deece66dL和 c 是0xbL

于 2011-05-28T20:15:08.860 回答
2

您的两个种子（PRNG 状态）仅在最低有效位上有所不同。考虑到 PRNG 通常只是做一些异或运算并进行转换，这应该不足为奇。

Random无论如何，你不应该这样使用。每种方法都会更新 PRNG 的状态（状态/种子将改变 48 个可用位的约 50%）nextInt。这就是你应该关心的一切。

于 2011-05-28T19:57:59.697 回答
1

据我了解，您需要一个依赖于某些计算种子的随机数序列，这样您就可以在给定相同种子的任何时候重新生成该序列。是对的吗？

相似种子产生的随机数序列开始相似，但很快就发散了。如果您跳过前 k 个值，您可能会得到更适合您需要的结果。在这里，k 是您必须根据您对序列不同和计算速度的需要来确定的数字。

于 2011-05-28T20:05:27.397 回答
0

引入java.security.SecureRandom是为了处理问题中java.util.Random 描述的问题。 SecureRandom没有表现出相同的可预测性（至少，它不那么明显）。您可以通过SecureRandom在代码中使用而不是Random因为前者是后者的子类来解决问题。

有人可能想知道为什么 Sun 在发现此问题后不立即修复Random。原因是向后兼容性—— 的行为Random无法更改，因为它会破坏依赖于任何给定种子生成的特定伪随机序列的现有代码。

于 2011-05-28T20:25:12.583 回答