Xorshift RNG 对于蒙特卡洛方法是否足够好?如果不是,有什么替代品?

机器算法验证 随机生成 爪哇
2022-03-07 19:55:08

我最近偶然发现了一篇关于 Java 中伪随机数的文章,其中提到了默认算法中的潜在弱点,称为线性同余生成器 (LCG),并提供了一些替代方案其中我发现Xorshift 生成器很有趣。所以我戴上我的研究员的帽子,潜入寻找更多信息。

事实证明,它实现起来非常简单,运行时速度非常快,听起来很棒。问题是该方法是否比默认的 LCG 算法有显着的改进。为了弄清楚这一点,我通读了Marsaglia 介绍该方法的原始论文,以及Panneton 和 L'ecuyer的相当严厉的批评/分析我不能声称我一直遵循数学,所以我不确定该方法是否比 LCG 更上一层楼,这让我想到了我的第一个问题:

问题 1: Xorshift 是否比java 使用的基于 LCG 的默认 RNG更上一层楼?

Panneton 和 L'ecuyer 提出了参数选择的问题,并指出仅 3 位移位可能还不够。我最近对哈希函数进行了一些研究(这是我在 StackOverflow 上提出的一个相关问题)。我想知道是否可以通过这样的方式改进 3-bitshift 方法?

long lhash = prime * (hash1 ^ hash2);然后使用(int)((lhash >> 32) ^ lhash)

根据@whuber 的评论,更改 RNG 的具体细节是一件棘手的事情,因此这可能会很棘手,但我会很感激任何关于如何修正 Xorshift RNG 中的弱点的想法/线索。问题2:可以做些什么来提高Xorshift算法的“整体性能”?(请注意,我在这里不是指计算性能)

最后一点,我想做的是生成伪随机 Gussians,以模拟类型的数字,其中的高斯。出于这个原因,我不太热衷于添加依赖项,而且我还认为在这一点上使用SecureRandom有点矫枉过正。erandrandN(0,σ)

1个回答

http://prng.di.unimi.it/,您可以找到使用 TestU01 测试的几个随机数生成器的枪战,TestU01 是用于取代顽固和顽固的伪随机数生成器的现代测试套件。

Java LCG 生成器不可用。你应该像避免瘟疫一样避免它。xorshift 生成器更好,但仍会显示几个统计工件。Marsaglia 在他的原始论文中建议将 xorshift 生成器的结果乘以一个常数以提高统计质量,结果就是 xorshift* 生成器。这些是一些最快的高质量发电机,特别是如果周期相当大。

使用 SecureRandom 生成大量随机位是极其危险的。在几十万次调用(或更少)之后,您的应用程序将停止(至少在 Linux 上)等待 /dev/random 提供更多真正的随机位。如果您不知道,调试将是一场噩梦——应用程序将毫无理由地挂起并使用 0% 的 CPU。