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

module type rng_engine = {
module int: integral
type rng
val rng_from_seed [n]: [n]i32 -> rng
val split_rng: (n: i64) -> rng -> [n]rng
val join_rng [n]: [n]rng -> rng
val rand: rng -> (rng, int.t)
val min: int.t
val max: int.t
}
module type rng_distribution = {
module engine: rng_engine
module num: numeric
type distribution
val rand: distribution -> engine.rng -> (engine.rng, num.t)
}
module linear_congruential_engine: (T: integral) -> (P: {
val a: T.t
val c: T.t
val m: T.t
}) -> rng_engine with int.t = T.t with rng = T.t
module subtract_with_carry_engine: (T: integral) -> (P: {
val w: i32
val r: i32
val s: i32
}) -> rng_engine with int.t = T.t
module discard_block_engine: (K: {
val p: i32
val r: i32
}) -> (E: rng_engine) -> rng_engine with int.t = E.int.t
module shuffle_order_engine: (K: {
val k: i32
}) -> (E: rng_engine) -> rng_engine with int.t = E.int.t
module minstd_rand: rng_engine with int.t = u32
module minstd_rand0: rng_engine with int.t = u32
module ranlux24_base: rng_engine with int.t = u32
module ranlux48_base: rng_engine with int.t = u64
module ranlux24: rng_engine with int.t = u32
module ranlux48: rng_engine with int.t = u64
module knuth_b: rng_engine with int.t = u32
module xorshift128plus: rng_engine with int.t = u64
module pcg32: rng_engine with int.t = u32
module uniform_int_distribution: (D: integral) -> (E: rng_engine) -> rng_distribution with num.t = D.t with engine.rng = E.rng with distribution = (D.t, D.t)
module uniform_real_distribution: (R: real) -> (E: rng_engine) -> rng_distribution with num.t = R.t with engine.rng = E.rng with distribution = (R.t, R.t)
module normal_distribution: (R: real) -> (E: rng_engine) -> rng_distribution with num.t = R.t with engine.rng = E.rng with distribution = {mean: R.t, stddev: R.t}

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 of p 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 producing u32 values and initialised with a=48271, c=0 and m=2147483647. This is the same configuration as in C++.

↑module minstd_rand0

A linear_congruential_engine producing u32 values and initialised with a=16807, c=0 and m=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 of subtract_with_carry_engine with w=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 of subtract_with_carry_engine with w=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 with ranlux24_base, with parameters p=223 and r=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 with ranlux48_base, with parameters p=223 and r=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.