Lune

OOPSLA2021Top-tier venue

LXM: better splittable pseudorandom number generators (and almost as fast)

Guy L. Steele Jr., Sebastiano Vigna

Abstract

In 2014, Steele, Lea, and Flood presented SplitMix, an object-oriented pseudorandom number generator (prng) that is quite fast (9 64-bit arithmetic/logical operations per 64 bits generated) and also splittable . A conventional prng object provides a generate method that returns one pseudorandom value and updates the state of the prng; a splittable prng object also has a second operation, split , that replaces the original prng object with two (seemingly) independent prng objects, by creating and returning a new such object and updating the state of the original object. Splittable prng objects make it easy to organize the use of pseudorandom numbers in multithreaded programs structured using fork-join parallelism. This overall strategy still appears to be sound, but the specific arithmetic calculation used for generate in the SplitMix algorithm has some detectable weaknesses, and the period of any one generator is limited to 2 64 . Here we present the LXM family of prng algorithms. The idea is an old one: combine the outputs of two independent prng algorithms, then (optionally) feed the result to a mixing function. An LXM algorithm uses a linear congruential subgenerator and an F 2 -linear subgenerator; the examples studied in this paper use a linear congruential generator (LCG) of period 2 16 , 2 32 , 2 64 , or 2 128 with one of the multipliers recommended by L’Ecuyer or by Steele and Vigna, and an F 2 -linear xor-based generator (XBG) of the xoshiro family or xoroshiro family as described by Blackman and Vigna. For mixing functions we study the MurmurHash3 finalizer function; variants by David Stafford, Doug Lea, and degski; and the null (identity) mixing function. Like SplitMix, LXM provides both a generate operation and a split operation. Also like SplitMix, LXM requires no locking or other synchronization (other than the usual memory fence after instance initialization), and is suitable for use with simd instruction sets because it has no branches or loops. We analyze the period and equidistribution properties of LXM generators, and present the results of thorough testing of specific members of this family, using the TestU01 and PractRand test suites, not only on single instances of the algorithm but also for collections of instances, used in parallel, ranging in size from 2 to 2 24 . Single instances of LXM that include a strong mixing function appear to have no major weaknesses, and LXM is significantly more robust than SplitMix against accidental correlation in a multithreaded setting. We believe that LXM, like SplitMix, is suitable for “everyday” scientific and machine-learning applications (but not cryptographic applications), especially when concurrent threads or distributed processes are involved.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Twin Column Parity Mixers and Gaston - A New Mixing Layer and PermutationSolane El Hirch, Joan Daemen, Raghvendra Rohit, Rusydi H. MakarimCRYPTO 2023 · 2 citations
  2. New Representations of the AES Key ScheduleGaëtan Leurent, Clara PernotEUROCRYPT 2021 · 33 citations
  3. Machine-Checked Proofs for Cryptographic Standards: Indifferentiability of Sponge and Secure High-Assurance Implementations of SHA-3José Bacelar Almeida, Cécile Baritel-Ruet, Manuel Barbosa, Gilles Barthe et al.CCS 2019 · 35 citations
  4. IMIX: In-Process Memory Isolation EXtensionTommaso Frassetto, Patrick Jauernig, Christopher Liebchen, Ahmad-Reza SadeghiUSENIX Security 2018 · 77 citations
  5. Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and InterpretabilityTao Tao, Maissam BarkeshliICLR 2026
Dusk over the sea between two cliffs drawn in fine vertical lines