Abstract
Random number generation inspired by <random>
in C++.
The overall idea is that you pass a low-level rng_engine
,
that knows how to generate random integers, to a parametric module
that maps said integers to the desired distribution. Since Futhark
is a pure language, the final random number function(s) will return
both the random number and the new state of the engine. It is the
programmer's responsibility to ensure that the same state is not
used more than once (unless that is what is desired). See the
Examples below.
Synopsis
Description
- ↑module type rng_engine
Low-level modules that act as sources of random numbers in some uniform distribution.
- ↑module int: integral
A module for the type of integers generated by the engine.
- ↑type rng
The state of the engine.
- ↑val rng_from_seed [n]: [n]i32 -> rng
Initialise an RNG state from a seed. Even if the seed array is empty, the resulting RNG should still behave reasonably. It is permissible for this function to process the seed array sequentially, so don't make it too large.
- ↑val split_rng: (n: i64) -> rng -> [n]rng
Split an RNG state into several states. Implementations of this function tend to be cryptographically unsound, so be careful.
- ↑val join_rng [n]: [n]rng -> rng
Combine several RNG states into a single state - typically done with the result of
split_rng
.- ↑val rand: rng -> (rng, int.t)
Generate a single random element, and a new RNG state.
- ↑val min: int.t
The minimum value potentially returned by the generator.
- ↑val max: int.t
The maximum value potentially returned by the generator.
- ↑module type rng_distribution
- ↑module engine: rng_engine
The random number engine underlying this distribution.
- ↑module num: numeric
A module describing the type of values produced by this random distribution.
- ↑type distribution
The dynamic configuration of the distribution.
- ↑val rand: distribution -> engine.rng -> (engine.rng, num.t)
- ↑module linear_congruential_engine
A linear congruential random number generator produces numbers by the recurrence relation
X(n+1) = (a × X(n) + c) mod m
where X is the sequence of pseudorandom values, and
-
m, 0 < m — "modulus"
-
a, 0 < a < m — "multiplier"
-
c, 0 ≤ c < m — "increment"
-
X(0), 0 ≤ X(0) < m — "seed" or "initial value"
-
- ↑module subtract_with_carry_engine
A random number engine that uses the subtract with carry algorithm. Presently quite slow. The size of the state is proportional to the long lag.
- ↑module discard_block_engine
An engine adaptor parametric module that adapts a pseudo-random number generator Engine type by using only
r
elements of each block ofp
elements from the sequence it produces, discarding the rest.The adaptor keeps and internal counter of how many elements have been produced in the current block.
- ↑module shuffle_order_engine
An engine adaptor that adapts an
rng_engine
so that the elements are delivered in a different sequence.The RNG keeps a buffer of
k
generated numbers internally, and when requested, returns a randomly selected number within the buffer, replacing it with a value obtained from its base engine.- ↑module minstd_rand
A
linear_congruential_engine
producingu32
values and initialised witha=48271
,c=0
andm=2147483647
. This is the same configuration as in C++.- ↑module minstd_rand0
A
linear_congruential_engine
producingu32
values and initialised witha=16807
,c=0
andm=2147483647
. This is the same configuration as in C++.- ↑module ranlux24_base
A subtract-with-carry pseudo-random generator of 24-bit numbers, generally used as the base engine for the
ranlux24
generator. It is an instantiation ofsubtract_with_carry_engine
withw=24
,s=10
,r=24
.- ↑module ranlux48_base
A subtract-with-carry pseudo-random generator of 48-bit numbers, generally used as the base engine for the
ranlux48
generator. It is an instantiation ofsubtract_with_carry_engine
withw=48
,s=5
,r=12
.- ↑module ranlux24
A subtract-with-carry pseudo-random generator of 24-bit numbers with accelerated advancement.
It is an instantiation of a
discard_block_engine
withranlux24_base
, with parametersp=223
andr=23
.- ↑module ranlux48
A subtract-with-carry pseudo-random generator of 48-bit numbers with accelerated advancement.
It is an instantiation of a
discard_block_engine
withranlux48_base
, with parametersp=223
andr=23
.- ↑module knuth_b
An engine adaptor that returns shuffled sequences generated with
minstd_rand0
. It is not a good idea to use this RNG in a parallel setting, as the state size is fairly large.- ↑module xorshift128plus
The xorshift128+ engine. Uses two 64-bit words as state.
- ↑module pcg32
PCG32. Has a state space of 128 bits, and produces uniformly distributed 32-bit integers.
- ↑module uniform_int_distribution
This uniform integer distribution generates integers in a given range with equal probability for each, assuming the passed
rng_engine
generates uniformly distributed integers.- ↑module uniform_real_distribution
This uniform integer distribution generates floats in a given range with "equal" probability for each.
- ↑module normal_distribution
Normally distributed floats.
Examples
This program constructs a uniform distribution of single precision
floats using the minstd_rand
as the underlying RNG engine.
The dist
module is constructed at the program top level, while we
use it at the expression level. We use the minstd_rand
module
for initialising the random number state using a seed, and then we
pass that state to the rand
function in the generated
distribution module, along with a description of the distribution
we desire. We get back not just the random number, but also the
new state of the engine.
module dist = uniform_real_distribution f32 minstd_rand
let rng = minstd_rand.rng_from_seed [123]
let (rng, x) = dist.rand (1,6) rng
The rand
function of uniform_real_distribution
simply
takes a pair of numbers describing the range. In contrast,
normal_distribution
takes a record specifying the mean and
standard deviation:
module norm_dist = normal_distribution f32 minstd_rand
let (rng, y) = norm_dist.rand {mean=50, stddev=25} rng
Since both dist
and norm_dist
have been initialised with the
same underlying rng_engine
(minstd_rand
), we can
re-use the same RNG state. This is often convenient when a program
needs to generate random numbers from several different
distributions, as we still only have to manage a single RNG state.
Parallel random numbers
Random number generation is inherently sequential. The rand
functions take an RNG state as input and produce a new RNG state.
This creates challenges when we wish to map
a function f
across
some array xs
, and each application of the function must produce
some random numbers. We generally don't want to pass the exact
same state to every application, as that means each element will
see the exact same stream of random numbers. Common procedure is
to use split_rng
, which creates any number of RNG states from
one, and then pass one to each application of f
:
let rngs = minstd_rand.split_rng n rng
let (rngs, ys) = unzip (map2 f rngs xs)
let rng = minstd.rand.join_rngs rngs
We assume here that the function f
returns not just the result,
but also the new RNG state. Generally, all functions that accept
random number states should behave like this. We subsequently use
join_rngs
to combine all resulting states back into a single
state. Thus, parallel programming with random numbers involves
frequently splitting and re-joining RNG states. For most RNG
engines, these operations are generally very cheap.
See also
The Sobol
module provides a very different
(and inherently parallel) way of generating random numbers, which
may be more suited for Monte Carlo applications.