跳到主要内容

JEP 356：增强的伪随机数生成器

QWen Max 中英对照 JEP 356: Enhanced Pseudo-Random Number Generators

总结​

为伪随机数生成器（PRNG）提供新的接口类型和实现，包括可跳跃的 PRNG 和一类额外的可拆分 PRNG 算法（LXM）。

目标​

  • 让应用程序中更容易互换使用各种 PRNG 算法。
  • 通过提供 PRNG 对象流，更好地支持基于流的编程。
  • 消除现有 PRNG 类中的代码重复。
  • 小心保留类 java.util.Random 的现有行为。

非目标​

我们的目标并不是实现众多其它的 PRNG 算法，而是提供一个可以容纳其它 PRNG 算法的框架。不过，我们已经添加了三个在其它编程语言环境中广泛使用的通用算法。

成功指标​

新的 LXM 算法的输出通过了现有的知名 TestU01 和 PractRand 测试套件。

可跳跃和可跃迁的 PRNG 算法通过了验证某些操作的可交换性的测试。

动机​

我们专注于 Java 中伪随机数生成器领域的五个改进方面：

  • 对于传统的 PRNG 类 Random、ThreadLocalRandom 和 SplittableRandom，尽管它们都支持几乎相同的方法集，但在应用程序中很难用其他算法替换其中任何一个。例如，如果一个应用程序使用了类 Random 的实例，那么它必然会声明类型为 Random 的变量，而这些变量无法容纳类 SplittableRandom 的实例；要将应用程序更改为使用 SplittableRandom，则需要更改每个用于保存 PRNG 对象的变量（包括方法参数）的类型。唯一的例外是 ThreadLocalRandom 是 Random 的子类，纯粹是为了允许类型为 Random 的变量容纳 ThreadLocalRandom 的实例，但 ThreadLocalRandom 几乎重写了 Random 的所有方法。接口可以轻松解决这个问题。

  • 传统类 Random、ThreadLocalRandom 和 SplittableRandom 都支持诸如 nextDouble() 和 nextBoolean() 等方法以及生成流的方法如 ints() 和 longs()，但它们具有完全独立且几乎复制粘贴相同的实现。重构此代码将使其更易于维护，此外，文档化将使第三方更容易创建也支持相同完整方法套件的新 PRNG 类。

  • 在 2016 年，测试揭示了类 SplittableRandom 所使用的算法存在两个新的弱点。一方面，一个相对较小的修订可以避免这些弱点。另一方面，还发现了一类新的可拆分 PRNG 算法（LXM），它们几乎同样快速，甚至更易于实现，并且似乎完全避免了 SplittableRandom 易受的三类弱点。

  • 能够从 PRNG 获取 PRNG 对象的流，这使得使用流方法表达某些类型的代码变得更加容易。

  • 文献中有许多不可拆分但可跳跃（或许还可大步跳跃，即能够进行非常长的跳跃以及普通跳跃）的 PRNG 算法，这一特性与拆分类似，但完全不同，不过同样适用于支持 PRNG 对象的流。过去，在 Java 中利用这一特性一直很困难。可跳跃 PRNG 算法的例子有 Xoshiro256** 和 Xoroshiro128+。

描述​

我们提供了一个新的接口 RandomGenerator，它为所有现有的和新的伪随机数生成器（PRNG）提供了一个统一的 API。RandomGenerator 提供了名为 ints、longs、doubles、nextBoolean、nextInt、nextLong、nextDouble 和 nextFloat 的方法，并且包含了它们当前所有的参数变体。

我们提供了四个新的专用 RandomGenerator 接口：

  • SplittableRandomGenerator 扩展了 RandomGenerator，还提供了名为 split 和 splits 的方法。可拆分性允许用户从现有的 RandomGenerator 中生成一个新的 RandomGenerator，通常会产生统计学上独立的结果。

  • JumpableRandomGenerator 扩展了 RandomGenerator，还提供了名为 jump 和 jumps 的方法。可跳跃性允许用户向前跳过适量的抽取次数。

  • LeapableRandomGenerator 扩展了 RandomGenerator，还提供了名为 leap 和 leaps 的方法。可大步跳跃性允许用户向前跳过大量的抽取次数。

  • ArbitrarilyJumpableRandomGenerator 扩展了 LeapableRandomGenerator，还提供了额外的 jump 和 jumps 方法变体，允许指定任意的跳跃距离。

我们提供了一个新的类 RandomGeneratorFactory，用于定位和构建 RandomGenerator 实现的实例。RandomGeneratorFactory 使用 ServiceLoader.Provider API 来注册 RandomGenerator 的实现。

我们已经重构了 Random、ThreadLocalRandom 和 SplittableRandom，以便共享它们的大部分实现代码，并且进一步使这些代码也能被其他算法复用。这次重构创建了一些底层的非公共抽象类：AbstractRandomGenerator、AbstractSplittableRandomGenerator、AbstractJumpableRandomGenerator、AbstractLeapableRandomGenerator 和 AbstractArbitrarilyJumpableRandomGenerator，每个类仅提供 nextInt()、nextLong() 方法的实现，以及（如果相关）split() 或 jump() 或 jump() 和 leap() 或 jump(distance) 的实现。在这次重构之后，Random、ThreadLocalRandom 和 SplittableRandom 继承了 RandomGenerator 接口。需要注意的是，由于 SecureRandom 是 Random 的子类，所有 SecureRandom 的实例也自动支持 RandomGenerator 接口，无需对 SecureRandom 类或其任何相关的实现引擎进行重新编码。

我们还添加了扩展 AbstractSplittableRandomGenerator 的底层非公共类（因此实现了 SplittableRandomGenerator 和 RandomGenerator），以支持 LXM 系列 PRNG 算法中的六个特定成员：

  • L32X64MixRandom
  • L32X64StarStarRandom
  • L64X128MixRandom
  • L64X128StarStarRandom
  • L64X256MixRandom
  • L64X1024MixRandom
  • L128X128MixRandom
  • L128X256MixRandom
  • L128X1024MixRandom

LXM 算法的中央 nextLong（或 nextInt）方法的结构遵循 Sebastiano Vigna 在 2017 年 12 月提出的一个建议，即使用一个 LCG 子生成器和一个基于异或的子生成器（而不是两个 LCG 子生成器）可以提供更长的周期、更优的均匀分布性、可扩展性以及更好的质量。这里的每个具体实现都将目前已知的最佳基于异或的生成器之一（xoroshiro 或 xoshiro，由 Blackman 和 Vigna 在《Scrambled Linear Pseudorandom Number Generators》，ACM Trans. Math. Softw.，2021 中描述）与一个使用目前已知最佳乘数之一的 LCG（由 Steele 和 Vigna 在 2019 年通过寻找更优乘数发现）相结合，然后应用 Doug Lea 提出的混合函数。测试已经证实，LXM 算法在质量上远优于 SplittableRandom 使用的 SplitMix 算法（2014）。

我们还提供了这些广泛使用的 PRNG 算法的实现：

  • Xoshiro256PlusPlus
  • Xoroshiro128PlusPlus

上面提到的非公共抽象实现未来可能会作为随机数实现者 SPI 的一部分提供。

这套算法为 Java 程序员提供了一系列在空间、时间、质量以及与其他语言的兼容性之间的合理权衡。

替代方案​

我们考虑过简单地引入新接口，同时保持 Random、ThreadLocalRandom 和 SplittableRandom 的实现不变。这将有助于使 PRNG 对象更易于互换，但不会使它们的实现变得更容易。

我们考虑在不改变 Random、ThreadLocalRandom 和 SplittableRandom 的功能或添加任何新接口的情况下对其进行重构。我们认为这将减少它们的整体内存占用，但无助于让未来的 PRNG 算法更容易实现或使用。

测试​

  • Random、ThreadLocalRandom 和 SplittableRandom 的所有现有测试
    应继续使用。

  • 新测试，可能仅需应用一次：重构后的 Random、ThreadLocalRandom 和 SplittableRandom 版本（在修复两个新发现的弱点之前）的输出应与现有的（JDK 8）实现进行抽查对比，以验证其行为保持不变。

  • 新测试，可能仅需应用一次：LXM 算法的输出应与用于 TestU01 和 PractRand 质量验证的 C 语言版本进行抽查对比。

  • 新测试，将成为测试套件的永久部分：应对 jump() 和 leap() 方法进行测试，以验证它们是否确实按照声称的距离遍历状态周期。例如，从任何特定的初始状态开始，操作序列 nextLong(); jump() 应使生成器的状态与操作序列 jump(); nextLong() 的最终状态相同。

风险与假设​

我们相信这是一个中型项目，风险极小。可能最大的负担是制定规范，第二大负担是测试。

为了确保旧版随机数生成器的行为未受影响，已投入了大量精力。