Many problems in engineering, finance and statistics can not be solved by direct methods, but a great number of them can be solved approximately using randomized algorithms. All those algorithms need flexible and efficient pseudo-random number generators. An effective implementation of PRNG in the F# language is somewhat tricky.

The F# language is based on .Net framework, which already provides a fast pseudo-random generator class System.Random, but it meets only certain statistical requirements for randomness. However, there are two classes of generators that have good performance:

• Combined multiple recursive generators (e.g., L’Ecuyer’s MRG32k3a)
• Twisted general feedback shift register generators (e.g., Matsumoto and Nishimura’s MT19937ar)

Despite the fact that MT19937ar has longer period than MRG32k3a, the state space in MT19937ar is very large and it is somewhat slow. Thus, MRG32k3a becomes a better alternative for many use cases.

Algorithm

MRG32k3a is just one of several good parameters sets that L’Ecuyer obtained for CMRGs 1. It has two components of order 3. The state at step $n$ is a pair of vectors $S_{1,n}=(s_{1,n},s_{1,n+1}, s_{1,n+2})$ and $S_{2,n}=(s_{2,n},s_{2,n+1}, s_{2,n+2})$, which change according to the linear recurrences:

The uniformly distributed output $u_n$ is obtained by

Implementation

Two key requirement for the random number generator are the computational performance and minimal memory consumption. MRG32k3a algorithm requires only a pair of 3 element double valued arrays for storing the current generator state, but F# arrays are heap allocated. Fortunately, the F# language supports structure types, which can be allocated on the stack:

The implementation of MRG32k3a gets a reference to State32k3a structure and updates its fields. In this way no intermediate object allocation and copy happens, and the computational performance is close to the C implementation.

Nonetheless, it is possible to create a nice functional wrapper around the low level implementation:

This implementaion returns a closure that can be used for generating a sequence of random numbers:

Though, the price for this nice wrapper is high enough. It involves a heap allocated box for the structure and additional copy operations for reading/writing the structure from the box.

Conslusions

Despite the fact that pure functions and immutable structures are preferable in the most cases because they reduce the number of mistakes, it is important to have clearly designed low level functions for advanced optimizations. Unlike R, Python and other scripting languages, F# has no language border between high level and low level implementations, and, thus, facilitates reuse of low level implementations.

1. L’Ecuyer Good parameters and implementations for combined multiple recursive random number generators // Operations Research. - 1999. - 47(1) - pp. 159-164.