xoshiro.h

An implementation of the xoshiro/xoroshiro family of pseudorandom number generators. See the Introduction page for more details. More...

Go to the source code of this file.

Classes
class	xso::generator< State, Scrambler >
	A pseudorandom number generator combining a State and a Scrambler. More...
class	xso::xoshiro< N, T, A, B >
	The state for the Xoshiro family of pseudorandom number generators. More...
class	xso::xoroshiro< N, T, A, B, C >
	The state for the Xoroshiro family of pseudorandom number generators. More...
struct	xso::star< S, w >
	The star functor multiplies a state word by a constant. More...
struct	xso::star_star< S, R, T, w >
	The star_star functor multiplies a state word by a constant, rotates the result, then multiplies by another constant. More...
struct	xso::plus< w0, w1 >
	The plus functor can be passed a state array and will return the sum of two state words. More...
struct	xso::plus_plus< R, w0, w1 >
	The plus_plus functor can be passed a state array and will return the sum of two state words rotated and shifted. More...
class	xso::partition< RNG >
	Partition a random number stream into a number of non-overlapping sub-streams. More...
struct	std::formatter< T >
	Our classes are connected to std::format and friends by specializing the std::formatter struct. More...

Concepts
concept	xso::Distribution
	A C++ concept that lets us distinguish standard distribution types from other types.

Typedefs
using	xso::rng32 = xoshiro_4x32_star_star
	The recommended 32-bit output generator – used as xso::rng32.
using	xso::rng64 = xoshiro_4x64_star_star
	The recommended 64-bit output generator – used as xso::rng64.
using	xso::rng = rng64
	The recommended default generator for most usage – used as xso::rng.

Functions
template<typename State>
constexpr auto	xso::jump_coefficients (std::size_t n, bool n_is_log2)
	Returns the coefficients of the jump polynomial that can be used to jump a generator/state ahead by \(J = n\) or \(J= 2^n\) steps. The coefficients are compactly packed into the returned array of words.
template<typename State>
auto	xso::transition_matrix ()
	Returns the transition matrix for a state/generator type as a gf2::BitMatrix.
template<typename State>
auto	xso::characteristic_polynomial ()
	Returns the characteristic polynomial for our state's transition matrix as a gf2::BitPolynomial.
template<typename State>
auto	xso::jump_polynomial (gf2::BitPolynomial< typename State::word_type > const &c, std::size_t N, bool N_is_log2=false)
	Returns a jump polynomial that moves the generator type J steps ahead in its random number stream.
template<has_type_string_class_method T>
std::ostream &	operator<< (std::ostream &s, const T &)
	The usual output stream operator for an xso::generator, State, or Scrambler.

Detailed Description

An implementation of the xoshiro/xoroshiro family of pseudorandom number generators. See the Introduction page for more details.

Function Documentation

characteristic_polynomial()

template<typename State>

auto xso::characteristic_polynomial

(

)

Returns the characteristic polynomial for our state's transition matrix as a gf2::BitPolynomial.

Note

If the transition matrix is n x n then the return will have degree n + 1 and should be monic.

jump_coefficients()

template<typename State>

auto xso::jump_coefficients ( std::size_t n, bool n_is_log2 )

constexpr

Returns the coefficients of the jump polynomial that can be used to jump a generator/state ahead by \(J = n\) or \(J= 2^n\) steps. The coefficients are compactly packed into the returned array of words.

The jump polynomial is computed \(r(x) = x^J \mathrm{mod} c(x)\) where \(c(x)\) is the characteristic polynomial of the state transition matrix.

The computed jump polynomial \(r(x) = r_0 + r_1 x + ... + r_{n-1} x^{n-1}\) can be represented by its \(n\) bit coefficients. Those coefficients are returned compactly packed into an array of words.

Panics

This method depends on having the State's precomputed characteristic polynomial available to us. In practice, we have precomputed the characteristic polynomial for just a few xoshiro/xoroshiro's with specific parameters. If the State has no precomputed characteristic coefficients this method will fail at compile time.

jump_polynomial()

template<typename State>

auto xso::jump_polynomial	(	gf2::BitPolynomial< typename State::word_type > const &	c,
		std::size_t	N,
		bool	N_is_log2 = false )

Returns a jump polynomial that moves the generator type J steps ahead in its random number stream.

This method computes the jump polynomial \(r(x) = x^J \mathrm{mod} c(x),\) where \(c(x)\) is the characteristic polynomial of the state transition matrix and \(J\) is either \(N\) or \(2^N\).

Setting N_is_log2 to true allows for really huge jumps like J = 2^100 which would overflow normal integer types.

operator<<()

template<has_type_string_class_method T>

std::ostream & operator<<	(	std::ostream &	s,
		const T &	)

The usual output stream operator for an xso::generator, State, or Scrambler.

We simply forward output requests to each type's type_string method.

transition_matrix()

template<typename State>

auto xso::transition_matrix

(

)

Returns the transition matrix for a state/generator type as a gf2::BitMatrix.

Note

The transition matrix will be a square n x n matrix over GF(2) where n is the number of bits in the state. The state advance operation can be represented as a matrix-vector multiplication over GF(2) \(\mathbf{s}\leftarrow T \cdot \mathbf{s},\) where \(\mathbf{s}\) is the state vector, and \(T\) is the transition matrix.

This method computes that \(T\) matrix by examining the action of the step() method on all the unit states.