Provide new interface types and implementations for pseudorandom number generators (PRNGs), including jumpable PRNGs and an additional class of splittable PRNG algorithms (LXM).
- Make it easier to use various PRNG algorithms interchangeably in applications.
- Better support stream-based programming by providing streams of PRNG objects.
- Eliminate code duplication in existing PRNG classes.
- Carefully preserve existing behavior of class
It is not a goal to provide implementations of numerous other PRNG algorithms, only to provide a framework that can accommodate other PRNG algorithms. However, we have added three common algorithms that have already been widely deployed in other programming language environments.
The output of the new LXM algorithms passes the existing well-known TestU01 and PractRand test suites.
Pierre L'Ecuyer and Richard Simard. TestU01: A C Library for Empirical Testing of Random Number Generators. ACM Transactions on Mathematical Software 33, 4 (August 2007), article 22. ISSN 0098-3500. http://doi.acm.org/10.1145/1268776.1268777
Richard Simard. TestU01 version 1.2.3 (August 2009). http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
Pierre L'Ecuyer and Richard Simard. TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators: User's guide, compact version. Département d'Informatique et de Recherche Opérationnelle, Univerité de Montréal, May 2013. http://www.iro.umontreal.ca/~simardr/testu01/guideshorttestu01.pdf
Chris Doty-Humphrey. PractRand version 0.90. July 2014. http://pracrand.sourceforge.net [That's not a typo. The name of the software is "PractRand"
but the SourceForge project name is "pracrand".]
Jumpable and leapable PRNG algorithms pass tests that verify the commutativity of certain operations.
We focus on five areas for improvement in the area of pseudorandom number generators in Java:
With the legacy PRNG classes
SplittableRandom, it is difficult to replace any one of them in an application with some other algorithm, despite the fact that they all support pretty much the same set of methods. For example, if an application uses instances of class
Random, it will necessarily declare variables of type
Random, which cannot hold instances of class
SplittableRandom; changing the application to use
SplittableRandomwould require changing the type of every variable (including method parameters) used to hold a PRNG object. The one exception is that
ThreadLocalRandomis a subclass of
Random, purely to allow variables of type
Randomto hold instances of
ThreadLocalRandomoverrides nearly all the methods of
Random. Interfaces can easily address this.
SplittableRandomall support such methods as
nextBoolean()as well as stream-producing methods such as
longs(), but they have completely independent and nearly copy-and-paste identical implementations. Refactoring this code would made it easier to maintain and, moreover, documentation would makes it much easier for third parties to create new PRNG classes that also support the same complete suite of methods.
In 2016, testing revealed two new weaknesses in the algorithm used by class
SplittableRandom. On the one hand, a relatively minor revision can avoid those weaknesses. On the other hand, a new class of splittable PRNG algorithms (LXM) has also been discovered that are almost as fast, even easier to implement, and appear to completely avoid the three classes of weakness to which
Being able to obtain a stream of PRNG objects from a PRNG makes it much easier to express certain sorts of code using streaming methods.
There are many PRNG algorithms in the literature that are not splittable but are jumpable (and perhaps also leapable, that is, capable of very long jumps as well as ordinary jumps), a property quite different from splitting that nevertheless also lends itself to supporting streams of PRNG objects. In the past, it has been difficult to take advantage of this property in Java. Examples of jumpable PRNG algorithms are Xoshiro256**, and Xoroshiro128+.
- Xoshiro256** and Xoroshiro128+: http://xoshiro.di.unimi.it
We provide a new interface,
RandomGenerator, which supplies a
uniform API for all existing and new PRNGs.
nextFloat, with all their current parameter variations.
We provide four new specialized RandomGenerator interfaces:
RandomGeneratorand also provides
splits. Splittability allows the user to spawn a new RandomGenerator from an existing RandomGenerator that will generally produce statistically independent results.
RandomGeneratorand also provides
jumps. Jumpability allows a user to jump ahead a moderate number of draws.
RandomGeneratorand also provides
leaps. Leapability allows a user to jump ahead a large number of draws.
LeapableRandomGeneratorand also provides additional variations of
jumpsthat allow an arbitrary jump distance to be specified.
We provide a new class
RandomGeneratorFactory which is used to
locate and construct instances of
RandomGenerator implementations. The
RandomGeneratorFactory uses the
ServiceLoader.Provider API to register
We have refactored
as to share most of their implementation code and, furthermore, make that code
reusable by other algorithms as well. This refactoring creates underlying non-public
AbstractArbitrarilyJumpableRandomGenerator, each provide only implementations
nextLong(), and (if relevant) either
jump(distance). After this refactoring,
SplittableRandom inherit the
RandomGenerator interface. Note that because
SecureRandom is a subclass of
Random, all instances of
SecureRandom also automatically support the
RandomGenerator interface, with no need to recode the
or any of its associated implementation engines.
We also added underlying non-public classes that extend
(and therefore implement
support six specific members of the LXM family of PRNG algorithms:
The structure of the central nextLong (or nextInt) method of an LXM algorithm follows a suggestion in December 2017 by Sebastiano Vigna that using one LCG subgenerator and one xor-based subgenerator (rather than two LCG subgenerators) would provide a longer period, superior equidistribution, scalability, and better quality. Each of the specific implementations here combines one of the best currently known xor-based generators (xoroshiro or xoshiro, described by Blackman and Vigna in "Scrambled Linear Pseudorandom Number Generators", ACM Trans. Math. Softw., 2021) with an LCG that uses one of the best currently known multipliers (found by a search for better multipliers in 2019 by Steele and Vigna), and then applies a mixing function identified by Doug Lea. Testing has confirmed that the LXM algorithm is far superior in quality to the SplitMix algorithm (2014) used by SplittableRandom.
We also provide implementations of these widely-used PRNG algorithms:
The non-public abstract implementations mentioned above may be supplied as part of a random number implementor SPI in the future.
This suite of algorithms provide Java programmers with a reasonable range of tradeoffs among space, time, quality, and compatibility with other languages.
We considered simply introducing new interfaces while leaving the
SplittableRandom as is.
This would help to make PRNG objects more easily interchangeable but would not
make it any easier to implement them.
We considered refactoring
without changing their functionality or adding any new interfaces. We believe
this would reduce their overall memory footprint, but do nothing to make future
PRNG algorithms easier to implement or use.
All existing tests for
should continue to be used.
New test, probably to be applied just once: The output of the refactored
repairing the two newly detected weaknesses) should be spot-checked against the existing (JDK 8) implementations to verify that their behavior remains
New test, probably to be applied just once: The output of the LXM algorithms
should be spot-checked against the C-coded versions used for quality
verification with TestU01 and PractRand.
New test, to become a permanent part of the test suite: The
leap()methods should be tested to verify that they do travel around the state cycle by the claimed distance. For example, starting from any specific initial state, the sequence of operations
nextLong(); jump()ought to leave a
generator in the same state as the sequence of operations
Risks and Assumptions
We believe this is a medium project and the risks are minimal. Probably
the largest burden has been crafting the specification and the second-largest has been testing.
Care has been give to ensure the behaviour of legacy random number generators has not been affected.