Java 中 setSeed 之后的第一个随机数总是相似的

Question

为了提供一些背景信息，我一直在 Java 中编写一个基本的 Perlin 噪声实现，而在实现播种时，我遇到了一个我无法解释的错误。

为了无论查询哪组坐标的噪声水平以及以什么顺序每次都为相同的种子生成相同的随机权重向量，我生成了一个新的种子（newSeed），基于在原始种子和权重向量坐标的组合上，并将其用作权重向量随机化的种子运行ning:

rnd.setSeed(newSeed);
weight = new NVector(2);
weight.setElement(0, rnd.nextDouble() * 2 - 1);
weight.setElement(1, rnd.nextDouble() * 2 - 1);
weight.normalize()

其中 NVector 是矢量数学的 self-made class。

然而，当运行时，程序产生了非常糟糕的噪音：

经过一些挖掘，我发现每个向量的第一个元素非常相似（因此每个 setSeed() 调用之后的第一个 nextDouble() 调用）导致每个向量的第一个元素在矢量网格相似。

这可以通过运行ning证明：

long seed = Long.valueOf(args[0]);
int loops = Integer.valueOf(args[1]);
double avgFirst = 0.0, avgSecond = 0.0, avgThird = 0.0;
double lastfirst = 0.0, lastSecond = 0.0, lastThird = 0.0;
for(int i = 0; i<loops; i++)
{
    ran.setSeed(seed + i);
    double first = ran.nextDouble();
    double second = ran.nextDouble();
    double third = ran.nextDouble();
    avgFirst += Math.abs(first - lastfirst);
    avgSecond += Math.abs(second - lastSecond);
    avgThird += Math.abs(third - lastThird);
    lastfirst = first;
    lastSecond = second;
    lastThird = third;
}
System.out.println("Average first difference.: " + avgFirst/loops);
System.out.println("Average second Difference: " + avgSecond/loops);
System.out.println("Average third Difference.: " + avgSecond/loops);

计算在程序参数指定的种子范围内调用 setSeed() 方法后生成的第一个、第二个和第三个随机数之间的平均差；这对我来说返回了这些结果：

C:\java Test 462454356345 10000
Average first difference.: 7.44638117976783E-4
Average second Difference: 0.34131692827329957
Average third Difference.: 0.34131692827329957

C:\java Test 46245445 10000
Average first difference.: 0.0017196011123287126
Average second Difference: 0.3416750057190849
Average third Difference.: 0.3416750057190849

C:\java Test 1 10000
Average first difference.: 0.0021601598225344998
Average second Difference: 0.3409914232342002
Average third Difference.: 0.3409914232342002

在这里您可以看到第一个平均差异明显小于其余差异，并且似乎随着种子数的增加而减少。

因此，通过在设置权重向量之前向 nextDouble() 添加一个简单的虚拟调用，我能够修复我的 perlin 噪声实现：

rnd.setSeed(newSeed);
rnd.nextDouble();
weight.setElement(0, rnd.nextDouble() * 2 - 1);
weight.setElement(1, rnd.nextDouble() * 2 - 1);

导致：

我想知道为什么在第一次调用 nextDouble() 时出现这种不良变化（我没有检查其他类型的随机性）and/or 以提醒人们注意这个问题。

当然，这可能只是我的执行错误，如果能向我指出，我将不胜感激。

Answer 1

将你的 setSeed 移出循环。 Java 的 PRNG 是一个线性同余生成器，因此使用顺序值对其进行播种可以保证给出在循环迭代之间相关的结果。

附录

我在运行出门开会之前就把它搞砸了，现在有时间来说明我上面所说的内容。

我写了一个小 Ruby 脚本，它实现了 Schrage 的便携式质数模乘线性同余生成器。我实例化了 LCG 的两个副本，两个副本的种子值为 1。但是，在输出循环的每次迭代中，我根据循环索引重新为第二个副本播种。这是代码：

# Implementation of a Linear Congruential Generator (LCG)
class LCG
  attr_reader :state
  M = (1 << 31) - 1    # Modulus = 2**31 - 1, which is prime

  # constructor requires setting a seed value to use as initial state
  def initialize(seed)
    reseed(seed)
  end

  # users can explicitly reset the seed.
  def reseed(seed)
    @state = seed.to_i
  end

  # Schrage's portable prime modulus multiplicative LCG
  def value
    @state = 16807 * @state % M
    # return the generated integer value AND its U(0,1) mapping as an array
    [@state, @state.to_f / M]
  end
end

if __FILE__ == [=10=]
  # create two instances of LCG, both initially seeded with 1
  mylcg1 = LCG.new(1)
  mylcg2 = LCG.new(1)
  puts "   default progression     manual reseeding"
  10.times do |n|
    mylcg2.reseed(1 + n)  # explicitly reseed 2nd LCG based on loop index
    printf "%d %11d %f %11d %f\n", n, *mylcg1.value, *mylcg2.value
  end
end

这是它产生的输出：

   default progression     manual reseeding
0       16807 0.000008       16807 0.000008
1   282475249 0.131538       33614 0.000016
2  1622650073 0.755605       50421 0.000023
3   984943658 0.458650       67228 0.000031
4  1144108930 0.532767       84035 0.000039
5   470211272 0.218959      100842 0.000047
6   101027544 0.047045      117649 0.000055
7  1457850878 0.678865      134456 0.000063
8  1458777923 0.679296      151263 0.000070
9  2007237709 0.934693      168070 0.000078

这些列是迭代次数，后跟 LCG 生成的基础整数和缩放到范围 (0,1) 时的结果。左侧的一组列显示了 LCG 在允许其自行进行时的自然进展，而右侧的一组显示了在每次迭代中重新播种时发生的情况。

Answer 2

这是已知问题。相似的种子将生成相似的少数第一值。 Random 并不是真正设计为以这种方式使用。您应该使用良好的种子创建实例，然后生成中等大小的 "random" 数字序列。

您当前的解决方案是可以的 - 只要它看起来不错并且速度足够快。您还可以考虑使用旨在解决您的问题的 hashing/mixing 函数（然后，可以选择使用输出作为种子）。例如参见：Parametric Random Function For 2D Noise Generation

Answer 3

Random class 被设计成一个低开销的伪随机数源。但是 "low overhead" 实现的结果是数字流的属性远非完美......从统计的角度来看。您遇到了其中一个缺陷。 Random 被记录为线性同余生成器，此类生成器的属性众所周知。

有多种处理方法。例如，如果你小心，你可以隐藏一些最明显的 "poor" 特征。（但是建议您运行进行一些统计测试。您看不到添加到第二张图像的噪声中的非随机性，但它可能仍然存在。）

或者，如果您想要具有良好统计特性的伪随机数，那么您应该使用 SecureRandom 而不是 Random。它的开销要高得多，但您可以放心，许多 "smart people" 将花费大量时间在算法的设计、测试和分析上。

最后，创建 Random 的子class 相对简单，它使用替代算法生成数字；参见 link。问题是您必须select（或设计）并实施适当的算法。

将此称为“问题”是值得商榷的。它是 LCG 的众所周知和理解的属性，使用 LCG 是一种有意识的工程选择。人们想要低开销的 PRNG，但低开销的 PRNG 的性能很差。 TANSTAAFL.

当然，Oracle 不会考虑在 Random 中进行更改。事实上，Random class.

javadoc 中明确说明了不更改的原因。

"In order to guarantee this property, particular algorithms are specified for the class Random. Java implementations must use all the algorithms shown here for the class Random, for the sake of absolute portability of Java code."

Java 中 setSeed 之后的第一个随机数总是相似的

First random number after setSeed in Java always similar

java

random

noise