Lattice namespace. More...

Namespaces
namespace	CoordinateSets
	A namespace containing different implementation of sets of coordinates.
namespace	Random
	This class generates random numbers (in fact pseudo-random numbers).

Classes
class	BasisConstruction
	This class implements general methods to perform a lattice basis construction from a set of vectors, as well as general methods to obtain the dual lattice basis depending on the current lattice basis. More...
class	Config
	This class contains a configuration that can be passed to a LatticeAnalysis object to perform a computation. More...
class	Coordinates
	This is basically a std::set<std::size_t>. More...
class	IntFactor
	The objects of this class are the "prime" factors in the decomposition of a positive integer. More...
class	IntLattice
	This class is a skeleton for the implementation of different types of lattices. More...
class	IntLatticeBasis
	This class represents a lattice and its basis and offers tools to do basic manipulations on lattice bases. More...
class	Lacunary
	This class represents a set of indices with lacunary values. More...
class	LatticeAnalysis
	Objects of this class can perform various tests on lattices. More...
struct	LLLConstr
class	NormaBestBound
	This class implements upper bounds on the lenght of the shortest nonzero vector in a lattice. More...
class	NormaBestLat
	This class implements upper bounds on the lenght of the shortest nonzero vector in a lattice. More...
class	NormaLaminated
	This class implements upper bounds on the lenght of the shortest nonzero vector in a lattice. 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. 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 LOWER bound on the length of the shortest non-zero vector in a lattice. More...
class	NormaPalpha
	This class implements theoretical bounds on the values of \(P_{\alpha}\) for a lattice (see class Palpha). More...
class	NormaRogers
	This class implements upper bounds on the lenght of the shortest nonzero vector in a lattice. More...
class	OrderDependentWeights
	Order-dependent weights. More...
class	ParamReader
	Utility class that can be used to read different kind of data from a file. More...
class	PODWeights
	Product and order-dependent (POD) weights. More...
class	ProductWeights
	Product weights. More...
class	ProjectionDependentWeights
	Projection-dependent weights. More...
class	Rank1Lattice
	This class implements a general rank 1 lattice. More...
class	Reducer
	This class implements (or wraps from NTL) all the functions that are needed to reduce a basis. More...
class	Types
	Sets standard typedef’s for the types that can be used in LatticeTester. More...
class	UniformWeights
	This class is used to implement the same weight for all projections. More...
class	Weights
	Abstract class representing Weights for figures of merit. More...
class	Writer
	This is an abstract class that represents an interface to Writer classes. More...
class	WriterRes
	This class is a simple implementation of the Writer abstract class to write in plain text format on the stream. More...

Enumerations
enum	NormType { SUPNORM = 1 , L1NORM = 2 , L2NORM = 3 , ZAREMBANORM = 4 }
	Indicates which norm is used to measure the length of vectors. More...
enum	OutputType { TERM , RES , TEX , GEN }
	Indicates in which form and where the results will be sent. More...
enum	ProblemType { BASIS , DUAL , REDUCTION , SHORTEST , MERIT }
	An enum listing the problems that LatticeTester can solve.
enum	PrecisionType { DOUBLE , QUADRUPLE , EXPONENT , ARBITRARY , EXACT }
	Indicates in which precision the NTL algorithms will be perfoms : DOUBLE – double QUADRUPLE – quad_float (quasi quadruple precision) this is useful when roundoff errors can cause problems EXPONENT – xdouble (extended exponent doubles) this is useful when numbers get too big ARBITRARY – RR (arbitrary precision floating point) this is useful for large precision and magnitudes Generally speaking, the choice DOUBLE will be the fastest, but may be prone to roundoff errors and/or overflow.
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	CriterionType { LENGTH , SPECTRAL , BEYER , PALPHA , BOUND_JS }
	Gives the merit criterion for ranking generators or lattices. More...
enum	NormaType { BESTLAT , BESTBOUND , LAMINATED , ROGERS , MINK , MINKL1 , L1 , L2 , NONE }
	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	PreReductionType { NOPRERED , DIETER , LLL , BKZ , FULL }
	A list of all the possible lattice reduction implemented in LatticeTester. More...

Functions
std::int64_t	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\).
double	Harmonic (std::int64_t n)
	Computes the \(n\)-th harmonic number \(H_n = \sum_{j=1}^n 1/j\).
double	Harmonic2 (std::int64_t n)
	Computes the sum.
double	FourierC1 (double x, std::int64_t n)
	Computes and returns the value of the series (see [14])
double	FourierE1 (double x, std::int64_t n)
	Computes and returns the value of the series.
void	negativeCholeski ()
template<typename T>
void	swap9 (T &x, T &y)
	Takes references to two variables of a generic type and swaps their content.
std::ostream &	operator<< (std::ostream &os, const Coordinates &coords)
	Formats the coordinate set coords and outputs it to os.
std::istream &	operator>> (std::istream &is, Coordinates &coords)
	Reads a formatted coordinate set from is.
std::istream &	operator>> (std::istream &is, ProjectionDependentWeights &weights)
	Reads formatted projection-dependent weights into the object `weights`.
std::ostream &	operator<< (std::ostream &os, const Weights &o)
	Identifies the type of weights, formats them and outputs them on `os`.
toString functions
Useful functions for printing the enum constants in this module. Returns the enum constants in this module as strings.
std::string	toStringNorm (NormType)
std::string	toStringPrime (PrimeType)
std::string	toStringCriterion (CriterionType)
std::string	toStringProblem (ProblemType)
std::string	toStringNorma (NormaType)
std::string	toStringCalc (CalcType)
std::string	toStringPreRed (PreReductionType)
std::string	toStringOutput (OutputType)
std::string	toStringPrecision (PrecisionType)
Random numbers
All the functions of this module use LFSR258 as an underlying source for pseudo-random numbers. A free (as in freedom) implementation of this generator can be found at http://simul.iro.umontreal.ca/ as well as the article presenting it. All the functions generating some sort of random number will advance an integer version of LFSR258 by one state and output a transformation of the state to give a double, an int or bits.
double	RandU01 ()
	Returns a random number in \([0, 1)\).
int	RandInt (int i, int j)
	Return a uniform pseudo-random integer in \([i, j]\).
std::uint64_t	RandBits (int s)
	Returns the first s pseudo-random bits of the underlying RNG in the form of a s-bit integer.
void	SetSeed (std::uint64_t seed)
	Sets the seed of the generator.
Mathematical functions
These are complete reimplementation of certain mathematical functions, or wrappers for standard C/C++ functions.
double	mysqrt (double x)
	Returns \(\sqrt{x}\) for \(x\ge0\), and \(-1\) for \(x < 0\).
template<typename T>
double	Lg (const T &x)
	Returns the logarithm of \(x\) in base 2.
double	Lg (std::int64_t x)
	Returns the logarithm of \(x\) in base 2.
template<typename Scal>
Scal	abs (Scal x)
	Returns the absolute value of \(x\).
template<typename T>
std::int64_t	sign (const T &x)
	Returns the sign of x.
template<typename Real>
Real	Round (Real x)
	Returns the value of x rounded to the NEAREST integer value.
std::int64_t	Factorial (int t)
	Calculates \(t!\), the factorial of \(t\) and returns it as an std::int64_t.
Division and modular arithmetic
Remarks Richard: Pour certaines fonctions, les résultats sont mis dans les premiers arguments de la fonction pour être compatible avec NTL; pour d’autres, ils sont mis dans les derniers arguments pour être compatible avec notre ancienne version de LatMRG en Modula-2. Plutôt détestable. Je crois qu’il faudra un jour réarranger les arguments des fonctions pour qu’elles suivent toutes la même convention que NTL. This module offers function to perform division and find remainders in a standard way. These functions are usefull in the case where one wants to do divisions or find remainders of operations with negative operands. The reason is that NTL and primitive types do not use the same logic when doing calculations on negative numbers. Basically, NTL will always floor a division and C++ will always truncate a division (which effectively means the floor function is replaced by a roof function if the answer is a negative number). When calculating the remainder of x/y, both apply the same logic but get a different result because they do not do the same division. In both representations, we have that \[ y\cdot(x/y) + x%y = x. \] It turns out that, with negative values, NTL will return an integer with the same sign as y where C++ will return an integer of opposite sign (but both will return the same number modulo y).
template<typename Int>
void	Quotient (const Int &a, const Int &b, Int &q)
	Computes a/b, truncates the fractionnal part and puts the result in q.
template<typename Real>
void	Modulo (const Real &a, const Real &b, Real &r)
	Computes the remainder of a/b and stores its positive equivalent mod b in 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\).
template<typename Real>
void	DivideRound (const Real &a, const Real &b, Real &q)
	Computes \(a/b\), rounds the result to the nearest integer and returns the result in \(q\).
std::int64_t	gcd (std::int64_t a, std::int64_t b)
	Returns the value of the greatest common divisor of \(a\) and \(b\) by using Stein's binary GCD algorithm.
template<typename Int>
void	Euclide (const Int &A, const Int &B, Int &C, Int &D, Int &E, Int &F, Int &G)
	This method computes the greater common divisor of A and B with Euclid's algorithm.
Vectors
These are utilities to manipulate vectors ranging from instanciation to scalar product.
template<typename Real>
void	CreateVect (Real *&A, int d)
	Allocates memory to A as an array of Real of dimension d and initializes its elements to 0.
template<typename Vect>
void	CreateVect (Vect &A, int d)
	Creates the vector A of dimensions d+1 and initializes its elements to 0.
template<typename Real>
void	DeleteVect (Real *&A)
	Frees the memory used by the vector A.
template<typename Vect>
void	DeleteVect (Vect &A)
	Frees the memory used by the vector A, destroying all the elements it contains.
template<typename Real>
void	SetZero (Real *A, int d)
	Sets the first d of A to 0.
template<typename Vect>
void	SetZero (Vect &A, int d)
	Sets the first d components of A to 0.
template<typename Real>
void	SetValue (Real *A, int d, const Real &x)
	Sets the first d components of A to the value x.
template<typename Vect>
std::string	toString (const Vect &A, int c, int d, const char *sep=" ")
	Returns a string containing A[c] to A[d-1] formated as [A[c]sep...sepA[d-1]].
template<typename Vect>
std::string	toString (const Vect &A, int d)
	Returns a string containing the first d components of the vector A as a string.
template<typename Int, typename Vect1, typename Vect2, typename Scal>
void	ProdScal (const Vect1 &A, const Vect2 &B, int n, Scal &D)
	Computes the scalar product of vectors A and B truncated to their n first components, then puts the result in D.
template<typename IntVec>
void	Invert (const IntVec &A, IntVec &B, int n)
	Takes an input vector A of dimension n+1 and fill the vector B with the values [-A[n] -A[n-1] ... -A[1][1].
template<typename Vect, typename Scal>
void	CalcNorm (const Vect &V, int n, Scal &S, NormType norm)
	Computes the norm norm of vector V trunctated to its n first components, and puts the result in S.
template<typename Vect>
void	CopyVect (Vect &A, const Vect &B, int n)
	Copies the first n components of vector B into vector A.
template<typename Vect1, typename Vect2, typename Scal>
void	ModifVect (Vect1 &A, const Vect2 &B, Scal x, int n)
	Adds the first n components of vector B multiplied by x to first n components of vector A.
template<typename Vect>
void	ChangeSign (Vect &A, int n)
	Changes the sign (multiplies by -1) the first n components of vector A.
std::int64_t	GCD2vect (std::vector< std::int64_t > V, int k, int n)
	Computes the greatest common divisor of V[k],...,V[n-1].
Matrices
template<typename Real>
void	CreateMatr (Real **&A, int d)
	Allocates memory to a square matrix A of dimensions \(d \times d\) and initializes its elements to 0.
template<typename Real>
void	CreateMatr (Real **&A, int line, int col)
	Allocates memory for the matrix A of dimensions \(\text{line} \times \text{col}\) and initializes its elements to 0.
template<typename IntMat>
void	CreateMatr (IntMat &A, int d)
	Resizes the matrix A to a square matrix of dimensions d*d and re-initializes its elements to 0.
template<typename IntMat>
void	CreateMatr (IntMat &A, int line, int col)
	Resizes the matrix A to a matrix of dimensions \(line \times col\) and re-initializes its elements to 0.
template<typename Real>
void	DeleteMatr (Real **&A, int d)
	Frees the memory used by the \(d \times d\) matrix A.
template<typename Real>
void	DeleteMatr (Real **&A, int line, int col)
	Frees the memory used by the matrix A of dimension \(\text{line} \times \text{col}\).
template<typename IntMat>
void	DeleteMatr (IntMat &A)
	Calls the clear() method on A.
template<typename Matr>
void	CopyMatr (Matr &A, const Matr &B, int n)
	Copies the \(n \times n\) submatrix of the first lines and columns of B into matrix A.
template<typename Matr>
void	CopyMatr (Matr &A, const Matr &B, int line, int col)
	Copies the \(\text{line} \times col\) submatrix of the first lines and columns of B into matrix A.
template<typename MatT>
std::string	toStr (const MatT &mat, int d1, int d2)
	Returns a string that is a representation of mat.
template<typename Int>
bool	CheckTriangular (const NTL::matrix< Int > &A, long dim, const Int m)
	Checks that the upper \(\text{dim} \times \text{dim}\) submatrix of A is triangular modulo m.
template<typename Matr, typename Int>
void	Triangularization (Matr &W, Matr &V, int lin, int col, const Int &m)
	Takes a set of generating vectors in the matrix W and iteratively transforms it into an upper triangular lattice basis into the matrix V.
template<typename Matr, typename Int>
void	CalcDual (const Matr &A, Matr &B, int d, const Int &m)
	Takes an upper triangular basis A and computes a dual lattice basis modulo m to this matrix.
Debugging functions
void	MyExit (int status, std::string msg)
	Special exit function.
Printing functions and operators
template<class K, class T, class C, class A>
std::ostream &	operator<< (std::ostream &out, const std::map< K, T, C, A > &x)
	Streaming operator for maps.
template<class T1, class T2>
std::ostream &	operator<< (std::ostream &out, const std::pair< T1, T2 > &x)
	Streaming operator for vectors.
template<class T, class A>
std::ostream &	operator<< (std::ostream &out, const std::vector< T, A > &x)
	Streaming operator for vectors.
template<class K, class C, class A>
std::ostream &	operator<< (std::ostream &out, const std::set< K, C, A > &x)
	Streaming operator for sets.

Variables
const std::array< unsigned int, NB_PRIMES >	PRIMES_ARRAY
template<typename RedDbl>
const double	NormaBestBound< RedDbl >::m_gamma []
template<typename RedDbl>
const double	NormaBestLat< RedDbl >::m_gamma []
template<typename RedDbl>
const double	NormaLaminated< RedDbl >::m_gamma []
	These laminated gamma constants are calculated as defined in Conway and Sloane book (Sphere packing, Lattices and groups) :
template<typename RedDbl>
const double	NormaMinkL1< RedDbl >::m_gamma0 []
template<typename RedDbl>
const double	NormaMinkowski< RedDbl >::m_gamma []
template<typename RedDbl>
const double	NormaRogers< RedDbl >::m_gamma0 []
	This is not all the story, this has to be updated.
template<typename Int, typename BasInt, typename Dbl, typename RedDbl>
bool	Reducer< Int, BasInt, Dbl, RedDbl >::PreRedDieterSV = false
template<typename Int, typename BasInt, typename Dbl, typename RedDbl>
bool	Reducer< Int, BasInt, Dbl, RedDbl >::PreRedLLLSV = false
template<typename Int, typename BasInt, typename Dbl, typename RedDbl>
bool	Reducer< Int, BasInt, Dbl, RedDbl >::PreRedLLLRM = false
template<typename Int, typename BasInt, typename Dbl, typename RedDbl>
bool	Reducer< Int, BasInt, Dbl, RedDbl >::PreRedBKZ = true
template<typename Int, typename BasInt, typename Dbl, typename RedDbl>
std::int64_t	Reducer< Int, BasInt, Dbl, RedDbl >::maxNodesBB = 1000000000
const double	MAX_LONG_DOUBLE = 9007199254740992.0
	Maximum integer that can be represented exactly as a double: \(2^{53}\).
const std::int64_t	TWO_EXP []
	Table of powers of 2: TWO_EXP[ \(i\)] \(= 2^i\), \(i=0, 1, …, 63\).

Detailed Description

Lattice namespace.

Enumeration Type Documentation

◆ CalcType

enum LatticeTester::CalcType

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

PAL is for the \(P_{\alpha}\) test.
BAL is for the bound on the \(P_{\alpha}\) test.
NORMPAL is for the \(P_{\alpha}\) test PAL, with the result normalized over the BAL bound.
SEEKPAL is for the \(P_{\alpha}\) seek, which searches for good values of the multiplier.

◆ CriterionType

enum LatticeTester::CriterionType

Gives the merit criterion for ranking generators or lattices.

LENGTH: Only using the length of the shortest vector as a criterion. BEYER: the figure of merit is the Beyer quotient \(Q_T\).
SPECTRAL: the figure of merit \(S_T\) is based on the spectral test.
PALPHA: the figure of merit is based on \(P_{\alpha}\).
BOUND_JS: the figure of merit is based on the Joe-Sinescu bound [28].

◆ NormaType

enum LatticeTester::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.
BESTLAT: the value used for \(d_t^*\) corresponds to the best bound known to us.
LAMINATED: the value used for \(d_t^*\) corresponds to the best laminated lattice.
ROGERS: the value for \(d_t^*\) is obtained from Rogers’ bound on the density of sphere packing.
MINKOWSKI: the value for \(d_t^*\) is obtained from Minkowski’ theoretical bounds on the length of the shortest nonzero vector in the lattice using the \({\mathcal{L}}_2\) norm.
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 \({\mathcal{L}}_1\) norm.
NONE: no normalization will be used.

◆ NormType

enum LatticeTester::NormType

Indicates which norm is used to measure the length of vectors.

For \(X = (x_1,…,x_t)\),

SUPNORM corresponds to \(\Vert X\Vert= \max(|x_1|,…,|x_t|)\).
L1NORM corresponds to \(\Vert X\Vert= |x_1|+\cdots+|x_t|\).
L2NORM corresponds to \(\Vert X\Vert= (x_1^2+\cdots+x_t^2)^{1/2}\).
ZAREMBANORM corresponds to \(\Vert X\Vert= \max(1, |x_1|)\cdots\max(1, |x_t|)\).

◆ OutputType

enum LatticeTester::OutputType

Indicates in which form and where the results will be sent.

TERM: the results will appear only on the terminal screen.
RES: the results will be in plain text format and sent to a file with extension .res.
TEX: the results will be in LaTeX format and sent to a file with extension .tex.
GEN: the results will be sent to a file with extension .gen.

◆ PreReductionType

enum LatticeTester::PreReductionType

A list of all the possible lattice reduction implemented in LatticeTester.

NORPRERED: no reduction DIETER: Pairwise reduction LLL: LLL reduction BKZ: block Korkine-Zolotarev reduction FULL: shortest vector search.

Function Documentation

◆ BernoulliPoly()

double LatticeTester::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.

◆ CalcDual()

template<typename Matr, typename Int>

void LatticeTester::CalcDual	(	const Matr &	A,
		Matr &	B,
		int	d,
		const Int &	m )

Takes an upper triangular basis A and computes a dual lattice basis modulo m to this matrix.

For this algorithm to work, A as to be upper triangular and all the coefficients on the diagonal have to divide m.

For B to be a m-dual to A, we have to have that \(AB^t = mI\). It is quite easy to show that, knowing A is upper triangular, B will be a lower triangular matrix with A(i,i)*B(i,i) = m for all i and \( A_i \cdot B_j = 0\) for \(i\neq j\). To get the second condition, we simply have to recursively take for each line

\[B_{i,j} = -\frac{1}{A_{j,j}}\sum_{k=j+1}^i A_{j,k} B_{i,k}.\]

References NTL::clear(), and DivideRound().

Referenced by LatticeTester::Rank1Lattice< Int, BasInt, Dbl, RedDbl >::buildBasis().

◆ CalcNorm()

template<typename Vect, typename Scal>

void LatticeTester::CalcNorm	(	const Vect &	V,
		int	n,
		Scal &	S,
		NormType	norm )

inline

Computes the norm norm of vector V trunctated to its n first components, and puts the result in S.

Scal has to be a floating point type.

References abs(), and NTL::conv().

Referenced by LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::updateDualVecNorm(), and LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::updateVecNorm().

◆ CheckTriangular()

template<typename Int>

bool LatticeTester::CheckTriangular	(	const NTL::matrix< Int > &	A,
		long	dim,
		const Int	m )

Checks that the upper \(\text{dim} \times \text{dim}\) submatrix of A is triangular modulo m.

This will return true if all the elements under the diagonal are equal to zero modulo m and false otherwise. If m is 0, this function simply verifies that the matrix is triangular.

Referenced by LatticeTester::BasisConstruction< BasInt >::DualConstruction(), and LatticeTester::BasisConstruction< BasInt >::DualSlow().

◆ CopyMatr() [1/2]

template<typename Matr>

void LatticeTester::CopyMatr	(	Matr &	A,
		const Matr &	B,
		int	line,
		int	col )

inline

Copies the \(\text{line} \times col\) submatrix of the first lines and columns of B into matrix A.

This function does not check for sizes, so A and B both have to be at leat \(line \times col\).

◆ CopyMatr() [2/2]

template<typename Matr>

void LatticeTester::CopyMatr	(	Matr &	A,
		const Matr &	B,
		int	n )

inline

Copies the \(n \times n\) submatrix of the first lines and columns of B into matrix A.

This function does not check for sizes, so A and B both have to be at leat \(n \times n\).

Referenced by LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::copyBasis().

◆ CreateVect() [1/2]

template<typename Real>

void LatticeTester::CreateVect	(	Real *&	A,
		int	d )

inline

Allocates memory to A as an array of Real of dimension d and initializes its elements to 0.

Real has to be a numeric type.

Referenced by LatticeTester::Lacunary< BasInt >::calcIndicesStreams(), LatticeTester::Lacunary< BasInt >::Lacunary(), and LatticeTester::Lacunary< BasInt >::Lacunary().

◆ CreateVect() [2/2]

template<typename Vect>

void LatticeTester::CreateVect	(	Vect &	A,
		int	d )

inline

Creates the vector A of dimensions d+1 and initializes its elements to 0.

The type Vect has to have a resize(integer_type) method that sets the size of the instance to the value of the argument.

◆ DeleteMatr() [1/3]

template<typename IntMat>

void LatticeTester::DeleteMatr ( IntMat & A )

inline

Calls the clear() method on A.

A has to have a clear() method that frees the memory allocated to it.

◆ DeleteMatr() [2/3]

template<typename Real>

void LatticeTester::DeleteMatr	(	Real **&	A,
		int	d )

inline

Frees the memory used by the \(d \times d\) matrix A.

This will not free all the memory allocated to A if A is of greater dimension and it can cause a memory leak.

◆ DeleteMatr() [3/3]

template<typename Real>

void LatticeTester::DeleteMatr	(	Real **&	A,
		int	line,
		int	col )

inline

Frees the memory used by the matrix A of dimension \(\text{line} \times \text{col}\).

This will not free all the memory allocated to A if A is of greater dimension and it can cause a memory leak.

◆ DeleteVect() [1/2]

template<typename Real>

void LatticeTester::DeleteVect ( Real *& A )

inline

Frees the memory used by the vector A.

This calls delete[] on A so trying to access A after using this is unsafe.

Referenced by LatticeTester::Lacunary< BasInt >::calcIndicesStreams(), and LatticeTester::Lacunary< BasInt >::~Lacunary().

◆ DeleteVect() [2/2]

template<typename Vect>

void LatticeTester::DeleteVect ( Vect & A )

inline

Frees the memory used by the vector A, destroying all the elements it contains.

Vect type has to have a clear() method that deallocates all the elements in the vector.

◆ Divide()

template<typename Real>

void LatticeTester::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|\). This works with std::int64_t, NTL::ZZ and real numbers.

\(a\)	\(b\)	\(q\)	\(r\)
\(5\)	3	1	\(2\)
\(-5\)	\(3\)	\(-1\)	\(-2\)
\(5\)	\(-3\)	\(-1\)	\(2\)
\(-5\)	\(-3\)	\(1\)	\(-2\)

References NTL::conv().

◆ DivideRound()

template<typename Real>

void LatticeTester::DivideRound	(	const Real &	a,
		const Real &	b,
		Real &	q )

inline

Computes \(a/b\), rounds the result to the nearest integer and returns the result in \(q\).

This works with std::int64_t, NTL::ZZ and real numbers.

Referenced by CalcDual(), and LatticeTester::BasisConstruction< BasInt >::DualConstruction().

◆ Euclide()

template<typename Int>

void LatticeTester::Euclide	(	const Int &	A,
		const Int &	B,
		Int &	C,
		Int &	D,
		Int &	E,
		Int &	F,
		Int &	G )

This method computes the greater common divisor of A and B with Euclid's algorithm.

This will store this gcd in G and also the linear combination that permits to get G from A and B. This function should work with std::int64_t and NTL::ZZ.

For \(A\) and \(B\) this will assign to \(C\), \(D\), \(E\), \(F\) and \(G\) values such that:

\begin{align*} C a + D b & = G = \mbox{GCD } (a,b)\\ E a + F b & = 0. \end{align*}

References NTL::clear(), NTL::IsZero(), Quotient(), NTL::set(), and swap9().

Referenced by Triangularization().

◆ FourierC1()

double LatticeTester::FourierC1	(	double	x,
		std::int64_t	n )

Computes and returns the value of the series (see [14])

\[S(x, n) = \sum_{j=1}^{n} \frac{\cos(2\pi j x)}{j}. \]

Restrictions: \(n>0\) and \(0 \le x \le 1\).

◆ FourierE1()

double LatticeTester::FourierE1	(	double	x,
		std::int64_t	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\).

◆ Harmonic2()

double LatticeTester::Harmonic2 ( std::int64_t 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.

◆ Invert()

template<typename IntVec>

void LatticeTester::Invert	(	const IntVec &	A,
		IntVec &	B,
		int	n )

inline

Takes an input vector A of dimension n+1 and fill the vector B with the values [-A[n] -A[n-1] ... -A[1][1].

B is assumed to be of dimension at least n+1.

References NTL::conv().

◆ lFactorial()

std::int64_t LatticeTester::lFactorial ( int t )

Calculates \(t!\), the factorial of \(t\).

Might throw if t is too large or if std::int64_t can't contain the factorial asked for.

◆ ModifVect()

template<typename Vect1, typename Vect2, typename Scal>

void LatticeTester::ModifVect	(	Vect1 &	A,
		const Vect2 &	B,
		Scal	x,
		int	n )

inline

Adds the first n components of vector B multiplied by x to first n components of vector A.

This will modify A. This does wierd type convertion and might not work well if different types are used.

References NTL::conv().

◆ Modulo()

template<typename Real>

void LatticeTester::Modulo	(	const Real &	a,
		const Real &	b,
		Real &	r )

inline

Computes the remainder of a/b and stores its positive equivalent mod b in r.

This works with std::int64_t, NTL::ZZ and real valued numbers.

Referenced by Triangularization().

◆ MyExit()

void LatticeTester::MyExit	(	int	status,
		std::string	msg )

Special exit function.

status is the status code to return to the system, msg is the message to print upon exit.

◆ operator<<() [1/4]

template<class K, class T, class C, class A>

std::ostream & LatticeTester::operator<<	(	std::ostream &	out,
		const std::map< K, T, C, A > &	x )

Streaming operator for maps.

Formats a map as: { key1=>val1, ..., keyN=>valN }.

◆ operator<<() [2/4]

template<class T1, class T2>

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

Streaming operator for vectors.

Formats a pair as: (first,second).

◆ operator<<() [3/4]

template<class K, class C, class A>

std::ostream & LatticeTester::operator<<	(	std::ostream &	out,
		const std::set< K, C, A > &	x )

Streaming operator for sets.

Formats a set as: { val1, ..., valN }.

◆ operator<<() [4/4]

template<class T, class A>

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

Streaming operator for vectors.

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

◆ ProdScal()

template<typename Int, typename Vect1, typename Vect2, typename Scal>

void LatticeTester::ProdScal	(	const Vect1 &	A,
		const Vect2 &	B,
		int	n,
		Scal &	D )

inline

Computes the scalar product of vectors A and B truncated to their n first components, then puts the result in D.

There is a lot to consider when passing types to this function. The best is for Vect1 to be the same type as Vect2 and for Scal to be the same as Int, and that those types are the ones stored in Vect1 and Vect2.

WARNING: This uses so many types without check about them and also assumes all those types can be converted to each other without problem. This is used in many places to compute a floating point norm of vectors with integers values. Take care when using this function.

References NTL::conv().

Referenced by LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::checkDuality(), LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::updateDualScalL2Norm(), LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::updateDualVecNorm(), LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::updateScalL2Norm(), and LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::updateVecNorm().

◆ Quotient()

template<typename Int>

void LatticeTester::Quotient	(	const Int &	a,
		const Int &	b,
		Int &	q )

inline

Computes a/b, truncates the fractionnal part and puts the result in q.

This function is overloaded to work as specified on NTL::ZZ integers. Example:

\(a\)	\(b\)	\(q\)
\(5\)	3	1
\(-5\)	\(3\)	\(-1\)
\(5\)	\(-3\)	\(-1\)
\(-5\)	\(-3\)	\(1\)

Referenced by Euclide(), and Triangularization().

◆ RandBits()

std::uint64_t LatticeTester::RandBits ( int s )

Returns the first s pseudo-random bits of the underlying RNG in the form of a s-bit integer.

It is imperative that \(1 \leq s \leq 64\) because the RNG is 64 bits wide.

◆ RandInt()

int LatticeTester::RandInt	(	int	i,
		int	j )

Return a uniform pseudo-random integer in \([i, j]\).

Note that the numbers \(i\) and \(j\) are part of the possible output. It is important that \(i < j\) because the underlying arithmetic uses unsigned integers to store j-i+1 and that will be undefined behavior.

◆ RandU01()

double LatticeTester::RandU01 ( )

Returns a random number in \([0, 1)\).

The number will have 53 pseudo-random bits.

◆ Round()

template<typename Real>

Real LatticeTester::Round ( Real x )

inline

Returns the value of x rounded to the NEAREST integer value.

(This does not truncate the integer value as is usual in computer arithmetic.)

◆ SetSeed()

void LatticeTester::SetSeed ( std::uint64_t seed )

Sets the seed of the generator.

Because of the constraints on the state, seed has to be \( > 2\). If this is never called, a default seed will be used.

◆ sign()

template<typename T>

std::int64_t LatticeTester::sign ( const T & x )

inline

Returns the sign of x.

The sign is 1 if x>0, 0 if x==0 and -1 if x<0.

Referenced by LatticeTester::ParamReader< Int, BasInt, RedDbl >::readNumber3().

◆ swap9()

template<typename T>

void LatticeTester::swap9	(	T &	x,
		T &	y )

inline

Takes references to two variables of a generic type and swaps their content.

This uses the assignment operator, so it might not always work well if this operator's implementation is not thorough.

Referenced by Euclide(), LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::permute(), and LatticeTester::IntLatticeBasis< Int, BasInt, Dbl, RedDbl >::permuteNoDual().

◆ toStr()

template<typename MatT>

std::string LatticeTester::toStr	(	const MatT &	mat,
		int	d1,
		int	d2 )

Returns a string that is a representation of mat.

This string will represent the \(d1 \times d2\) submatrix of the first lines and colums of mat.

◆ toString() [1/2]

template<typename Vect>

std::string LatticeTester::toString	(	const Vect &	A,
		int	c,
		int	d,
		const char *	sep = " " )

Returns a string containing A[c] to A[d-1] formated as [A[c]sep...sepA[d-1]].

In this string, components are separated by string sep. By default, sep is just a whitespace character.

Referenced by toString(), and LatticeTester::Rank1Lattice< Int, BasInt, Dbl, RedDbl >::toStringCoef().

◆ toString() [2/2]

template<typename Vect>

std::string LatticeTester::toString	(	const Vect &	A,
		int	d )

Returns a string containing the first d components of the vector A as a string.

Calls toString(const Vect&, int, int, const char*).

References toString().

◆ Triangularization()

template<typename Matr, typename Int>

void LatticeTester::Triangularization	(	Matr &	W,
		Matr &	V,
		int	lin,
		int	col,
		const Int &	m )

Takes a set of generating vectors in the matrix W and iteratively transforms it into an upper triangular lattice basis into the matrix V.

W and V have to have more lines than lin and more columns than col since this algorithm will only operate on the upper lin*col matrix of W. All the computations will be done modulo m, which means that you must know a rescalling factor for the vector system to call this function. After the execution, W will be a matrix containing irrelevant information and V will contain an upper triangular basis.

For more details please look at [5]. This algorithm basically implements what is written at the end of the article, that is the matrix W contains the set of vectors that is used and modified at each step to get a new vector from the basis.

References NTL::clear(), Euclide(), NTL::IsZero(), Modulo(), and Quotient().

Referenced by LatticeTester::Rank1Lattice< Int, BasInt, Dbl, RedDbl >::buildBasis().

Variable Documentation

◆ NormaLaminated< RedDbl >::m_gamma

template<typename RedDbl>

const double LatticeTester::NormaLaminated< RedDbl >::m_gamma[]

These laminated gamma constants are calculated as defined in Conway and Sloane book (Sphere packing, Lattices and groups) :

equation (47) page 20 of chapter 1
table 6.1 page 158 of chapter 6

◆ NormaRogers< RedDbl >::m_gamma0

template<typename RedDbl>

const double LatticeTester::NormaRogers< RedDbl >::m_gamma0[]

This is not all the story, this has to be updated.

These Rogers gamma constants are calculated as defined in Conway and Sloane book (Sphere packing, Lattices and groups) :

equation (47) page 20 of chapter 1
table 1.2 page 15 of chapter 1

Namespaces

Classes

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ CalcType

◆ CriterionType

◆ NormaType

◆ NormType

◆ OutputType

◆ PreReductionType

Function Documentation

◆ BernoulliPoly()

◆ CalcDual()

◆ CalcNorm()

◆ CheckTriangular()

◆ CopyMatr() [1/2]

◆ CopyMatr() [2/2]

◆ CreateVect() [1/2]

◆ CreateVect() [2/2]

◆ DeleteMatr() [1/3]

◆ DeleteMatr() [2/3]

◆ DeleteMatr() [3/3]

◆ DeleteVect() [1/2]

◆ DeleteVect() [2/2]

◆ Divide()

◆ DivideRound()

◆ Euclide()

◆ FourierC1()

◆ FourierE1()

◆ Harmonic2()

◆ Invert()

◆ lFactorial()

◆ ModifVect()

◆ Modulo()

◆ MyExit()

◆ operator<<() [1/4]

◆ operator<<() [2/4]

◆ operator<<() [3/4]

◆ operator<<() [4/4]

◆ ProdScal()

◆ Quotient()

◆ RandBits()

◆ RandInt()

◆ RandU01()

◆ Round()

◆ SetSeed()

◆ sign()

◆ swap9()

◆ toStr()

◆ toString() [1/2]

◆ toString() [2/2]

◆ Triangularization()

Variable Documentation

◆ NormaLaminated< RedDbl >::m_gamma

◆ NormaRogers< RedDbl >::m_gamma0