Lattice Builder Manual
Software Package for Constructing Rank-1 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 |
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 | |
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 32-bits machines, and \(i \le 63\) for 64-bits 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 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.
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.
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] .
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^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.
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).