30

我发现使用 Java 的 Random 类生成随机数时有些奇怪。基本上，如果您使用紧密种子（例如在 1 到 1000 之间）创建多个 Random 对象，每个生成器生成的第一个值将几乎相同，但下一个值看起来很好（我没有进一步搜索）。

这是种子从 0 到 9 的两个第一个生成的双打：

  • 0 0.730967787376657 0.24053641567148587
  • 1 0.7308781907032909 0.41008081149220166
  • 2 0.7311469360199058 0.9014476240300544
  • 3 0.731057369148862 0.07099203475193139
  • 4 0.7306094602878371 0.9187140138555101
  • 5 0.730519863614471 0.08825840967622589
  • 6 0.7307886238322471 0.5796252073129174
  • 7 0.7306990420600421 0.7491696031336331
  • 8 0.7302511331990172 0.5968915822372118
  • 9 0.7301615514268123 0.7664359929590888

从 991 到 1000 ：

  • 991 0.7142160704801332 0.9453385235522973
  • 992 0.7109015598097105 0.21848118381994108
  • 993 0.7108119780375055 0.38802559454181795
  • 994 0.7110807233541204 0.8793923921785096
  • 995 0.7109911564830766 0.048936787999225295
  • 996 0.7105432327208906 0.896658767102804
  • 997 0.7104536509486856 0.0662031629235198
  • 998 0.7107223962653005 0.5575699754613725
  • 999 0.7106328293942568 0.7271143712820883
  • 1000 0.7101849056320707 0.574836350385667

这是一个显示从 0 到 100,000 的种子生成的第一个值的图。

基于种子生成的第一个随机双精度：

图片

我搜索了有关此的信息，但没有看到任何与此确切问题相关的信息。我知道 LCG 算法存在很多问题，但我不知道这个问题，我想知道这是否是一个已知问题。

而且，您是否知道这个问题是否仅针对第一个值（或前几个值），或者它是否更普遍并且应该避免使用紧密种子？

谢谢。

4

4 回答 4

20

最好下载和阅读Random源代码以及一些关于伪随机生成器的论文，但这里是源代码的一些相关部分。首先，控制算法的三个常数参数：

private final static long multiplier = 0x5DEECE66DL;
private final static long addend = 0xBL;
private final static long mask = (1L << 48) - 1;

乘数约为 2^34 并更改，掩码 2^48 - 1，对于此分析，加数非常接近 0。

当您使用种子创建 Random 时，构造函数会调用setSeed：

synchronized public void setSeed(long seed) {
    seed = (seed ^ multiplier) & mask;
    this.seed.set(seed);
    haveNextNextGaussian = false;
}

您提供的种子非常接近于零，因此设置的初始种子值取决于multiplier两者的 OR'ed 时间。在种子接近于零的所有测试用例中，内部使用的种子大约为 2^34；但是很容易看出，即使您提供了非常大的种子数量，类似的用户提供的种子也会产生类似的内部种子。

最后一块是next(int)方法，它实际上是根据当前种子生成请求长度的随机整数，然后更新种子：

protected int next(int bits) {
    long oldseed, nextseed;
    AtomicLong seed = this.seed;
    do {
    oldseed = seed.get();
    nextseed = (oldseed * multiplier + addend) & mask;
    } while (!seed.compareAndSet(oldseed, nextseed));
    return (int)(nextseed >>> (48 - bits));
}

这被称为“线性同余”伪随机生成器，这意味着它通过将当前种子乘以一个常数乘数然后加上一个常数加数来生成每个连续的种子（在这种情况下，然后屏蔽以获取低 48 位） . 生成器的质量取决于乘法器和加法器的选择，但是所有此类生成器的输出都可以根据当前输入轻松预测，并且在重复之前有一个设定的周期（因此建议不要在敏感的情况下使用它们）应用程序）。

您看到nextDouble给定相似种子的相似初始输出的原因是，因为下一个整数的计算只涉及乘法和加法，所以下一个整数的大小受低位差异的影响不大。下一个 double 的计算涉及基于种子计算一个大整数并将其除以另一个（常数）大整数，结果的大小主要受整数大小的影响。

下一个种子的重复计算将放大种子低位的差异，因为重复乘以常数乘数，并且因为 48 位掩码每次都会抛出最高位，直到最终你看到看起来像甚至传播。

于 2012-09-05T15:04:55.377 回答
4

我不会称这是一个“问题”。

而且，您是否知道这个问题是否仅针对第一个值（或前几个值），或者它是否更普遍并且应该避免使用紧密种子？

连续数字之间的相关模式是非加密 PRNG 的常见问题，这只是一种表现形式。相关性（严格的自相关性）是算法所依据的数学中固有的。如果您想理解这一点，您可能应该从阅读 Knuth 的计算机编程艺术第 3 章的相关部分开始。

如果您需要不可预测性，您应该使用（真正的）随机种子Random......或者让系统为您选择一个“相当随机”的种子；例如使用无参数构造函数。或者更好的是，使用真正的随机数源或加密质量 PRNG 而不是Random.

作为记录：

  1. javadoc (Java 7) 没有指定 Random() 本身是如何播种的。
  2. 在 Java 7 for Linux 上的实现Random()是从纳秒时钟中播种的，与“唯一符”序列进行异或运算。'uniquifier' 序列是使用不同乘数的 LCG，其状态是静态的。这是为了避免种子的自相关......
于 2012-09-05T13:44:30.893 回答
2

对于伪随机种子来说，这是一种相当典型的行为——它们不需要提供完全不同的随机序列，它们只提供保证，如果你使用相同的种子，你可以再次获得相同的序列。

这种行为是由于 PRNG 的数学形式而发生的——Java 使用线性同余生成器，因此您只是看到通过一轮线性同余生成器运行种子的结果。这不足以完全混合所有位模式，因此您会看到类似种子的类似结果。

您最好的策略可能只是使用非常不同的种子 - 一种选择是通过散列您当前使用的种子值来获得这些种子。

于 2012-09-05T13:46:43.920 回答
-1

通过制作随机种子（例如，使用 System.currentTimeMillis() 或 System.nanoTime() 上的一些数学函数来生成种子），您可以获得更好的随机结果。也可以在这里查看更多信息

于 2012-09-05T13:44:04.190 回答