问题描述
我发现使用 Java 的 Random 类生成随机数时有些奇怪.基本上，如果您使用相近的种子(例如在 1 到 1000 之间)创建多个 Random 对象，则每个生成器生成的第一个值几乎相同，但接下来的值看起来不错(我没有进一步搜索).
I discovered something strange with the generation of random numbers using Java's Random class. Basically, if you create multiple Random objects using close seeds (for example between 1 and 1000) the first value generated by each generator will be almost the same, but the next values looks fine (i didn't search further).
以下是最初生成的两个双打，种子从 0 到 9 :
Here are the two first generated doubles with seeds from 0 to 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 :
And from 991 to 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 的种子生成的第一个值.
And here is a figure showing the first value generated with seeds from 0 to 100,000.
基于种子生成的第一个随机双:
First random double generated based on the seed :
我搜索了有关此问题的信息，但没有看到任何与此确切问题相关的内容.我知道 LCG 算法有很多问题，但我不知道这个问题，我想知道这是否是一个已知问题.
I searched for information about this, but I didn't see anything referring to this precise problem. I know that there is many issues with LCGs algorithms, but I didn't know about this one, and I was wondering if this was a known issue.
此外，您是否知道这个问题是否仅针对第一个值(或前几个值)，或者是否更普遍并且应该避免使用密种子?
And also, do you know if this problem only for the first value (or first few values), or if it is more general and using close seeds should be avoided?
谢谢.
推荐答案
您最好下载并阅读 Random 源代码，以及一些关于伪随机生成器的论文，但是这是源代码的一些相关部分.首先，有三个控制算法的常量参数:
You'd be best served by downloading and reading the Random source, as well as some papers on pseudo-random generators, but here are some of the relevant parts of the source. To begin with, there are three constant parameters that control the algorithm:
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.
The multiplier works out to approximately 2^34 and change, the mask 2^48 - 1, and the addend is pretty close to 0 for this analysis.
当你创建一个带有种子的 Random 时，构造函数调用 setSeed:
When you create a Random with a seed, the constructor calls setSeed:
synchronized public void setSeed(long seed) {
seed = (seed ^ multiplier) & mask;
this.seed.set(seed);
haveNextNextGaussian = false;
}
您提供的种子非常接近于零，因此当两者进行 OR 运算时，设置的初始种子值由 multiplier 支配.在所有种子接近于零的测试用例中，内部使用的种子大约是 2^34；但很容易看出，即使您提供了非常大的种子数，类似的用户提供的种子也会产生类似的内部种子.
You're providing a seed pretty close to zero, so initial seed value that gets set is dominated by multiplier when the two are OR'ed together. In all your test cases with seeds close to zero, the seed that is used internally is roughly 2^34; but it's easy to see that even if you provided very large seed numbers, similar user-provided seeds will yield similar internal seeds.
最后一块是next(int)方法，它实际上根据当前种子生成一个请求长度的随机整数，然后更新种子:
The final piece is the next(int) method, which actually generates a random integer of the requested length based on the current seed, and then updates the seed:
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 位，在这个案例).生成器的质量由乘法器和加数的选择决定，但是可以根据当前输入轻松预测所有此类生成器的输出，并且在重复之前有一段设定的时间(因此建议不要在敏感的情况下使用它们)应用程序).
This is called a 'linear congruential' pseudo-random generator, meaning that it generates each successive seed by multiplying the current seed by a constant multiplier and then adding a constant addend (and then masking to take the lower 48 bits, in this case). The quality of the generator is determined by the choice of multiplier and addend, but the ouput from all such generators can be easily predicted based on the current input and has a set period before it repeats itself (hence the recommendation not to use them in sensitive applications).
在给定类似种子的情况下，您看到 nextDouble 的类似初始输出的原因是，由于下一个整数的计算仅涉及乘法和加法，因此下一个整数的大小并不多受低位差异的影响.下一个double的计算涉及基于种子计算一个大整数并除以另一个(常数)大整数，结果的大小主要受整数大小的影响.
The reason you're seeing similar initial output from nextDouble given similar seeds is that, because the computation of the next integer only involves a multiplication and addition, the magnitude of the next integer is not much affected by differences in the lower bits. Calculation of the next double involves computing a large integer based on the seed and dividing it by another (constant) large integer, and the magnitude of the result is mostly affected by the magnitude of the integer.
下一个种子的重复计算会放大种子低位的差异，因为重复乘以常数乘法器，并且因为48位掩码每次都抛出最高位，直到最终你看到了什么看起来是均匀分布.
Repeated calculations of the next seed will magnify the differences in the lower bits of the seed because of the repeated multiplication by the constant multiplier, and because the 48-bit mask throws out the highest bits each time, until eventually you see what looks like an even spread.
这篇关于为什么使用相似种子时初始随机数相似?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，WP2