- Generated by
1.8.15
|
LatMRG Guide
1.0
A software package to test and search for new linear congruential random number generators
|
Most use cases of LatMRG should be covered by the executable program, but LatMRG is also distributed as a library to easily expand its functions.
You might want to:
This section first presents the main classes of the library and how to expand them. We then provide a few programming guidelines to expand the software provided in LatMRG. Finally, we present a few examples of its usage as a library.
We present the main classes of LatMRG. This will not cover the details of those classes, which is available in their respective documentation.
If you browse the source code, you will notice that a lot of classes are template classes. This is because the arithmetic can be done with a variable level of precision depending on the usage. Template classes feature readily available template instantiation with relevant types and types combinations in the library.
For integers, types we use are fixed width 64 bits integers int64_t and the arbitrary precision integers of NTL ZZ. For floating point numbers, the template parameters types can be double or RR from NTL. Choosing standard types int64_t and double makes the program perform much faster because of the arithmetic. But they have a limited precision. This is specially important for integers: lattices basis need to be stored exactly for the program to work properly. If you think you might need to store a number greater than 2^63-1, it is best to use arbitrary precision integers.
This topic is discussed more in length latter.
The most important feature of LatMRG is its capacity to represent MRG random number generators and their lattices. The library features two different classes in this regard, depending on the use case.
LatMRG::MRGLattice is the main class to do so. This class allows the the storage of a MRG's parameters (a vector of multipliers, a modulo and an order) and also the reprensentation of a lattice basis for this generator. This class also has an overridable interface to build the basis of the generator lattice for an arbitrary dimension.
The other class to store MRG generators is the LatMRG::MRGComponent class. Just like MRGLattice, this class stores the components of a MRG generator, but it cannot store a lattice basis. This is useful when you want to avoid having to store a heavy object only for generators componenets. This class also bundles a few utility function that can, for example, check if the components stored are that of a full period MRG.
MRGLattice is used as the base class for other MRG generator types classes. Combined generators represented in LatMRG::ComboLattice, MWC generators in LatMRG::MWCLattice and LatMRG::AWCSWBLattice and even MMRG generators in LatMRG::MMRGLattice. Since most generators have an equivalence with MRG, it is practical to just define them with a constructor that initializes the underlying MRGLattice correctly. For example, the next few lines of code (and a few more declaration in the class body) are what initializes a MWCLattice with
\begin{align} x_n & = (e_1 x_{n-1} + \cdots + e_k x_{n-k} + c_{n-1})d\ \mathrm{mod} \ b, \\ c_n & = \lfloor (e_0 x_n + e_1 x_{n-1} + \cdots + e_k x_{n-k} + c_{n-1} )/b \rfloor, \\ u_n & = \sum_{i=1}^\infty x_{n+i-1} b^{-i}. \end{align}
The resulting object can then be used in any function working on MRGLattices seamlessly.
Most of the reduction functions available in LatMRG come from the LatticeTester library. By using this library, it is possible to
LatMRG mainly implements two things, buiding up on LatticeTester
LatMRG::Projections is the class representing projections. It can be considered as a set \(\mathcal{I}\) of sets of indices and can be iterated over to obtain those sets of indices. Once objects of this class have been initialized, they can be used as iterators. This pairs with the buildProjection method inherited from LatticeTester in MRGLattice.
The Test.h file provides with functions that wrap LatticeTester to either reduce a lattice or compute a form on merit on it. Once MRGLattice objects have been initialized, you simply need to build the lattice basis for different projections and call functions from this file on them.
In this section, we will present how to use LatMRG as a library and provide guidelines on how to expand the software.
The first thing anyone programming with LatMRG should know, is that LatMRG HAS TO perform on different types depending on the use case. Therefore, when programming new functions in LatMRG it is necessary to make sure that they are agnostic the possible types that might be used by the different LatMRG objects. Currently LatMRG can use ZZ from the NTL library, as well as fixed width int64_t integers to represent the generators and their basis. It can also represent floating point numbers with both double and RR types. Note that there is one cavehat to the previous statements: the BKZ reduction method (in LatticeTester) requires that integers are of the ZZ type. This is because we did not implement the BKZ reduction and use the NTL version instead. This version does not operate on long integers.
To work around this problem, LatMRG uses templates for most classes. This can feel problematic since these templates are not intended to work with most types ut only a few specific ones. This is mainly meant to reduce code duplication, but also gives us the flexibility to eventually change NTL for another library and not have to rewrite most of our code base. This is also intended to modify the old version of LatMRG that used compile time flags to determine the types.
Template classes in the software look like this:
The first thing to note are the typedefs. Having them means that it is possible to interract with the class and its types and still write types agnostic code by referring to typename LatMRGClass::Int. The other thing to note is that the library instanciates all its templated classes with the types we support. This is meant to reduce compile time when using the library and helps verify that supported types works.
2^32, the result of a multiplication can overflow. Multiplications will occur when building a lattice basis.Although it shouldn't be necessary to add new types of generators in the the software, it is possible that some users would want to include classes to represent specific parameter combinations for certain generator kinds and specialize the lattice construction for those. For all its operation on generators, LatMRG interracts with the base class MRGLattice. This class inherits from IntLattice in LatticeTester and has quite a few functions that can be specialized in subclasses.
To specialize the basis construction, all subclasses for MRGLattice can reimplement the virtual methods buildBasis(int) and incDim(). The first method is intended to build a basis of dimension specified as argument, and the second one increases the basis dimension by one.
The other main function you might want to specialize in MRGLattice is the toString() function. This function returns a string that describes the generator represented by the lattice. There curently is no standard format to be returned by this method and it is left to the user discretion to choose what information is important. For example, for MRGLattice, this only prints the coefficients as
but it could be possible to create a class that represents a MRG with specific choice of coefficients. For example, if the coefficients are chosen as the sum of powers of primes p1, ..., pj one could change the method to print a1 = x1 = p1^e1 + ... + pj^ej.
One of the reasons you might want to use LatMRG is to search for generators. The main tool LatMRG provides for this is its executable, but this means expanding the search functionnality of the software is not as easy as writing a function to generate vectors \((a_1, \ldots, a_k)\) given a strategy. There are two options to search for custom new generators with LatMRG.
First, you can write some sort of script using the library functions to handle the lattices and make the computations. In that case, most, if not all, the logic would have to be written by you. If you want a customizable program, this might get complicated for what should be a "simple" task.
Your other option is to modify the executable of LatMRG to search generators as you need them and apply tests as it can already do. The intention of the executable is to be robust to different types specifications and easily enable users to modify it. We focus on this option here.
To search for generators, the program calls the following function:
This function takes a pointer to a function as an argument. This function passed as an argument is used at each step to search and return the next generator to test. Following this logic, there is only need to implement another function to pass as nextGenerator and to make it such that the program can pass it to Seek().
This means that searching generators with a new method can be done by implementing this method in a new function and modifying the executable for this function to be passed to the search method.
1.8.15