random_number_generator.h File Reference

#include "memilio/io/default_serialize.h"
#include "memilio/utils/compiler_diagnostics.h"
#include "memilio/utils/logging.h"
#include "memilio/utils/miompi.h"
#include "memilio/utils/span.h"
#include "memilio/utils/type_safe.h"
#include "Random123/array.h"
#include "Random123/threefry.h"
#include <cassert>
#include <cstdint>
#include <functional>
#include <limits>
#include <numeric>
#include <random>
#include <type_traits>

Include dependency graph for random_number_generator.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
	MSVC_WARNING_DISABLE_PUSH (4127) GCC_CLANG_DIAGNOSTIC(ignored "-Wexpansion-to-defined") namespace mio

Function Documentation

MSVC_WARNING_DISABLE_PUSH()

MSVC_WARNING_DISABLE_PUSH

(

4127

)

Base class for counter based random number generator.

All (pseudo) random number generators (RNG) consist of some state, a function state = advance(state), and a function sample = generate(state). They produce a sequence of random samples by advancing the state and from the new state generate the actual sample.

example in pseudo code: state = initial_state(seed) sample1 = generate(state) state = advance(state) sample2 = generate(state) ...

In most normal RNGs like mersenne twister the advance function needs to be complicated in order to perform the necessary mixing of bits. The state needs to be relatively large to contain sufficient numbers of random bits. The generate function on the other hand is very simple, often just returning the state (whole or in parts) without further computation.

In counter based generators (cRNG), the state and advance function are very simple and all the mixing of bits is in the generate function. The state is split into a key and a counter. The generate function is an encryption or hash function. Like a hash function, it produces a pseudo-random value from the input. The key is used by the generate function the same way as an encryption key. The key is randomly seeded in the beginning so that a different sequence of samples is generated on each run. Then the key doesn't change anymore. The advance function only increments the counter. The generate function produces completely different output even for sequential numbers.

Because their state is simple, cRNG are well suited for parallel applications. To create n independent subsequences from a total sequence of N samples you only need to create n counters, where counter i starts at i * (N / n). Normal RNGs need special algorithms to efficiently generate subsequences, if it is possible at all. The counter is of minimal size, it only needs to be big enough to fit the number of samples generated. Often the subsequence index i is already available in some other form, e.g., the thread index or the agent index in an agent based model, so only a small amount of extra storage is needed for the subsequence counter. The key is shared between all subsequences. Modern CPU architectures also are very efficient at executing the hash and encryption functions that are used as the generate function, increasing performance of the generator.

The length of the total sequence and the subsequences and the number of subsequences can be adjusted as needed by assigning different numbers of bits to the key, the subsequence index and the subsequence counter. The counter only needs to store the number of samples generated. A counter of c bits supports a sequence of 2^c samples or 2^n subsequences of 2^(c - n) samples, in which case you can split the counter into a subsequence index of n bits and a subsequence counter of (c - n) bits where each of the subsequence counters starts at 0. Generating a samples of k bits requires a key of at least k bits for sufficient randomness. Example:

• A 64 bit counter (uint64_t) and a 64 bit key produce 2^64 samples each with 64 bits. You need to store one counter and one key.
• A subsequence index of 32 bits (uint32_t), subsequence counter with 32 bits and a 64 bit key produce 2^32 subsequences of 2^32 samples each with 64 bits per sample. You need to store 2^32 subsequence indices, 2^32 subsequence counters and one key, but the counters are completely independent and thread safe. The subsequence index and corresponding subsequence counter can also be stored together in one 64bit counter, e.g., the subsequence index is the high bits and subsequence counter is the low bits, see rng_totalsequence_index().

Also see https://github.com/DEShawResearch/random123 for more information on cRNGs and the specific cRNG we use.

Classes deriving from this base class need to supply the key and counter by implementing the functions

• result_type get_key() const
• result_type get_counter() const
• void increment_counter()

This class satisfies the standard UniformRandomBitGenerator concept.

Minimum value generated by this generator. Counterbased generators allow the whole range supported by the result_type.

Maximum value generated by this generator. Counterbased generators allow the whole range supported by the result_type.

Generate the next value in the random sequence. Key and counter are supplied by the Derived class by implementing the functions get_key(), get_counter(), and increment_counter().

Convert a Random123 array type (rng counters and keys) to uint64_t.

Convert a uint64_t to a Random123 array type (rng counters and keys).

A key type for counter based random number generators.

Template Parameters

an	unsigned integer type that determines the size of the key, i.e., the number of different sequences.

A counter type for counter based random number generators.

Template Parameters

an	unsigned integer type that determines the size of the counter, i.e., the length of the random sequence.

Seed a counter based random number generator key.

Template Parameters

A	type that satisfies standard SeedSeq.

Parameters

seed_seq

A seed sequence, e.g. initialized using std::random_device.

Returns

A seeded key.

Get the counter in the total sequence for a counter in a given subsequence. A total sequence counter of C bits supports 2^N subsequences of 2^(C - N) samples. Then the counter can be split into a subsequence index of N bits and a subsequence counter of S = (C - N) bits. The length of the subsequences is determined by the type of the subsequence counter and the requested total sequence counter. The subsequence index does not need to be exactly N bits, it can be larger. E.g., a subsequence counter of 16 bits and a subsequence index of 64 bits can be used for a combined counter of 64 bits since there is not 48 bit type.

Template Parameters

UIntC	The counter type of the total sequence with C bits.
UIntN	An unsigned integer type with at least N bits for the subsequence index.
CounterS	A counter type with S = (C - N) bits for the subsequence counter.

Parameters

subsequence_idx	The index of the subsequence. Must be less than 2^N.
counter	The counter in the subsequence.
return	The counter in the total sequence.

Get the subsequence counter from the total sequence counter. A total sequence counter of C bits supports 2^N subsequences of 2^(C - N) samples. Then the counter can be split into a subsequence index of N bits and a subsequence counter of S = (C - N) bits. The length of the subsequences is determined by the type of the subsequence counter.

Template Parameters

UIntS	An unsigned integer type of S bits for the subsequence counter.
CounterC	A counter type of C bits, where C > S.

Parameters

counter

The total sequence counter.

Returns

The counter in the subsequence.

General purpose counter based random number generator. Stores its own key and counter.

See also

RandomNumberGeneratorBase.

Set the seeds in all MPI processes the same as in the root.

This method is used by the default serialization feature.

get a random number generator that is static and local to this thread.

Returns

a RandomNumberGenerator that is static and local to this thread.

Note

Not to be used anymore, only used by ParameterDistribution.

Log the seeds used by the RandomNumberGenerator at the specified LogLevel.

Log the seeds used by the RandomNumberGenerator from thread_local_rng() at the specified LogLevel.

adapter for a random number distribution. Provides a static thread local instance of the distribution and a replacable core generator function (e.g. for mocks during testing). The parameters of the distribution are passed when the random number is generated instead of when the object is constructed.

Template Parameters

DistT

a type that models the standard RandomNumberDistribution concept

The type returned by the distribution.

The type that contains the parameters of the distribution. The template parameter must be constructible from this type.

get a static thread local instance of the contained Distribution class. Calls DistributionAdapter::get_instance().

The function that generates a random value from the distribution with the specified parameters.

the default generator function invokes an instance of the template parameter with a static thread local RNG engine. Constructors are private, use get_instance to get the current version.

get a random sample from the distribution. accepts the same arguments as the constructors of the template parameter type. example: std::uniform_int_distribution is constructed from two integers, so DistributionAdapter<std::uniform_int_distribution>::operator() accepts two integers as well.

get the generator function.

set the generator function.

get a static instance of this class. Instance is default constructed on the first call. The generator function of this instance can be replaced for mocking during tests.

select a random integer in [0, n) with weights [w_0, ..., w_(n-1)] the probability to pick i is w_i/S where S is the sum of all weights. Similar to std::discrete_distribution but does not allocate, instead expects a Span of weights. Models the standard RandomNumberDistribution concept.

the type returned by the distribution.

stores the parameters of the distribution (i.e. the weights).

default distribution has no weights. always returns 0.

distribution with specified weights.

distribution with specified params.

reset internal state. does nothing, but required by the concept.

get the parameters of the distribution.

set the parameters of the distribution.

get the weights.

draw a random number from the distribution.

Parameters

rng	object of a type that that models UniformRandomBitGenerator concept.

draw a random number from the distribution with the specified parameters.

Parameters

rng	object of a type that that models UniformRandomBitGenerator concept.
p	parameters of the dstribution.

adapted discrete distribution

See also

DistributionAdapter

adapted std::exponential_distribution.

See also

DistributionAdapter

adapted std::normal_distribution.

See also

DistributionAdapter

adapted std::uniform_int_distribution.

See also

DistributionAdapter

adapted uniform_real_distribution.

See also

DistributionAdapter

adapted poisson_distribution.

See also

DistributionAdapter

adapted lognormal_distribution.

See also

DistributionAdapter

adapted gamma_distribution.

See also

DistributionAdapter

adapted normal_distribution.

See also

DistributionAdapter