File RandomGenerators.h

↰ Parent directory (ADS/numeric)

The engineered random numbers, beyond the book: generators of 64 bits that cost a few instructions and pass the statistical batteries (BigCrush of TestU01, PractRand), and the uses of a word that need no division.

Definition (ADS/numeric/RandomGenerators.h)

Detailed Description

  • Xoshiro256 is xoshiro256++ of Blackman and Vigna: the state :math:` s in mathbb{F}_2^{256} ` goes by a linear map of xor, shifts and rotations of full period :math:` 2^{256} - 1 ` (all the states but 0), and the output :math:` mathrm{rotl}( s_0 + s_3 , 23 ) + s_0 ` scrambles it; jump() advances it by :math:` 2^{128} ` steps (the product of the state by a fixed polynomial of the map, 256 steps), so that each of :math:` 2^{128} ` streams of :math:` 2^{128} ` numbers serves a thread. Xoshiro256StarStar is xoshiro256** on the same state, the output :math:` mathrm{rotl}( 5 s_1 , 7 ) cdot 9 . The seed fills the state by SplitMix64 of Steele, Lea and Flood [see :ref:`file_ADS_dictionary_RandomHashing.h].

  • WyRand is the generator of Wang Yi: the Weyl sequence :math:` s_{i+1} = s_i + c bmod 2^{64} , c odd, of period :math: 2^{64} , hashed by the folding of a product of 128 bits, :math: h oplus l ` for :math:` h R + l = s ( s oplus c’ ) `.

  • Philox4x32 and Philox4x64 are the counter-based generators Philox4xW-10 of Salmon, Moraes, Dror and Shaw: the output of the counter c (4 words of W bits) under the key k (2 words) is 10 rounds of the bijection :math:` ( c_0 , c_1 , c_2 , c_3 ) mapsto ( h( M_1 c_2 ) oplus c_1 oplus k_0 , l( M_1 c_2 ) , h( M_0 c_0 ) oplus c_3 oplus k_1 , l( M_0 c_0 ) ) `, h and l the high and the low word of a product of 2W bits, the key bumped by the Weyl constants between the rounds; the counter only increases, so that discard( z ) costs O( 1 ) and any block of the stream is computed on its own. The sequence is that of std::philox4x32 and std::philox4x64 of C++26 (the key ( seed , 0 ), the counter from 0, the words of a block in order); two blocks are computed at once, their rounds interleaved, so that the products of one fill the latency of those of the other.

  • normalZiggurat() and exponentialZiggurat() are the ziggurats of Marsaglia and Tsang with 256 layers of equal area v under the density [see ZigguratTables.tpp]: one word gives the layer i (its low 8 bits) and a uniform u of [ -1 , 1 ) or [ 0 , 1 ) (its top 53 bits, apart from the layer, as Leong et al. ask), and :math:` u x_i ` is the result when :math:` | u | < x_{i+1} / x_i `, about 98.8% (normal) and 98.9% (exponential) of the draws, at the cost of a word, a product and a comparison; otherwise a uniform height decides the wedge against the density, and in the base strip the tail beyond r is drawn by the exponentials of Marsaglia (normal) or from r again (exponential, with no memory). The tables are constants, and the functions are inlined, so that the state of the generator stays in the registers of the caller.

  • uniformBelow( g , s ) is the integer uniform in [ 0 , s ) of Lemire: for the word x, :math:` x s = h 2^{64} + l ` and the result is h, which is uniform once the l below :math:` t = 2^{64} bmod s ` are rejected; since :math:` t < s , the comparison :math: l < s ` decides without the division in all but a fraction :math:` s / 2^{64} ` of the draws, a draw is rejected with probability :math:` t / 2^{64} < s / 2^{64} , and the expected words per result are :math: 2^{64} / ( 2^{64} - t ) ; uniformReal() is :math: lfloor x / 2^{11} rfloor 2^{-53} , uniform on the :math: 2^{53} ` doubles :math:` k 2^{-53} ` of [ 0 , 1 ).

  • shuffleFast() is the shuffle of Fisher and Yates [see shuffle() of File RandomNumbers.h] with the indices drawn in batches, after Brackett- Rozinsky and Lemire: one word x gives the indices of k consecutive steps with bounds :math:` b_1 , dots , b_k ` of product :math:` p le 2^{64} , the j-th the high word of :math: l_{j-1} b_j ` with :math:` l_0 = x ` and :math:` l_j ` its low word, which is uniform on the :math:` prod b_j ` tuples once :math:` l_k < 2^{64} bmod p ` is rejected, with probability below :math:` p / 2^{64} ; 6 steps a word while the bounds are below :math: 2^{10} ` ( :math:` p < 2^{60} ), 2 below :math: 2^{32} , so that a shuffle of n items draws about :math: n / 2 ` words instead of n.

  • AliasTable is the alias method of Walker in the construction of Vose: with :math:` p_i = n w_i / sum_j w_j , the items with :math: p_i < 1 ` and those with :math:` p_i ge 1 ` in two lists, each step gives to a small one its alias, a large one that gives up :math:` 1 - p_i ` of its mass, so that the cell i keeps i with probability :math:` p_i ` and gives its alias otherwise: O( n ) time and space to build, the probabilities exact up to the rounding of :math:` p_i . A draw is one word x: :math: x n = h 2^{64} + l , the cell h and the coin :math: l < lfloor p_h 2^{64} rfloor ` from the same product, O( 1 ) time and two loads, against the :math:` O( log n ) ` of the search in the cumulative sums; the cells and the coins are off the exact ones by at most :math:` n / 2^{64} ` each, as for the products of Lemire with no rejection.

The generators meet UniformRandomBitGenerator, with min() = 0 and max() = :math:` 2^{64} - 1 `, so that they serve the distributions of std; the functions above need such a generator of 64 full bits.

The contracts [see File Contract.h]: s >= 1 for uniformBelow(), and its result is below s. The functions are defined in RandomGenerators.tpp.

  1. Blackman, S. Vigna, Scrambled linear pseudorandom number generators, ACM Transactions on Mathematical Software 47(4), 36:1-32, 2021, doi:10.1145/3460772

    1. Steele, D. Lea, C. H. Flood, Fast splittable pseudorandom number generators, Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA), 453-472, 2014, doi:10.1145/2660193.2660195

  1. Yi, wyhash and wyrand, https://github.com/wangyi-fudan/wyhash

  1. Lemire, Fast random integer generation in an interval, ACM Transactions on Modeling and Computer Simulation 29(1), 3:1-12, 2019, doi:10.1145/3230636

    1. Fisher, F. Yates, Statistical Tables for Biological, Agricultural and Medical Research, Oliver and Boyd, 1938, and R. Durstenfeld, Algorithm 235: random permutation, Communications of the ACM 7(7), 420, 1964, doi:10.1145/364520.364540

  1. Brackett-Rozinsky, D. Lemire, Batched ranged random integer generation, Software: Practice and Experience 55(1), 155-169, 2025, doi:10.1002/spe.3369

    1. Salmon, M. A. Moraes, R. O. Dror, D. E. Shaw, Parallel random numbers: as easy as 1, 2, 3, International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 1-12, 2011, doi:10.1145/2063384.2063405

  1. Marsaglia, W. W. Tsang, The ziggurat method for generating random variables, Journal of Statistical Software 5(8), 2000, doi:10.18637/jss.v005.i08

      1. Leong, G. Zhang, D.-U. Lee, W. Luk, J. D. Villasenor, A comment on the implementation of the ziggurat method, Journal of Statistical Software 12(7), 2005, doi:10.18637/jss.v012.i07

    1. Walker, An efficient method for generating discrete random variables with general distributions, ACM Transactions on Mathematical Software 3(3), 253-256, 1977, doi:10.1145/355744.355749

    1. Vose, A linear algorithm for generating random numbers with a given distribution, IEEE Transactions on Software Engineering 17(9), 972-975, 1991, doi:10.1109/32.92917

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions

Defines

Typedefs