## 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: i32) -> 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.