# Basic Random Number Generators

Basic Random Number Generators (BRNG) are used to obtain random numbers of various statistical distributions. Non-uniform distribution generators depend on the quality of the underlying BRNGs. You should choose the BRNG depending on your application requirements, such as:

- quality requirements
- speed
- memory use
- efficient generation of random number subsequences
- using random numbers as real ones
- using random numbers as a bit stream

For example, a BRNG that cannot provide true randomness for lower bits is still applicable to applications using variates as real numbers.

VS provides a variety of BRNGs and permits you to register user-defined basic generators and use them in the same way as the BRNGs available with VS. You can also use random numbers generated externally, for example, from a physical source of random numbers [Jun99]. This makes VS a general-purpose library suitable for various tasks. See Abstract Basic Random Number Generators. Abstract Streams section for details.

Having several basic RNGs of different types available in VS also enables you to get more accurate verification results. Result verification is very important for computational experimentation. Typically, a researcher cannot verify the output since the solution is simply unknown. Any verification process involves testing of each structural element of the system. Being one of such structural elements, an RNG may produce inadequate results. To get more reliable results of the experiment, many authors recommend using several different BRNGs in a series of computational experiments.

VS provides the following basic pseudo-, quasi-, and non-deterministic random number generators:

BRNG | Type | Description |
---|---|---|

MCG31m1 | pseudorandom | A 31-bit multiplicative congruential generator. |

R250 | pseudorandom | A generalized feedback shift register generator. |

MRG32k3a | pseudorandom | A combined multiple recursive generator with two components of order 3. |

MCG59 | pseudorandom | A 59-bit multiplicative congruential generator. |

WH | pseudorandom | A set of 273 Wichmann-Hill combined multiplicative congruential generators ( = 1, 2, ... , 273 ).j |

MT19937 | pseudorandom | Mersenne Twister pseudorandom number generator. |

MT2203 | pseudorandom | A set of 6024 Mersenne-Twister pseudorandom number generators ( = 1,...,6024).j |

SFMT19937 | pseudorandom | SIMD-oriented Fast Mersenne Twister pseudorandom number generator. |

SOBOL (with Antonov-Saleev [Ant79] modification) | quasi-random | A 32-bit Gray code-based generator producing low-discrepancy sequences for dimensions 1≤s≤40 |

NIEDERREITER (with Antonov-Saleev [Ant79] modification) | quasi-random | A 32-bit Gray code-based generator producing low-discrepancy sequences for dimensions 1≤s≤318. |

PHILOX4X32X10 | pseudorandom | A Philox4x32-10 counter-based pseudorandom number generator. |

ARS5 | pseudorandom | A counter-based pseudorandom number generator, which uses instructions from the AES-NI set. Available in IA® architectures supporting this instruction set. |

ABSTRACT | pseudorandom or quasi-random, depending on the user-provided settings | Abstract source of random numbers. See Abstract Basic Random Number Generators. Abstract Streams section for details. |

NON-DETERMINISTIC | Non-deterministic |

Each VS basic generator consists of the following subroutines:

- Stream Initialization Subroutine. See section Random Streams and RNGs in Parallel Computation for details.
- Integer Output Generation Subroutine. Every generated integral value (within certain bounds) may be considered a random bit vector. For details on randomness of individual bits or bit groups, see Basic Random Generator Properties and Testing Results.
- Single Precision Floating-Point Random Number Vector Generation Subroutine. The subroutine generates a real arithmetic vector of uniform distribution over the interval [
).a, b - Double Precision Floating-Point Random Number Vector Generation Subroutine. The subroutine generates a real arithmetic vector of uniform distribution over the interval [
).a, b

The sections below discuss each basic generator in more detail and provide references for further reading.

MCG31m1

32-bit linear congruential generators including MCG31m1 [L'Ecuyer99] are still used as the default RNGs in various systems because of the simplicity of implementation, speed of operation, and compatibility with earlier versions of the systems. However, their period lengths do not meet the requirements for modern BRNGs. Nevertheless, MCG31m1 has good statistical properties and may provide optimal results in generating random numbers of various distribution types for relatively small samplings.

R250

R250 is a generalized feedback shift register generator. Feedback shift register generators have extensive theoretical footing and were first considered as RNGs for cryptographic and communications applications. Generator R250 proposed in [Kirk81] is fast and simple in implementation and is commonly used in the field of physics. However, the generator fails a number of tests, for example, a 2D self-avoiding random walk [Ziff98].

MRG32k3a

A combined generator MRG32k3a [L'Ecu99] meets the requirements for modern RNGs, such as good multidimensional uniformity or a fairly large period. Being optimized for various Intel® architectures, this generator rivals other VS basic RNGs in speed.

MCG59

A multiplicative congruential generator MCG59 is one of the two basic generators implemented in Numerical Algorithms Group (NAG) Numerical Libraries [NAG]. Since the module of this generator is not prime, its period length is 2

^{57}instead of 2^{59}, if the seed is an odd number. The drawback of such generators is that the lower bits of the output sequence are not random, therefore breaking numbers down into their bit patterns and using individual bits may be error-prone. For example, see [Knuth81], [L'Ecu94]. Besides, block-splitting of the sequence over the entire period into 2D similar blocks results in full coincidence of such blocks in d lower bits. For example, see [Knuth81], [L'Ecu94].WH

Wichmann-Hill (WH) is a set of 273 different BRNGs. It is the second BRNG in NAG libraries. The constants

a

_{i,j}are in the range from 112 to 127 and the constantsm

_{i,j}are prime numbers in the range from 16718909 to 16776971, which are close to 2^{24}. These constants have been chosen so that they give good results with the spectral test, see [Knuth81] and [MacLaren89]. The period of each WH generator should be at least 2^{92}, but it is affected by common factors between (m

_{1,j}- 1), (m

_{2,j}- 1), (m

_{3,j}- 1), and (m

_{4,j}- 1). Still, each generator should have a period of at least 2^{80}. Further discussion of the properties of these generators is given in [MacLaren89], which shows that the generated pseudorandom sequences are essentially independent of one another according to the spectral test.The variables

x

_{n},y

_{n},z

_{n},w

_{n}in the above equations define a successive member of integer subsequence set by recursion. The variableu

_{n}is the generator real output normalized to the interval (0, 1).MT19937

,

,

,

,

,

,

,

,
,
,
,
,
,
,
,
,

,

with matrix

`(32x32) having following format:`A

where 32-bit vector

a = a

_{31}...a

_{0}has the value`= 0x9908B0DF.`a

MT2203

The set of 6024 MT2203 pseudorandom number generators is an addition to MT19937 generator used in large-scale Monte Carlo simulations performed on distributed multi-processor systems. Parameters of the MT2203 generators are calculated using the methodology described in [Matsum2000] that provides mutual independence of the corresponding random number sequences. Every MT2203 generator has a period length equal to 2

^{2203}.
,

,

,

,

,

,

,

,
,
,
,
,
,
,

,

where matrix

`(32x32) has the following format:`Aj

,

with 32-bit vector

a

_{j}=a

_{31,j}...a

_{0,j}.SFMT19937

The SIMD-oriented Fast Mersenne Twister pseudorandom number generator [Saito08] is analogous to the MT19937 generator and uses Single Instruction Multiple Data (SIMD) and multi-stage pipelining CPU features. SFMT19937 generator has a period of a multiple of 2

^{19937}-1 and better equidistribution property than MT19937.where

w

_{0},w

_{m},w

_{n-2}... are 128-bit integers, and are`sparse 128 x 128 binary matrices for which`A, B, C, D

`operations are defined as follows:`wA, wB, wC, wD

- , left shift of 128-bit integer
bywfollowed by exclusive OR operationa - , right shift of each 32-bit integer in quadruple
bywfollowed by and-operation with quadruple of 32-bit masksb,maskmask = (mask_{1}mask_{2}mask_{3}mask_{4}) - , right shift of 128-bit integer
bywc - , left shift of each 32-bit integer in quadruple
bywd - , , k-th 32-bit integer in quadruplew
_{n} - Parameters of the generator take the following values:
= 8,a= 8,b= 8,c= 18,dmask_{1}=0xBFFFFFFG,mask_{2}=0xBFFAFFFF,mask_{3}=0xDDFECB7F,mask_{4}=0xDFFFFFEF

SOBOL

Bratley and Fox [Brat88] provide an implementation of the Sobol quasi-random number generator. VS implementation permits generating Sobol’s low-discrepancy sequences of length up to 2

^{32}. This implementation also permits registering user-defined parameters (direction numbers or initial direction numbers and primitive polynomials) during the initialization, which allows obtaining quasi-random vectors of any dimension. If you do not supply user-defined parameters, the default parameter values [Brat88] are used for generation of quasi-random vectors. The default dimension of quasi-random vectors can vary from 1 to 40 inclusive.The value

`is the right-most zero bit in`c

`-1;`n

x

_{n}is an s-dimensional vector of 32-bit values. The s-dimensional vectors (calculated during random stream initialization)v

_{i}, i =1,32

are called direction numbers. Vector u

_{n}is the generator output normalized to the unit hypercube (0,1)^{5}.NIEDERREITER

According to the results of Bratley, Fox, and Niederreiter [Brat92] Niederreiter’s sequences have the best known theoretical asymptotic properties. VS implementation permits generating Niederreiter’s low-discrepancy sequences of length up to 2

^{32}. This implementation also permits registering user-defined parameters (irreducible polynomials or direction numbers), which allows obtaining quasi-random vectors of any dimension. If you do not supply user-defined parameters, the default parameter values [Brat92] are used for generation of quasi-random vectors. The default dimension of quasi-random vectors can vary from 1 to 318 inclusive.Philox4x32-10

This is a keyed family of counter-based BRNGs. The state consists of 128-bit integer counter

`and two 32-bit keys`c

k

_{0}andk

_{1}. The generator output for each state consists of four 32-bit integer numbers obtained in the following way [Salmon2011]:- c
_{n}=c_{n-1}+ 1 - w
_{n}=f(c_{n}, where)is a function that takes a 128-bit argument and returns a 128-bit number. The returned number is obtained as follows:f- The argument
is interpreted as four 32-bit numbers , where , putck_{0}^{0}=k_{0}andk_{1}^{0}=k_{1}. - The following recurrence is calculated:Wheremulhi(a,b)andmullo(a,b)are high and low 32-bit parts of the a*b product, respectively.
- Put
, wheref(c) == 10N

- Integer output:r
_{4n+k}=w_{n}, where(k)w_{n}is the(k)-th 32-bit integer in quadruplekw_{n},= 0, 1, 2, 3k - Real output:u
_{n}=r_{n}/2^{32}

ARS5

ARS5 is a keyed family of counter-based BRNGs. The state consists of 128-bit integer counter

`and a 128-bit key`c

`. The BRNG is based on the AES encryption algorithm [FIPS-197]. The 32-bit output is obtained in the following way [Salmon2011]:`k

- c
_{n}=c_{n-1}+ 1 - w
_{n}=f(c_{n}, where)is a function that takes a 128-bit argument and returns a 128-bit number. The returned number is obtained as follows:f- Putc
_{0}=andc xor kk_{0}=.k - The following recurrence is calculated N times:
- c
_{i+1}=SubBytes(c) - c
_{i+1}= ShiftRows(c_{i+1}) - c
_{i+1}= MixColumns(c_{i+1}), this step is omitted ifi + 1 = N - c
_{i+1}= AddRoundKey(c_{i+1},k_{j}) - Lo(k
_{i+1}=)Lo(k+ 0x9E3779B97F4A7C15)Hi(k_{i+1}=)Hi(k+ 0xBB67AE8584CAA73B)

- Putf(c) = c
_{N}, where= 5N

- Integer output:r
_{4n+k}=w_{n}, where(k)w_{n}is the(k)-th 32-bit integer in quadruplekw_{n},= 0, 1, 2, 3k - Real output:u
_{n}=r_{n}/2^{32}

Specification for the

SubBytes

, ShiftRows

, MixColumns

and AddRoundKey

functions can be found in [FIPS-197].ABSTRACT

Abstract basic generators enable VS distribution generators to be used with the underlying uniform random numbers that are already generated. This feature might be useful in the following cases:

- You want to study the system using the same uniform random sequence but under different distribution parameters [Mikh2000]. It is unnecessary to generate uniform random numbers as many times as many different parameters you want to investigate.

There might be other cases when abstract basic generators are useful. See Abstract Basic Random Number Generators. Abstract Streams section for further reading. Because of the specificity of abstract basic generators, you cannot use

vslNewStream

and vslNewStreamEx

functions to create abstract streams. VS provides special vsliNewAbstractStream

, vslsNewAbstractStream

, and vsldNewAbstractStream

functions to initialize integer, single precision, and double precision abstract streams, respectively.NON-DETERMINISTIC

This basic generator is an abstraction of the source of non-deterministic random numbers supported in hardware. A given hardware may support multiple non-deterministic sources. Each source supported by the library is associated with a unique identifier. By specifying the identifier during initialization of the basic generator, you can determine the non-deterministic random number generator to be used in the computations.

The current version of oneMKL provides the interface to

RDRAND

-based non-deterministic source only, defined by identifier VSL_BRNG_RDRAND

[AVX], [IntelSWMan].Some non-deterministic sources may require non-constant time to generate a random number. In this case, multiple requests to a non-deterministic source may be required before the next random number becomes available. In extreme cases, for example, when the non-deterministic source fails, the generator may require infinite time to get the next random number. To avoid such situations, the number of retries for requests to the non-deterministic source is limited to

VSL_BRNG_NONDETERM_NRETRIES

equal to 10. You can redefine the maximum number of retries during the initialization of the non-deterministic random number generator with the vslNewStreamEx

function. For details on the non-deterministic source implementation for Intel® processors, see Chapter 7.3.18 in [IntelSWMan] and Chapter 4.2.2 in [BMT].