Pseudorandom number generator (PRNG)#

This software module implements different pseudorandom number generators (PRNGs) [[1]], [[2]]. The implemented generators return uniformly distributed unsigned 32-bit integers. All implemented generators are not cryptographically secure and are intended for engineering applications such as neural network initialization or random excitation for model identification. Additional reading:

Implementation#

The module uz_prng is a generic implementation for PRNGs. The actual generation of the random numbers is facilitated by the Implemented generators, each with specific properties. Other software modules can depend on uz_prng instead of the individual generators, which enables changing the generator for experiments without code changes. In addition to generating uniform distributions of uint32_t type, different scaling methods and generation of bounded uint32_t as well as float are supported.

Seeds#

PRNGs use an initial condition called seed that determines the specific random number stream. The sequence of random numbers is deterministic for a given seed, i.e., initializing uz_prng with a given seed and generator type always returns the same sequence. The initialization of uz_prng passes the seed to the specific algorithm. The details of each generator seed are as follows:

  • uz_prng_squares: if the seed is between 0 and 29, a pre-generated key is used (recommended). Otherwise, the value is used as the key.

  • uz_prng_mtwister: 32-bit seed. Since uz_prng_init uses 64-bit seeds, the upper 32-bits are ignored if Mersenne Twister is used.

  • uz_prng_halton: seed must be a prime number.

  • uz_prng_pcg: 64-bit random seed. The initial sequence controlling substreams is arbitrarily set to 54.

  • uz_prng_xoshiro: 64-bit random seed which is shuffled using splitmix64 as recommended by algorithm author.

Implemented generators#

Distribution of PRNG [0,UINT32_MAX]#

1D-Case#

The following figure compares the distributions of the different implemented PRNGs by showing the generated numbers’ histogram after different sample sizes are drawn. The distributions of the generated numbers tend towards a uniform distribution for an increasing number of samples.

(Source code, png, hires.png, pdf)

../../../_images/uz_prng-1.png

Fig. 349 Histogram for different numbers of samples taken from the implemented generators. Samples are generated using uz_prng_X_get_uniform_uint32, where X is the name of the specific generator. For an increasing number of taken samples, the distribution tends towards uniform data. However, for a small number of samples, the generated random numbers can deviate from a uniform distribution considerably (as is the case with real randomness, i.e., law of large numbers). As can be seen, the Halton sequence produces uniformly distributed values already for a low number of samples.#

2D Case#

Applications may require the generation of random numbers for n-dimensions. One example is a random sampling of the possible operating range of an electrical machine, i.e., the rotational speed and output torque. Other examples include the identification of model parameters, which might require a random excitation to yield transfer functions. Random sampling for multiple dimensions using the Halton sequence requires special care. If a 2D-Halton sequence is required, uz_prng can not be used; use uz_prng_halton directly. The following figure shows the generated distributions of different PRNGs in the 2D case.

(Source code, png, hires.png, pdf)

../../../_images/uz_prng_2d_compare_00_00.png

Fig. 351 Generated random values generated with uz_prng_get_uniform_uint32_zero_to_uint32_max using different generators plotted as 2-dimensional data. Using uz_prng_generator_halton does not yield a random pattern but a linear relationship between the generated values. Using uz_prng_halton_get_uniform_float_2d generates a proper Halton sequence for 2 dimensions.#

Distributions for multiple seeds#

Bounded integer#

The generation of bounded integer values is not straightforward. Essentially, there are methods for scaling uniform distributions in the interval [0,UINT32_MAX] to [0,upper_bound], which are simple but slightly biased, and more complex methods that are not biased. Bias and unbiased methods are implemented. See the following for more information:

Note that the bias happens rarely. I.e., in the Ceedling tests, 50000 random samples for different seeds and generators do not yield any difference between biased and unbiased transformation to bounded integers. A loop generating random integers like so:

#pragma GCC push_options
#pragma GCC optimize("O0")
void test_uz_prng_ever_biased(void)
{
    uz_prng_t *pcg = uz_prng_init(uz_prng_generator_pcg, uz_prng_float_scale_fp_multiply, 0U);
    volatile uint32_t unbiased = 0;
    volatile uint32_t biased = 0;

    for (uint32_t i = 0U; i < UINT32_MAX; i++)
    {
        unbiased = uz_prng_get_uniform_uint32_zero_to_range_unbiased_opt(pcg, 9);
        biased = uz_prng_get_uniform_uint32_zero_to_range_int_mult(pcg, 9);
        TEST_ASSERT_EQUAL_UINT32(unbiased, biased);
    }
}
#pragma GCC pop_options

Will fail the test, i.e., some random numbers differ between biased and unbiased versions. Note that the GCC options are required to prevent that the loop is not executed since both variables are unused for the compiler.

(Source code, png, hires.png, pdf)

../../../_images/density_plot_multipe_seeds_biased_uint1000.png

Fig. 353 Histogram of uz_prng_get_uniform_uint32_zero_to_range_unbiased_opt(X,9U) (left) and uz_prng_get_uniform_uint32_zero_to_range_int_mult(X,9U) (right) for the implemented generators for 10 different random seeds. The different distributions of the generators, as well as the random seeds, result in varying distributions of random numbers. Within this test, no difference between the biased and unbiased versions is observed. Note that this bias is more pronounced for large numbers in the range.#

Uniform distribution float [0,1)#

The following figure highlights the dependency of the different generators on the random seed. A sample of 5000 values is taken from each generator for ten different random seeds. As can be seen, the specific distribution generated varies for the given seed and the used generator.

(Source code, png, hires.png, pdf)

../../../_images/density_plot_multiple_seeds.png

Fig. 355 Density distribution of each generator calculated using Matlab ksdensity for 10 random seeds each. Values generated by uz_prng_get_uniform_float_zero_to_one using uz_prng_float_scale_fp_multiply.#

Normal distribution#

Generating normal distributions is implemented by the polar method [[3]], which is a variation of the Box-Muller transformation [[4]].

(Source code, png, hires.png, pdf)

../../../_images/density_plot_normal_distribution.png

Fig. 357 Density distribution of 5000 samples generated by uz_prng_get_normal_float using uz_prng_generator_squares as PRNG. Comparison of three different random seeds.#

Calculation time#

The following calculation times are measured using the mean execution time required to generate one uint32_t for each generator. Measurements are facilitated on the R5 of the UltraZohm. The measurement principle uses System Time R5 to log the execution time of the ISR. The following code is used in the ISR.

if (current_state == control_state)
{
    // Start: Control algorithm - only if ultrazohm is in control state
    for (uint32_t i = 0; i < NUMBER_OF_PRNG_RUNS_PER_ISR; i++)
    {
        rnd_numbers[i]=uz_prng_get_uniform_uint32_zero_to_uint32_max(generator);
    }
}

If the system is not in the control state, the baseline execution without generating random values is \(16.2\,\mu s\). This baseline is subtracted from execution time and divided by the number of generated PRNGs to yield the generation time for one value. Note that the smallest difference between execution times by this method is \(10\,ns\) due to the clock frequency of the global counter in the FPGA. Therefore, the measurements should be used as a rough estimation.

Generate one rand [0,UINT32_MAX]#

The measurement is based on generating 20 values per ISR over 4000 ISR cycles by calling uz_prng_get_uniform_uint32_zero_to_uint32_max.

Results:

  • uz_prng_generator_xoshiro and uz_prng_generator_pcg are the fastest generators

  • uz_prng_generator_mtwister has a low mean calculation time. However, the internal state is shuffled every 620 calls, resulting in a spike in calculation time. This shuffle of the state is inherent to the algorithm. Thus, uz_prng_generator_mtwister is not recommended for usage in the ISR.

  • uz_prng_generator_halton seems to increase calculation time with the number of samples taken and approaches \(0.6\,\mu s\) per random number, see Halton timing.

(Source code, png, hires.png, pdf)

../../../_images/uz_prng-2.png

Fig. 359 Measured execution time of uz_prng_get_uniform_uint32_zero_to_uint32_max for different generators.#

Float [0,1)#

  • uz_prng_scale_to_float_zero_to_one_divide

  • uz_prng_scale_to_float_zero_to_one_multiply = 10ns overhead

  • uz_prng_scale_to_float_zero_to_one_shift_multiply = 8ns -> This is the fastest

  • All three functions do not have a measurable difference in execution time

  • Generating one float (0,1) using pcg takes 0.153 us

  • Additional calculation time for float is approx. 10ns compared to uint32

The following table shows the calculation time of calling uz_prng_get_uniform_float_zero_to_one once and compares the different settings of uz_prng_float_scale_method. The results do not show a meaningful difference. Measurements

Method

Execution time

fp_muliply_mean

\(0.1985\,\mu s\)

fp_divide_mean

\(0.1983\,\mu s\)

shift_multi_mean

\(0.1942\,\mu s\)

(Source code, png, hires.png, pdf)

../../../_images/uz_prng-3.png

The following figure shows the density distribution over 10000 samples of the execution times calculated using Matlab ksdensity.

(Source code, png, hires.png, pdf)

../../../_images/uz_prng-4.png

uint32_t in range [0,range)#

  • int multi is the fastest but is biased

  • unbiased opt is unbiased and faster than unbiased

  • No reason to use float multiplication version

  • Use unbiased mean if comparability with other Frameworks that use Lemire’s method (https://arxiv.org/abs/1805.10941) is desired

Method

Execution time

float_mult_mean

\(0.1955\,\mu s\)

int_mult_mean

\(0.1705\,\mu s\)

unbiased_mean

\(0.2108\,\mu s\)

unbiased_opt_mean

\(0.1761\,\mu s\)

(Source code, png, hires.png, pdf)

../../../_images/uz_prng-5.png

Halton timing#

The calculation time for uz_prng_generator_halton increases with the number of samples taken from the Halton sequence. This seems to be related to the fact that the implementation relies on a loop to find the nth value of the Halton sequence, which requires more passes for increasing numbers of \(n\). The following figure shows the execution time of uz_prng_generator_halton for 874,821,900 samples, which did not result in a settled calculation time. The seed is set to 7 in this experiment; the behavior probably depends on the starting prime number. Usage of uz_prng_generator_halton in long-running applications (multiple days) should be handled carefully.

Warning

Halton generator draws the \(i-th\) number of the Halton sequence of the starting prime number. Therefore, the internal counter will overflow after 4,294,967,295 (i.e., UINT32_MAX) drawn samples. Note that unsigned integer wrap, therefore, the Halton sequence will repeat after 2^32-1 calls.

(Source code, png, hires.png, pdf)

../../../_images/uz_prng-6.png

Reference#

typedef struct uz_prng_t uz_prng_t#

Object of a random number generator.

enum uz_prng_generator#

Choose which generator is used internally.

Values:

enumerator uz_prng_generator_squares#
enumerator uz_prng_generator_mtwister#
enumerator uz_prng_generator_pcg#
enumerator uz_prng_generator_xoshiro#
enumerator uz_prng_generator_halton#
enum uz_prng_float_scale_method#

Choose which scaling version to generate random float values is used. uz_prng_float_scale_fp_shift_multiply is recommended.

Values:

enumerator uz_prng_float_scale_fp_multiply#
enumerator uz_prng_float_scale_fp_divide#
enumerator uz_prng_float_scale_fp_shift_multiply#
uz_prng_t *uz_prng_init(enum uz_prng_generator generator, enum uz_prng_float_scale_method scale_method, uint64_t seed)#

Initializes a random number generator for the specified generator type, scaling method and random seed.

Parameters:

  • generator – Generator type

  • scale_method – Scaling version

  • seed – Seed of the generator. See documentation of the individual generator types on how to set the seed.

Returns:

uz_prng_t*

uint32_t uz_prng_get_uniform_uint32_zero_to_uint32_max(uz_prng_t *self)#

Generate one uniform distributed uint32 in the interval [0,2^32), i.e., 0 up to and including UINT32_MAX.

Parameters:

  • self

Returns:

uint32_t

uint32_t uz_prng_get_uniform_uint32_zero_to_range_unbiased(uz_prng_t *self, uint32_t range)#

Generate one uniform distributed uint32 in the interval [0,range), i.e., 0 up to but excluding “range”. Uses Lemire’s method (https://arxiv.org/abs/1805.10941) according to https://www.pcg-random.org/posts/bounded-rands.html.

Parameters:

  • self

  • range

Returns:

uint32_t

uint32_t uz_prng_get_uniform_uint32_zero_to_range_unbiased_opt(uz_prng_t *self, uint32_t range)#

Generate one uniform distributed uint32 in the interval [0,range), i.e., 0 up to but excluding “range”. Uses an faster version of Lemire’s method (https://arxiv.org/abs/1805.10941) according to https://www.pcg-random.org/posts/bounded-rands.html.

Parameters:

  • self

  • range

Returns:

uint32_t

uint32_t uz_prng_get_uniform_uint32_zero_to_range_float_mult(uz_prng_t *self, uint32_t range)#

Generate one uniform distributed uint32 in the interval [0,range), i.e., 0 up to but excluding “range”. Uses float multiplication to scale and is biased according to https://www.pcg-random.org/posts/bounded-rands.html.

Parameters:

  • self

  • range

Returns:

uint32_t

uint32_t uz_prng_get_uniform_uint32_zero_to_range_int_mult(uz_prng_t *self, uint32_t range)#

Generate one uniform distributed uint32 in the interval [0,range), i.e., 0 up to but excluding “range”. Uses integer multiplication to scale and is biased according to https://www.pcg-random.org/posts/bounded-rands.html.

Parameters:

  • self

  • range

Returns:

uint32_t

bool uz_prng_get_uniform_bool(uz_prng_t *self)#

Returns true or false in a uniform distribution.

Parameters:

  • self

Returns:

true

Returns:

false

float uz_prng_get_uniform_float_zero_to_one(uz_prng_t *self)#

Returns uniform distributed float values in the unit interval [0,1)

Parameters:

  • self

Returns:

float

float uz_prng_get_uniform_float_min_to_max(uz_prng_t *self, float min, float max)#

Returns uniform distributed float values in the unit (min,max). Min and max can be positive or negative, but max>min is required.

Parameters:

  • self

  • min – Lower bound of the interval

  • max – Upper bound of the interval

Returns:

float

float uz_prng_get_normal_float(uz_prng_t *self, float mean, float sigma)#

Generate normal distributed random float.

Parameters:

  • self

  • mean – Mean value of the normal distribution

  • sigma – Standard deviation of the normal distribution

Returns:

float

Implementation details#

This module uses a pointer of type void internally to be able to provide a generic interface for different generator types. Specifically, each generator has a type, e.g., uz_prng_squares_t or uz_prng_pcg_t. The initialization function of these generators returns a pointer of type uz_prng_X_t, with X being the specific generator. This type is cast to void to store the pointer independent of the generator. This approach decreases type safety, but enables flexibility.

Sources#