Better Splittable Pseudorandom Number Generators (and Almost As Fast)April 2017We have tested and analyzed the {\sc SplitMix} pseudorandom number generator algorithm
presented by Steele, Lea, and Flood \citeyear{FAST-SPLITTABLE-PRNG}, and have discovered two additional classes
of gamma values that produce weak pseudorandom sequences. In this paper we
present a modification to the {\sc SplitMix} algorithm
that avoids all three classes of problematic gamma values,
and also a completely new algorithm for splittable pseudorandom number generators,
which we call {\sc TwinLinear}.
Like {\sc SplitMix}, {\sc TwinLinear} provides both a \emph{generate}
operation that returns one (64-bit) pseudorandom value and a \emph{split} operation
that produces a new generator instance that with very high probability
behaves as if statistically independent of all other instances.
Also like {\sc SplitMix}, {\sc TwinLinear} requires no locking or other synchronization
(other than the usual memory fence after instance initialization),
and is suitable for use with {\sc simd} instruction sets
because it has no branches or loops.
The {\sc TwinLinear} algorithm is the result of a systematic exploration
of a substantial space of nonlinear mixing functions that combine the output of
two independent generators of (perhaps not very strong) pseudorandom number sequences.
We discuss this design space and our strategy for exploring it.
We used the PractRand test suite (which has provision for failing fast)
to filter out poor candidates, then used TestU01 BigCrush to verify the quality
of candidates that withstood PractRand.
We present results of analysis and extensive testing
on {\sc TwinLinear} (using both TestU01 and PractRand). Single instances of {\sc TwinLinear}
have no known weaknesses, and {\sc TwinLinear} is significantly more robust than
{\sc SplitMix} against accidental correlation in a multithreaded setting. It is slightly more costly
than {\sc SplitMix} (10 or 11 64-bit arithmetic operations per 64 bits generated, rather than 9)
but has a shorter critical path (5 or 6 operations rather than 8).
We believe that {\sc TwinLinear} is suitable for the same sorts of applications as {\sc SplitMix},
that is, ``everyday'' scientific and machine-learning applications (but not cryptographic applications),
especially when concurrent threads or distributed processes are involved.
Authors: Guy Steele
Venue: 2017 ACM OOPSLA
Content: