Lattice Builder Manual
Software Package for Constructing Rank1 Lattices

This module contains global constants used in LatMRG{} and Lattice Builder. More...
Namespaces  
CoordinateSets  
Sequences of coordinate sets.  
Classes  
class  Base 
This class represents a basis for a lattice. More...  
class  Coordinates 
Set of coordinates. More...  
class  IntLattice 
This class offers tools to manipulate lattice bases. More...  
class  KorobovLattice 
This class implements lattice bases built from a Korobov lattice rule. More...  
class  NormaBestLat 
This class implements the best theoretical bounds on the length of the shortest nonzero vector in a lattice, based on the densest sphere packing in lattices. More...  
class  NormaLaminated 
This class implements theoretical bounds on the length of the shortest nonzero vector in a lattice, based on the densest sphere packing in laminated lattices. More...  
class  Normalizer 
Classes which inherit from this base class are used in implementing bounds on the length of the shortest nonzero vector in a lattice [3] . More...  
class  NormaMinkL1 
This class implements theoretical bounds on the length of the shortest nonzero vector in a lattice, based on the densest sphere packing in space. More...  
class  NormaMinkowski 
This class implements {Minkowski\/}'s theoretical bounds on the length of the shortest nonzero vector in a lattice. More...  
class  NormaRogers 
This class implements the Rogers bounds on the density of sphere packing. More...  
class  OrderDependentWeights 
Orderdependent weights. More...  
class  PODWeights 
Product and orderdependent (POD) weights. More...  
class  ProductWeights 
Product weights. More...  
class  ProjectionDependentWeights 
Projectiondependent weights. More...  
class  Random 
This class generates random numbers (in fact pseudorandom numbers). More...  
class  Rank1Lattice 
class  Reducer 
For a given lattice, this class implements methods to reduce its basis in the sense of Minkowski and to find the shortest nonzero vector of the lattice using prereductions and a branchandbound (BB) algorithm [11] . More...  
class  UniformWeights 
This class is used to implement the same weight for all projections. More...  
class  Weights 
Abstract weights class. More...  
Typedefs  
typedef double  Weight 
Scalar weight type. More...  
Enumerations  
enum  NormType { SUPNORM, L1NORM, L2NORM, ZAREMBANORM } 
Indicates which norm is used to measure the length of vectors. More...  
enum  GenType { LCG, MRG, MWC, KOROBOV, RANK1 } 
Used to identify the type of a generator. More...  
enum  LatticeType { FULL, RECURRENT, ORBIT, PRIMEPOWER } 
Indicates whether to analyze the lattice generated by all possible states, or a sublattice generated by the set of recurrent states or by a subcycle of the generator. More...  
enum  PrimeType { UNKNOWN, PRIME, PROB_PRIME, COMPOSITE } 
Indicates whether an integer is prime, probably prime, composite or its status is unknown (or don't care).  
enum  DecompType { DECOMP, DECOMP_WRITE, DECOMP_READ, DECOMP_PRIME } 
Given an integer \(r\), indicates what to do about the decomposition of \(r\) in its prime factors. More...  
enum  OutputType { TERMINAL, RES, TEX, GEN } 
Indicates in which form and where the results will be sent. More...  
enum  CriterionType { SPECTRAL, BEYER, PALPHA, BOUND_JS } 
Gives the merit criterion for ranking generators or lattices. More...  
enum  NormaType { BESTLAT, LAMINATED, ROGERS, MINKOWSKI, MINKL1, PALPHA_N, NORMA_GENERIC } 
Indicates which normalization is used to compute \(S_t\) in the spectral test, for each dimension \(t\). More...  
enum  CalcType { PAL, NORMPAL, BAL, SEEKPAL } 
Indicates which type of calculation is considered for the \(P_\alpha\) test. More...  
enum  ImplemCond { NO_COND, APP_FACT, POWER_TWO, EQUAL_COEF, ZERO_COEF } 
Indicates which type of conditions are imposed on the coefficients \(a_i\) of a recurrence. More...  
enum  SearchMethod { EXHAUST, RANDOM } 
Indicates the search method used to find good multipliers \(a_i\). More...  
Functions  
long  lFactorial (int t) 
Calculates \(t!\), the factorial of \(t\).  
double  Digamma (double x) 
Returns the value of the logarithmic derivative of the Gamma function \(\psi(x) = \Gamma'(x) / \Gamma(x)\).  
double  BernoulliPoly (int n, double x) 
Evaluates the Bernoulli polynomial \(B_n(x)\) of degree \(n\) at \(x\). More...  
double  Harmonic (long n) 
Computes the \(n\)th harmonic number \(H_n = \sum_{j=1}^n 1/j\).  
double  Harmonic2 (long n) 
Computes the sum \[ \sideset{}{'}\sum_{n/2<j\le n/2}\; \frac 1{j}, \] where the symbol \(\sum^\prime\) means that the term with \(j=0\) is excluded from the sum.  
double  FourierC1 (double x, long n) 
Computes and returns the value of the series (see [8]) \[ S(x, n) = \sum_{j=1}^{n} \frac{\cos(2\pi j x)}{j}. \] Restrictions: \(n>0\) and \(0 \le x \le 1\).  
double  FourierE1 (double x, long n) 
Computes and returns the value of the series \[ G(x, n) = \sideset{}{'}\sum_{n/2<h\le n/2}\; \frac{e^{2\pi i h x}}{h}, \] where the symbol \(\sum^\prime\) means that the term with \(h=0\) is excluded from the sum, and assuming that the imaginary part of \(G(x, n)\) vanishes. More...  
void  MyExit (int status, std::string msg) 
Special exit function. More...  
template<typename T >  
void  swap9 (T &x, T &y) 
Swaps the values of x and y .  
template<typename A , typename B >  
void  conv (A &x, const B &y) 
template<class K , class C , class A >  
std::ostream &  operator<< (std::ostream &out, const std::set< K, C, A > &x) 
}.  
template<class K , class T , class C , class A >  
std::ostream &  operator<< (std::ostream &out, const std::map< K, T, C, A > &x) 
}.  
toString functions  
Useful functions for printing the  
std::string  toStringNorm (NormType) 
Returns the enum constants in this module as strings. More...  
std::string  toStringGen (GenType) 
std::string  toStringLattice (LatticeType) 
std::string  toStringPrime (PrimeType) 
std::string  toStringDecomp (DecompType) 
std::string  toStringOutput (OutputType) 
std::string  toStringCriterion (CriterionType) 
std::string  toStringNorma (NormaType) 
std::string  toStringCalc (CalcType) 
std::string  toStringImplemCond (ImplemCond) 
std::string  toStringSearchMethod (SearchMethod) 
NTL compatibility functions  
void  clear (double &x) 
void  clear (long &x) 
Sets \(x\) to 0.  
void  set9 (long &x) 
bool  IsZero (const long &x) 
Return true if \(x = 0\).  
Division and remainder  
For negative operands, the The negative quotient differs by 1 and the remainder also differs. Thus the following small  
template<typename Int >  
void  Quotient (const Int &a, const Int &b, Int &q) 
void  Modulo (const long &a, const long &b, long &r) 
template<typename Real >  
void  Divide (Real &q, Real &r, const Real &a, const Real &b) 
Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\). More...  
void  Divide (long &q, long &r, const long &a, const long &b) 
template<typename Real >  
void  DivideRound (const Real &a, const Real &b, Real &q) 
void  DivideRound (const long &a, const long &b, long &q) 
Mathematical functions  
void  Euclide (const MScal &a, const MScal &b, MScal &C, MScal &D, MScal &E, MScal &F, MScal &G) 
For given \(a\) and \(b\), returns the values \(C\), \(D\), \(E\), \(F\) and \(G\) such that: \begin{eqnarray*} C a + D b &=& G = \mbox{GCD } (a,b) \\ E a + F b &=& 0. \end{eqnarray*} .  
long  gcd (long a, long b) 
Returns the value of the greatest common divisor of \(a\) and \(b\). More...  
template<typename Real >  
Real  Round (Real x) 
Rounds to the nearest integer value.  
bool  IsPrime (unsigned long n) 
Returns true if \(n\) is prime, false otherwise.  
Vector operations  
template<typename Vect >  
void  SetZero (Vect &A, int d) 
Sets components \([0..d]\) of \(A\) to 0.  
template<typename Vect , typename Scal >  
void  ModifVect (Vect &A, Vect &B, const Scal &x, int n) 
Adds vector \(B\) multiplied by \(x\) to vector \(A\) using components \([1..n]\), and puts the result in \(A\).  
template<typename Vect , typename Scal >  
void  ModifVect (MVect &A, Vect &B, const Scal &x, int n) 
Adds vector \(B\) multiplied by \(x\) to vector \(A\) using components \([1..n]\), and puts the result in \(A\).  
template<typename V , typename Scal >  
void  ProdScal (const V &A, const V &B, int n, Scal &D) 
template<typename Scal >  
void  ProdScal (const BVect &A, const BVect &B, int n, Scal &D) 
Computes the scalar product of vectors \(A\) and \(B\), using components \([1..n]\), and puts the result in \(D\).  
template<typename Vect >  
void  ChangeSign (Vect &A, int n) 
Changes the sign of the components \([1..n]\) of vector \(A\).  
long  GCD2vect (std::vector< long > V, int k, int n) 
Computes the greatest common divisor of \(V[k],\ldots,V[n]\).  
template<typename Vect , typename Scal >  
void  CalcNorm (const Vect &V, int n, Scal &S, NormType norm) 
Computes the norm norm of vector \(V\), using components \([1..n]\), and puts the result in \(S\).  
Matrices  
template<typename Matr >  
bool  CheckTriangular (const Matr &A, int dim, const MScal &m) 
Checks that square matrix \(A\) is upper triangular (modulo \(m\)) for dimensions 1 to dim .  
template<typename Matr >  
void  Triangularization (Matr &W, Matr &V, int lin, int col, const MScal &m) 
Performs an integer triangularization operation modulo \(m\) on the matrix \(W\) to obtain an upper triangular matrix \(V\), dual to \(W\). More...  
template<typename Matr >  
void  CalcDual (const Matr &A, Matr &B, int d, const MScal &m) 
Calculates the \(m\)dual of the matrix A . More...  
Printing functions and operators  
template<typename Vect >  
std::string  toString (const Vect &A, int c, int d, const char *sep) 
Prints components \([c..d]\) of vector \(A\) as a string. More...  
template<typename Vect >  
std::string  toString (const Vect &A, int c, int d) 
Prints components \([c..d]\) of vector \(A\) as a string.  
template<typename Vect >  
std::string  toString (const Vect &A, int d) 
Prints components \([1..d]\) of vector \(A\) as a string.  
template<class T1 , class T2 >  
std::ostream &  operator<< (std::ostream &out, const std::pair< T1, T2 > &x) 
Streaming operator for vectors. More...  
template<class T , class A >  
std::ostream &  operator<< (std::ostream &out, const std::vector< T, A > &x) 
Streaming operator for vectors. More...  
Variables  
const unsigned long  TWO_EXP [] 
Table of powers of 2: TWO_EXP [ \(i\)] \(= 2^i\), \(i=0, 1, \ldots\) for \(i \le 31\) for 32bits machines, and \(i \le 63\) for 64bits machines.  
This module contains global constants used in LatMRG{} and Lattice Builder.
This module describes useful tools and interface functions to Boost or NTL.
This module implements a few useful mathematical functions.
typedef double LatCommon::Weight 
Scalar weight type.
Weight
, but it might be wise to leave this typedef
in case we decide to use long Weight
at some point. enum LatCommon::CalcType 
Indicates which type of calculation is considered for the \(P_\alpha\) test.
CalcType.def
PAL
is for the \(P_\alpha\) test. \f[1ex] BAL
is for the bound on the \(P_\alpha\) test. \f[1ex] NORMPAL
is for the \(P_\alpha\) test PAL
, with the result normalized over the BAL
bound. \f[1ex] SEEKPAL
is for the \(P_\alpha\) seek, which searches for good values of the multiplier.
Gives the merit criterion for ranking generators or lattices.
BEYER:
the figure of merit is the Beyer quotient \(Q_T\).\f[1ex] SPECTRAL:
the figure of merit \(S_T\) is based on the spectral test.\f[1ex] PALPHA:
the figure of merit is based on \(P_\alpha\).\f[1ex] BOUND_JS:
the figure of merit is based on the JoeSinescu bound [17] .
Given an integer \(r\), indicates what to do about the decomposition of \(r\) in its prime factors.
DECOMP:
means that the program will factorize \(r\).\f[1ex] DECOMP_WRITE:
means that the program will factorize \(r\) and writes the factors in a file.\f[1ex] DECOMP_READ:
means that \(r\) is already factorized, and the factors will be read from a file.\f[1ex] DECOMP_PRIME:
means that \(r\) is prime. No factorization will be done.
enum LatCommon::GenType 
Used to identify the type of a generator.
If a generator is of type MWC
, it is converted to its corresponding MRG
by the program.LCG:
the linear congruential generator.\f[1ex] MRG:
the multiplerecursive generator.\f[1ex] MWC:
the multiplywithcarry generator.\f[1ex] KOROBOV:
the Korobov lattice.\f[1ex] RANK1:
the rank 1 lattice.
Indicates which type of conditions are imposed on the coefficients \(a_i\) of a recurrence.
NO_COND:
no condition is imposed on the coefficients.\f[1ex] APP_FACT:
the coefficients must satisfy the ``approximate factoring'' condition \(a_i (m\mod a_i) < m\). Congruential generators are easier to implement under this condition [13] .\f[1ex] POWER_TWO:
the coefficients must be sums or differences of powers of 2.\f[1ex] EQUAL_COEF:
all the coefficients must be equal by groups: a first group all equal to a first number, a second group all equal to a second number, and so on. \f[1ex] ZERO_COEF:
all the coefficients must be equal to 0, except for a select fews.
Indicates whether to analyze the lattice generated by all possible states, or a sublattice generated by the set of recurrent states or by a subcycle of the generator.
FULL:
The complete lattice, generated by all possible initial states, will be analyzed.\f[1ex] RECURRENT:
If the (combined) generator has transient states, then the lattice analyzed will be the sublattice generated by the set of recurrent states.\f[1ex] ORBIT:
The grid generated by the (forward) orbit of a state of the (combined) generator is analyzed. This state is specified as follows. On the following \(J\) lines, the initial state for each component must be given. This is an integer vector with a number of components equal to the order of the component.\f[1ex] PRIMEPOWER:
In the case where some component is an MLCG whose modulus is a power of a prime \(p\), then the states visited over a single orbit (subcycle) of that component generate a sublattice (when \(a \equiv 1 \bmod{p}\)) or belong to the union of \(p1\) sublattices (otherwise). If LatticeType
takes this value, and a component is a MLCG ( \(k=1\)), and if the modulus of that MLCG is given in the data file in the form (b): \((x\ y\ z)\) with \(z=0\) and \(x\) prime, then what is analyzed is one of those sublattices. This is done by dividing the modulus by the appropriate power of \(p\), as described in [12] . For example, if \(p=2\) and \(a \mod 8 = 5\), then the modulus is divided by 4 as in [7], [9] .
enum LatCommon::NormaType 
Indicates which normalization is used to compute \(S_t\) in the spectral test, for each dimension \(t\).
BESTLAT:
the value used for \(d_t^*\) corresponds to the best lattice.\f[1ex] LAMINATED:
the value used for \(d_t^*\) corresponds to the best emph lattice.\f[1ex] ROGERS:
the value for \(d_t^*\) is obtained from emph bound on the density of sphere packing.\f[1ex] MINKOWSKI:
the value for \(d_t^*\) is obtained from emph theoretical bounds on the length of the shortest nonzero vector in the lattice using the \({\cal L}_2\) norm.\f[1ex] MINKL1:
the value for \(d_t^*\) is obtained from the theoretical bounds on the length of the shortest nonzero vector in the lattice using the \({\cal L}_1\) norm.\f[1ex] PALPHA_N:
the case of the \(P_\alpha\) test.\f[1ex] NORMA_GENERIC:
the trivial normalization (= 1) used for the generic case when no useful normalization constant is known.
enum LatCommon::NormType 
Indicates which norm is used to measure the length of vectors.
For \(X = (x_1,\dots,x_t)\),SUPNORM
corresponds to \(\Vert X\Vert = \max (x_1,\dots,x_t)\).\f[1ex] L1NORM
corresponds to \(\Vert X\Vert = x_1+\cdots+x_t\).\f[1ex] L2NORM
corresponds to \(\Vert X\Vert = (x_1^2+\cdots+x_t^2)^{1/2}\).\f[1ex] ZAREMBANORM
corresponds to \(\Vert X\Vert = \max(1, x_1)\cdots\max(1, x_t)\).
Indicates in which form and where the results will be sent.
co:output
TERMINAL:
the results will appear only on the terminal screen.\f[1ex] RES:
the results will be in plain text format and sent to a file with extension ``.res''.\f[1ex]
TEX:
the results will be in \(\mbox{\LaTeX}\) format and sent to a file with extension ``.tex''.\f[1ex]
GEN:
the results will be sent to a file with extension ``.gen''.
Indicates the search method used to find good multipliers \(a_i\).
EXHAUST:
the search will be exhaustive over the chosen regions.\f[1ex] RANDOM:
the search will be random over the chosen regions.
double LatCommon::BernoulliPoly  (  int  n, 
double  x  
) 
Evaluates the Bernoulli polynomial \(B_n(x)\) of degree \(n\) at \(x\).
The first Bernoulli polynomials are:
\begin{align*} B_0(x) &= 1 \\ B_1(x) &= x  1/2 \\ B_2(x) &= x^2x+1/6 \\ B_3(x) &= x^3  3x^2/2 + x/2 \\ B_4(x) &= x^42x^3+x^21/30 \\ B_5(x) &= x^5  5x^4/2 + 5x^3/3  x/6 \\ B_6(x) &= x^63x^5+5x^4/2x^2/2+1/42 \\ B_7(x) &= x^7  7x^6/2 + 7x^5/2  7x^3/6 + x/6 \\ B_8(x) &= x^84x^7+14x^6/3  7x^4/3 +2x^2/31/30. \end{align*}
Only degrees \(n \le 8\) are programmed for now.
void LatCommon::CalcDual  (  const Matr &  A, 
Matr &  B,  
int  d,  
const MScal &  m  
) 
Calculates the \(m\)dual of the matrix A
.
The result is placed in the matrix B
. Only the first \(d\) lines and columns are considered.

inline 
Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\).
Truncates \(q\) to the nearest integer towards 0. One always has \(a = qb + r\) and \(r < b\).
double LatCommon::FourierE1  (  double  x, 
long  n  
) 
Computes and returns the value of the series
\[ G(x, n) = \sideset{}{'}\sum_{n/2<h\le n/2}\; \frac{e^{2\pi i h x}}{h}, \]
where the symbol \(\sum^\prime\) means that the term with \(h=0\) is excluded from the sum, and assuming that the imaginary part of \(G(x, n)\) vanishes.
Restrictions: \(n>0\) and \(0 \le x \le 1\).
long LatCommon::gcd  (  long  a, 
long  b  
) 
Returns the value of the greatest common divisor of \(a\) and \(b\).
long
et les ZZ
(voir fichier ZZ.h) void LatCommon::MyExit  (  int  status, 
std::string  msg  
) 
Special exit function.
status
is the code to return to the system, msg
is the message to print on exit.
std::ostream& LatCommon::operator<<  (  std::ostream &  out, 
const std::pair< T1, T2 > &  x  
) 
Streaming operator for vectors.
Formats a pair as: (first,second).
std::ostream& LatCommon::operator<<  (  std::ostream &  out, 
const std::vector< T, A > &  x  
) 
Streaming operator for vectors.
Formats a vector as: [ val1, ..., valN ]
.
std::string LatCommon::toString  (  const Vect &  A, 
int  c,  
int  d,  
const char *  sep  
) 
Prints components \([c..d]\) of vector \(A\) as a string.
Components are separated by string sep
.
Referenced by toString().
std::string LatCommon::toStringNorm  (  NormType  ) 
Returns the enum
constants in this module as strings.
Const
should be a class containing these methods. void LatCommon::Triangularization  (  Matr &  W, 
Matr &  V,  
int  lin,  
int  col,  
const MScal &  m  
) 
Performs an integer triangularization operation modulo \(m\) on the matrix \(W\) to obtain an upper triangular matrix \(V\), dual to \(W\).
However, the matrix \(W\) will be transformed too in order to preserve duality. Only the first lin
lines and the first col
columns of the matrices will be considered (counting indices from 1; line 0 and column 0 must be there but are unused).