Lattice Builder Manual Software Package for Constructing Rank-1 Lattices

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- Namespace List
- Namespace Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
Namespaces | Classes | Typedefs | Enumerations | Functions | Variables
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

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.

enum LatCommon::CriterionType

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] .

enum LatCommon::DecompType

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 multiple-recursive generator.\f[1ex] `MWC:` the multiply-with-carry generator.\f[1ex] `KOROBOV:` the Korobov lattice.\f[1ex] `RANK1:` the rank 1 lattice.

enum LatCommon::ImplemCond

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.

enum LatCommon::LatticeType

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] .

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|)\).

enum LatCommon::OutputType

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''.

enum LatCommon::SearchMethod

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().