Lattice Builder Manual
Software Package for Constructing Rank-1 Lattices
LatCommon Namespace Reference

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
 Order-dependent weights. More...
 
class  PODWeights
 Product and order-dependent (POD) weights. More...
 
class  ProductWeights
 Product weights. More...
 
class  ProjectionDependentWeights
 Projection-dependent weights. More...
 
class  Random
 This class generates random numbers (in fact pseudo-random 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 non-zero vector of the lattice using pre-reductions and a branch-and-bound (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 sub-lattice generated by the set of recurrent states or by a sub-cycle 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 enum constants in this module.

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 / and % operators do not give the same results for NTL large integers ZZ and for primitive types int and long.

The negative quotient differs by 1 and the remainder also differs. Thus the following small inline functions for division and remainder.

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 32-bits machines, and \(i \le 63\) for 64-bits machines.
 

Detailed Description

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.

Note
Richard: Most of these are used only in LatMRG; thus should separate this in two different files: one common and one in LatMRG.

Typedef Documentation

typedef double LatCommon::Weight

Scalar weight type.

Note
We could have used Weight, but it might be wise to leave this typedef in case we decide to use long Weight at some point.

Enumeration Type Documentation

Indicates which type of calculation is considered for the \(P_\alpha\) test.

CalcType.defPAL 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 Joe-Sinescu 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.

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 multiple-recursive generator.\f[1ex] MWC: the multiply-with-carry 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 sub-lattice generated by the set of recurrent states or by a sub-cycle 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 sub-lattice 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 (sub-cycle) of that component generate a sub-lattice (when \(a \equiv 1 \bmod{p}\)) or belong to the union of \(p-1\) sub-lattices (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 sub-lattices. 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] .

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.

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:outputTERMINAL: 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.

Function Documentation

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^2-x+1/6 \\ B_3(x) &= x^3 - 3x^2/2 + x/2 \\ B_4(x) &= x^4-2x^3+x^2-1/30 \\ B_5(x) &= x^5 - 5x^4/2 + 5x^3/3 - x/6 \\ B_6(x) &= x^6-3x^5+5x^4/2-x^2/2+1/42 \\ B_7(x) &= x^7 - 7x^6/2 + 7x^5/2 - 7x^3/6 + x/6 \\ B_8(x) &= x^8-4x^7+14x^6/3 - 7x^4/3 +2x^2/3-1/30. \end{align*}

Only degrees \(n \le 8\) are programmed for now.

template<typename Matr >
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.

template<typename Real >
void LatCommon::Divide ( Real &  q,
Real &  r,
const Real &  a,
const Real &  b 
)
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\).

Note
Richard: Il y a déjà des fonctions GCD dans NTL, pour les 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.

template<class T1 , class T2 >
std::ostream& LatCommon::operator<< ( std::ostream &  out,
const std::pair< T1, T2 > &  x 
)

Streaming operator for vectors.

Formats a pair as: (first,second).

template<class T , class A >
std::ostream& LatCommon::operator<< ( std::ostream &  out,
const std::vector< T, A > &  x 
)

Streaming operator for vectors.

Formats a vector as: [ val1, ..., valN ].

template<typename Vect >
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.

Note
Richard: These are global methods for now, but maybe Const should be a class containing these methods.
template<typename Matr >
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).

References Euclide(), and IsZero().