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

概括

为伪随机数生成器 (PRNG) 提供新的接口类型和实现，包括可跳转的 PRNG 和一类附加的可拆分 PRNG 算法 (LXM)。

目标

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

非目标

提供众多其他 PRNG 算法的实现并不是目标，只是提供一个可以容纳其他 PRNG 算法的框架。但是，我们添加了三种已在其他编程语言环境中广泛部署的常见算法。

成功指标

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

• 皮埃尔·勒埃库耶和理查德·西马德。 TestU01：用于随机数生成器实证测试的 AC 库。_ACM 数学软件汇刊_33, 4（2007 年 8 月），文章 22。ISSN 0098-3500。http://doi.acm.org/10.1145/1268776.1268777

• 理查德·西马德. TestU01 版本 1.2.3（2009 年 8 月）。http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

• 皮埃尔·勒埃库耶和理查德·西马德。TestU01：用于随机数生成器实证测试的 ANSI C 软件库：用户指南，精简版。蒙特利尔大学信息与运营研究部，2013 年 5 月。http ://www.iro.umontreal.ca/~simardr/testu01/guideshorttestu01.pdf

• 克里斯·多蒂-汉弗莱。 PractRand 版本 0.90。 2014 年 7 月。http ://pracrand.sourceforge.net [这不是拼写错误。该软件的名称是“PractRand”，但 SourceForge 项目名称是“pracrand”。]

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

动机

我们重点关注 Java 伪随机数生成器领域的五个需要改进的领域：

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

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

• 2016 年，测试揭示了 class 使用的算法中的两个新弱点SplittableRandom。一方面，相对较小的修改可以避免这些弱点。另一方面，还发现了一类新的可分割 PRNG 算法 (LXM)，它几乎同样快，甚至更容易实现，并且似乎完全避免了SplittableRandom容易出现的三类弱点。

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

• 文献中有许多不可分割但可跳跃的 PRNG 算法（也许也是可跳跃的，即能够进行很长的跳跃以及普通的跳跃），这种属性与分割完全不同，但也适合支持流PRNG 对象的数量。过去，在Java中很难利用这个特性。可跳转 PRNG 算法的示例有 Xoshiro256** 和 Xoroshiro128+。

  • Xoshiro256** 和 Xoroshiro128+：http://xoshiro.di.unimi.it

描述

我们提供了一个新的接口，RandomGenerator它为所有现有的和新的 PRNG 提供统一的 API。RandomGenerators提供名为ints、longs、doubles、nextBoolean、nextInt、nextLong、nextDouble和 的方法nextFloat及其所有当前参数变化。

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

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

• JumpableRandomGenerator扩展RandomGenerator并还提供了名为和 的
  方法。跳跃性允许用户向前跳跃适度的抽奖次数。jump``jumps

• LeapableRandomGenerator扩展RandomGenerator并还提供了名为和 的
  方法。跳跃性允许用户跳过大量抽奖。leap``leaps

• ArbitrarilyJumpableRandomGenerator扩展LeapableRandomGenerator并且还提供了jump和的附加变体jumps，允许指定任意跳跃距离。

我们提供了一个新类RandomGeneratorFactory，用于定位和构造RandomGenerator实现的实例。使用RandomGeneratorFactoryAPIServiceLoader.Provider来注册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

• 新测试，可能只应用一次：、、 和
  的重构版本的输出（在 修复两个新检测到的弱点之前）应该针对现有 (JDK 8) 实现进行抽查，以验证其行为是否保持 不变。Random``ThreadLocalRandom``SplittableRandom

• 新测试，可能只应用一次：LXM 算法的输出
  应根据用于
  TestU01 和 PractRand 质量验证的 C 编码版本进行抽查。

• 新测试，成为测试套件的永久部分：应该测试jump()和
  leap()方法，以验证它们确实按照声明的距离围绕状态循环行进。例如，从任何特定的初始状态开始，操作序列nextLong(); jump()应该使
  生成器处于与操作序列相同的状态jump(); nextLong()。

风险和假设

我们认为这是一个中等项目，风险很小。也许
最大的负担是制定规范，第二大负担是测试。

我们已尽力确保传统随机数生成器的行为不受影响。