LatMRG Guide
1.0
A software package to test and search for new linear congruential random number generators
|
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
This page summarizes the contents and the possible uses of LatMRG. The rest of this guide covers the following:
The API documentation is automatically generated by Doxygen.
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.
But LatMRG can do a few more things:
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.