PCGRandom¶
Usage
use Random.PCGRandom;
or
import Random.PCGRandom;
Permuted Linear Congruential Random Number Generator
This module provides PCG random number generation routines. See http://www.pcg-random.org/ and the paper, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation by M.E. O’Neill.
It also includes some Chapel-specific features, such as generating real, imag, and complex numbers; and generating numbers in a range in parallel. These features are not available in the reference implementations of PCG.
The related module PCGRandomLib
provides a lower-level interface to
many PCG functions.
Note
The interface provided by this module is expected to change.
- class PCGRandomStream¶
Models a stream of pseudorandom numbers generated by the PCG random number generator. See http://www.pcg-random.org/ and the paper, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation by M.E. O’Neill.
This class builds upon the
pcg_setseq_64_xsh_rr_32_rng
PCG RNG which has 64 bits of state and 32 bits of output.While the PCG RNG used here is believed to have good statistical properties, it is not suitable for generating key material for encryption since the output of this RNG may be predictable. Additionally, if statistical properties of the random numbers are very important, another strategy may be required.
We have good confidence that the random numbers generated by this class match the C PCG reference implementation and have specifically verified equal output given the same seed. However, this implementation differs from the C PCG reference implementation in how it produces random integers within particular bounds (with
PCGRandomStream.getNext
using min and max arguments). In addition, this implementation directly supports the generation of random real values, unlike the C PCG implementation.Smaller numbers, such as uint(8) or uint(16), are generated from the high-order bits of the 32-bit output.
To generate larger numbers, several 32-bit-output RNGs are ganged together. This strategy is recommended by the author of PCG (and demonstrated in the file pcg32x2-demo.c. Each of these 32-bit RNGs has a different sequence constant and so will be independent and uncorrelated. For example, to generate 128-bit complex numbers, this RNG will use 4 ganged 32-bit PCG RNGs with different sequence constants. One impact of this approach is that this implementation will only generate 2**64 different complex numbers with a given seed (for example).
This class also supports generating integers within particular bounds. When that is required, this class uses a strategy different from the PCG reference implementation in order to work better in a parallel setting. In particular, when more than 1 random value is required as part of generating a value in a range, conceptually it uses more ganged-together RNGs (as with the 32x2 strategy). Each new value beyond the first that is computed will be computed with a different ganged-together RNG. This strategy is meant to avoid statistical bias. While we have tested this strategy to our satisfaction, it has not been subject to rigorous analysis and may have undesirable statistical properties.
When generating a real, imaginary, or complex number, this implementation uses the strategy of generating a 64-bit unsigned integer and then multiplying it by 2.0**-64 in order to convert it to a floating point number. While this does construct a uniform distribution on rounded floating point values, it leaves out many possible real values (for example, 2**-128). We believe that this strategy has reasonable statistical properties. One side effect of this strategy is that the real number 1.0 can be generated because of rounding. The real number 0.0 can be generated because PCG can produce the value 0 as a random integer.
We have tested this implementation with TestU01 (available at http://simul.iro.umontreal.ca/testu01/tu01.html ). We measured our implementation with TestU01 1.2.3 and the Crush suite, which consists of 144 statistical tests. The results were:
no failures for generating uniform reals
1 failure for generating 32-bit values (which is also true for the reference version of PCG with the same configuration)
0 failures for generating 64-bit values (which we provided to TestU01 as 2 different 32-bit values since it only accepts 32 bits at a time)
0 failures for generating bounded integers (which we provided to TestU01 by requesting values in [0..,2**31+2**30+1) until we had two values < 2**31, removing the top 0 bit, and then combining the top 16 bits into the value provided to TestU01).
- type eltType¶
Specifies the type of value generated by the PCGRandomStream. All numeric types are supported: int, uint, real, imag, complex, and bool types of all sizes.
- const seed: int(64)¶
The seed value for the PRNG.
- param parSafe: bool = true¶
Indicates whether or not the PCGRandomStream needs to be parallel-safe by default. If multiple tasks interact with it in an uncoordinated fashion, this must be set to true. If it will only be called from a single task, or if only one task will call into it at a time, setting to false will reduce overhead related to ensuring mutual exclusion.
- proc init(type eltType, seed: int(64) = SeedGenerator.currentTime, param parSafe: bool = true)¶
Creates a new stream of random numbers using the specified seed and parallel safety.
- Arguments
eltType : type – The element type to be generated.
seed : int(64) – The seed to use for the PRNG. Defaults to currentTime from
RandomSupport.SeedGenerator
. Can be any int(64) value.parSafe : bool – The parallel safety setting. Defaults to true.
- proc getNext(type resultType = eltType): resultType¶
Returns the next value in the random stream.
Generated reals are in [0,1] - both 0.0 and 1.0 are possible values. Imaginary numbers are analogously in [0i, 1i]. Complex numbers will consist of a generated real and imaginary part, so 0.0+0.0i and 1.0+1.0i are possible.
Generated integers cover the full value range of the integer.
- Arguments
resultType – the type of the result. Defaults to
eltType
. resultType must be the same or a smaller size number.- Returns
The next value in the random stream as type resultType.
- proc getNext(min: eltType, max: eltType): eltType
Return the next random value but within a particular range. Returns a number in [min, max] (inclusive). Halts if checks are enabled and
min > max
.Note
For integers, this class uses a strategy for generating a value in a particular range that has not been subject to rigorous study and may have statistical problems.
For real numbers, this class generates a random value in [max, min] by computing a random value in [0,1] and scaling and shifting that value. Note that not all possible floating point values in the interval [min, max] can be constructed in this way.
- proc getNext(type resultType, min: resultType, max: resultType): resultType
As with getNext(min, max) but allows specifying the result type.
- proc skipToNth(n: integral) throws¶
Advances/rewinds the stream to the n-th value in the sequence. The first value corresponds to n=0. n must be >= 0, otherwise an IllegalArgumentError is thrown.
- Arguments
n : integral – The position in the stream to skip to. Must be >= 0.
- Throws
IllegalArgumentError – When called with negative n value.
- proc getNth(n: integral): eltType throws¶
Advance/rewind the stream to the n-th value and return it (advancing the stream by one). n must be >= 0, otherwise an IllegalArgumentError is thrown. This is equivalent to
skipToNth()
followed bygetNext()
.- Arguments
n : integral – The position in the stream to skip to. Must be >= 0.
- Returns
The n-th value in the random stream as type
eltType
.- Throws
IllegalArgumentError – When called with negative n value.
- proc fillRandom(arr: [] eltType)¶
Fill the argument array with pseudorandom values. This method is identical to the standalone
fillRandom
procedure, except that it consumes random values from thePCGRandomStream
object on which it’s invoked rather than creating a new stream for the purpose of the call.- Arguments
arr : []
eltType
– The array to be filled
- proc choice(x: [?dom], size: ?sizeType = none, replace = true, prob: ?probType = none) throws¶
Returns a random sample from a given 1-D array,
x
.- Arguments
x – a 1-D array with values that will be sampled from.
size – An optional integral value specifying the number of elements to choose, or a domain specifying the dimensions of the sampled array to be filled, otherwise a single element will be chosen.
replace – an optional
bool
specifying whether or not to sample with replacement, i.e. elements will only be chosen up to one time whenreplace=false
.prob – an optional 1-D array that contains probabilities of choosing each element of
x
, otherwise elements will be chosen over a uniform distribution.prob
must have integral or real element type, with no negative values and at least one non-zero value. The size must be equal to that ofx.domain
.
- Returns
An element chosen from
x
ifsize == 1
, or an array of element chosen fromx
ifsize > 1
orsize
is a domain.- Throws
IllegalArgumentError – if
x.size == 0
, ifx.size != prob.size
, ifprob
contains a negative value, ifprob
has no non-zero values, ifsize < 1 || size.size < 1
, ifreplace=false
andsize > x.size || size.size > x.size
- proc choice(x: range(stridable = ?), size: ?sizeType = none, replace = true, prob: ?probType = none) throws
Returns a random sample from a given bounded range,
x
.- Arguments
x – a bounded range with values that will be sampled from.
size – An optional integral value specifying the number of elements to choose, or a domain specifying the dimensions of the sampled array to be filled, otherwise a single element will be chosen.
replace – an optional
bool
specifying whether or not to sample with replacement, i.e. elements will only be chosen up to one time whenreplace=false
.prob – an optional 1-D array that contains probabilities of choosing each element of
x
, otherwise elements will be chosen over a uniform distribution.prob
must have integral or real element type, with no negative values and at least one non-zero value. The size must be equal to that ofx
.
- Returns
An element chosen from
x
ifsize == 1
, or an array of element chosen fromx
ifsize > 1
orsize
is a domain.- Throws
IllegalArgumentError – if
x.size == 0
, ifx.size != prob.size
, ifprob
contains a negative value, ifprob
has no non-zero values, ifsize < 1 || size.size < 1
, ifreplace=false
andsize > x.size || size.size > x.size
. ifisBoundedRange(x) == false
- proc choice(x: domain, size: ?sizeType = none, replace = true, prob: ?probType = none) throws
Returns a random sample from a given 1-D domain,
x
.- Arguments
x – a 1-D dom with values that will be sampled from.
size – An optional integral value specifying the number of elements to choose, or a domain specifying the dimensions of the sampled array to be filled, otherwise a single element will be chosen.
replace – an optional
bool
specifying whether or not to sample with replacement, i.e. elements will only be chosen up to one time whenreplace=false
.prob – an optional 1-D array that contains probabilities of choosing each element of
x
, otherwise elements will be chosen over a uniform distribution.prob
must have integral or real element type, with no negative values and at least one non-zero value. The size must be equal to that ofx
.
- Returns
An element chosen from
x
ifsize == 1
, or an array of element chosen fromx
ifsize > 1
orsize
is a domain.- Throws
IllegalArgumentError – if
x.size == 0
, ifx.size != prob.size
, ifprob
contains a negative value, ifprob
has no non-zero values, ifsize < 1 || size.size < 1
, ifreplace=false
andsize > x.size || size.size > x.size
.
- proc shuffle(arr: [?D] ?eltType)¶
Randomly shuffle a 1-D array.
- proc permutation(arr: [] eltType)¶
Produce a random permutation, storing it in a 1-D array. The resulting array will include each value from low..high exactly once, where low and high refer to the array’s domain.
- proc iterate(D: domain, type resultType = eltType)¶
Returns an iterable expression for generating D.size random numbers. The RNG state will be immediately advanced by D.size before the iterable expression yields any values.
The returned iterable expression is useful in parallel contexts, including standalone and zippered iteration. The domain will determine the parallelization strategy.
- Arguments
D – a domain
resultType – the type of number to yield
- Returns
an iterable expression yielding random resultType values