Overview

This is the user guide and API documentation of LatMRG a collection of executables and a library intended to study the lattice structure of congruential recursive random number generators. LatMRG is free and open source software distributed with the Apache License 2.0 available on Github

Content Outline

This page summarizes the contents and the possible uses of LatMRG. The rest of this guide covers the following:

Theory on Lattices and Theory of Random Numbers contain the theoretical knowledge needed to understand the basics of LatMRG.
Compilation and Executables Usage presents the executable programs and their usage. It also also contains compilation instruction for LatMRG.
Tutorial and Library Usage presents segments of code highlighting some functionnalities of LatMRG
The full API documentation is also available in the Namespace and Classes tabs.
Getting back to Github

The API documentation is automatically generated by Doxygen.

Presentation of LatMRG

LatMRG is a C++ software toolkit for examining theoretical properties of linear congruential or multiple recursive random number generators. Generators of this kind generate a sequence of numbers \(\{x_n \in \mathbb{Z}\ | \ 0 \leq x_n < m\}\) with recurrence of the kind (or equivalent to)

\[ x_n = a_1 x_{n-1} + \cdots + a_k x_{n-k} \pmod m \]

The values outputed by these generators are then transformed as \(u_n = x_n/m\) to give another number sequence \(\{u_n\} \subset [0,1)\). This sequence can then be used as a random stream of \(\mathcal{U}[0,1)\) independent identically distributed random variables. This sequence is NOT random but it appears so with a good choice of \(m\in \mathbb{Z}_{>0}\), \(k>0\) and \(a = (a_1, \ldots, a_k) \in \mathbb{Z}_k\), this is what is called a pseudo-random number sequence.

Given a set of indices \(I = \{i_1, \ldots, i_t\}\) it is possible to use the sequence of \(u_n\) to generate pseudo-random vectors of the form \(v = (u_{c + i_1}, \ldots, u_{c + i_t})\). Define \(\Psi_I = \{(u_{i_1}, \ldots, u_{i_t}) \ | \ 0 \leq x_1, \ldots, x_k < m\}\). This set covers vectors \(v\) for all possible values of \(c\). This is the set of all vectors the generator can produce with indices spacing as in \(I\). The set

\[ L(I) = \{k v + l w \ | \ k,l \in \mathbb{Z},\ v,w \in \Psi_I\} \]

is then a lattice spanned by the vectors produced by the generator. This structure is well know and can be studied extensively. This guide does not cover the theory behind lattices as it would be redundant with what is described in LatticeTester which we is also written by us.

Let \(\ell(I)\) be the shortest non-zero vector of \(L(I)\). It is possible to have an upper bound \(\ell^*(I)\) [mCON99a] on the length of \(\ell_t(I)\) such that \(0 < \ell(I) /\ell^*(I) \leq 1\). Given \(\mathcal{J}\) a set of sets of indices and \(\omega_I \in \mathbb{R},\ I \in \mathcal{J}\), it is possible to compute Figures of Merit on a generator as

\begin{align*} M_\mathcal{J} &= \sum_{I \in \mathcal{J}} \omega_I \ell(I)/\ell^*(I) \\ Q_\mathcal{J} & = \min_{I \in \mathcal{J}} \omega_I \ell(I)/\ell^*(I) \end{align*}

The point of these figures of merit is that for a fixed set \(\mathcal{J}\) they are comparable for different generators. LatMRG builds figures of merit based on the well known spectral test [rKNU97a]. More detail on how which figures of merit are constructed and available in LatMRG can be found in Measures on MRGs.

LatMRG got its name from lattice and MRG and, as its name hints, it is mainly intended as a tool to study the lattice of MRG and MRG-like random number generators. Studying this lattice can provide usefull information about the generator.

It can help assess that the points it outputs are as uniform as possible
It can determine if the points are correlated on only a few hyperplans

But LatMRG can do a few more things:

Study the period of MRG-like generators
Finding parameters with a good lattice structure for such generators. This has to be done in two steps:
- Finding a combination of \(m\) and \(k\)
- Finding a vector \(a\) that has a good lattice for such \(m\) and \(k\)
Test the lattice structure of a generator for a large quantity of \(I\) and build comparable mesures based on them

As a library, LatMRG can also be extended to easily test the lattice structure and search for MRG-like generators given specific constraints on its implementation.