Util.h File Reference

#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <type_traits>
#include "NTL/tools.h"
#include "NTL/ZZ.h"
#include "NTL/RR.h"
#include "latticetester/EnumTypes.h"
#include "latticetester/NTLWrap.h"

Namespaces
namespace	LatticeTester
	Lattice namespace.

Macros
#define	SEPAR   "===============================================================\n"

Functions
template<typename T >
void	LatticeTester::swap9 (T &x, T &y)
	Takes references to two variables of a generic type and swaps their content.
template<typename Matr1 , typename Matr2 >
void	LatticeTester::copyMatrixToMat (Matr1 &A, Matr2 &B)
template<typename IntMat >
void	LatticeTester::printBase (IntMat bas_mat)
template<typename IntMat >
void	LatticeTester::printBase2 (IntMat bas_mat)
template<typename IntMat >
void	LatticeTester::copy (IntMat &b1, IntMat &b2)
template<typename IntMat >
void	LatticeTester::copy (IntMat &b1, IntMat &b2, int64_t r, int64_t c)
int64_t	LatticeTester::getWidth (clock_t time[], int64_t dim, std::string message, clock_t totals[], int64_t ind)
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 int64_t or bits.
double	LatticeTester::RandU01 ()
	Returns a random number in \([0, 1)\).
int64_t	LatticeTester::RandInt (int64_t i, int64_t j)
	Return a uniform pseudo-random integer in \([i, j]\).
std::uint64_t	LatticeTester::RandBits (int64_t s)
	Returns the first s pseudo-random bits of the underlying RNG in the form of a s-bit integer.
void	LatticeTester::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	LatticeTester::mysqrt (double x)
	Returns \(\sqrt{x}\) for \(x\ge0\), and \(-1\) for \(x < 0\).
template<typename T >
double	LatticeTester::Lg (const T &x)
	Returns the logarithm of \(x\) in base 2.
double	LatticeTester::Lg (std::int64_t x)
	Returns the logarithm of \(x\) in base 2.
template<typename Scal >
Scal	LatticeTester::abs (Scal x)
	Returns the absolute value of \(x\).
template<typename T >
std::int64_t	LatticeTester::sign (const T &x)
	Returns the sign of x.
template<typename Real >
Real	LatticeTester::Round (Real x)
	Returns the value of x rounded to the NEAREST integer value.
std::int64_t	LatticeTester::Factorial (int64_t 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	LatticeTester::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	LatticeTester::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	LatticeTester::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	LatticeTester::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	LatticeTester::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	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.
template<typename Int >
void	LatticeTester::Euclide (const Int &A, const Int &B, Int &C, Int &D, Int &G)
template<typename IntMat >
void	LatticeTester::TransposeMatrix (IntMat &mat, IntMat &mat2)
	Takes a set of generating vectors in the matrix mat and iteratively transforms it into an upper triangular lattice basis into the matrix mat2.
Vectors
These are utilities to manipulate vectors ranging from instantiation to scalar product.
template<typename Real >
void	LatticeTester::CreateVect (Real *&A, int64_t d)
	Allocates memory to A as an array of Real of dimension d and initializes its elements to 0.
template<typename Vect >
void	LatticeTester::CreateVect (Vect &A, int64_t d)
	Creates the vector A of dimensions d+1 and initializes its elements to 0.
template<typename Real >
void	LatticeTester::DeleteVect (Real *&A)
	Frees the memory used by the vector A.
template<typename Vect >
void	LatticeTester::DeleteVect (Vect &A)
	Frees the memory used by the vector A, destroying all the elements it contains.
template<typename Real >
void	LatticeTester::SetZero (Real *A, int64_t d)
	Sets the first d of A to 0.
template<typename Vect >
void	LatticeTester::SetZero (Vect &A, int64_t d)
	Sets the first d components of A to 0.
template<typename Real >
void	LatticeTester::SetValue (Real *A, int64_t d, const Real &x)
	Sets the first d components of A to 0.
template<typename Vect >
std::string	LatticeTester::toString (const Vect &A, int64_t c, int64_t 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	LatticeTester::toString (const Vect &A, int64_t 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	LatticeTester::ProdScal (const Vect1 &A, const Vect2 &B, int64_t 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	LatticeTester::Invert (const IntVec &A, IntVec &B, int64_t 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	LatticeTester::CalcNorm (const Vect &V, int64_t 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	LatticeTester::CopyPartVec (Vect &toVec, const Vect &fromVec, int64_t c)
	Copies the first c components of vector fromVec into vector toVec.
template<typename Matr >
void	LatticeTester::CopyPartMat (Matr &toMat, const Matr &fromMat, int64_t r, int64_t c)
	Copies the first r rows and c columns of matrix fromMat into matrix toMat.
template<typename Vect >
void	LatticeTester::CopyVect (Vect &A, const Vect &B, int64_t n)
	Copies the first n components of vector B into vector A.
template<typename Vect1 , typename Vect2 , typename Scal >
void	LatticeTester::ModifVect (Vect1 &A, const Vect2 &B, Scal x, int64_t n)
	Adds the first n components of vector B multiplied by x to first n components of vector A.
template<typename Vect >
void	LatticeTester::ChangeSign (Vect &A, int64_t n)
	Changes the sign (multiplies by -1) the first n components of vector A.
std::int64_t	LatticeTester::GCD2vect (std::vector< std::int64_t > V, int64_t k, int64_t n)
	Computes the greatest common divisor of V[k],...,V[n-1].
Matrices
template<typename Real >
void	LatticeTester::CreateMatr (Real **&A, int64_t d)
	Allocates memory to a square matrix A of dimensions \(d \times d\) and initializes its elements to 0.
template<typename Real >
void	LatticeTester::CreateMatr (Real **&A, int64_t line, int64_t col)
	Allocates memory for the matrix A of dimensions \(\text{line} \times \text{col}\) and initializes its elements to 0.
template<typename IntMat >
void	LatticeTester::CreateMatr (IntMat &A, int64_t d)
	Resizes the matrix A to a square matrix of dimensions d*d and re-initializes its elements to 0.
template<typename IntMat >
void	LatticeTester::CreateMatr (IntMat &A, int64_t line, int64_t col)
	Resizes the matrix A to a matrix of dimensions \(line \times col\) and re-initializes its elements to 0.
template<typename Real >
void	LatticeTester::DeleteMatr (Real **&A, int64_t d)
	Frees the memory used by the \(d \times d\) matrix A.
template<typename Real >
void	LatticeTester::DeleteMatr (Real **&A, int64_t line, int64_t col)
	Frees the memory used by the matrix A of dimension \(\text{line} \times \text{col}\).
template<typename IntMat >
void	LatticeTester::DeleteMatr (IntMat &A)
	Calls the clear() method on A.
template<typename Matr >
void	LatticeTester::CopyMatr (Matr &A, const Matr &B, int64_t n)
	Copies the \(n \times n\) submatrix of the first lines and columns of B into matrix A.
template<typename Matr >
void	LatticeTester::CopyMatr (Matr &A, const Matr &B, int64_t line, int64_t col)
	Copies the \(\text{line} \times col\) submatrix of the first lines and columns of B into matrix A.
template<typename MatT >
std::string	LatticeTester::toStr (const MatT &mat, int64_t d1, int64_t d2, int64_t prec=2)
	Returns a string that is a representation of mat.
template<typename Int >
void	LatticeTester::ProductDiagonal (const NTL::matrix< Int > &A, long dim, Int &prod)
	Returns the product of the diagonal elements of the matrix A, which is assumed to be square dim x dim.
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.
template<typename Int >
bool	LatticeTester::checkInverseModm (const NTL::matrix< Int > &A, const NTL::matrix< Int > &B, const Int m)
	Checks if A and B are m-dual to each other.
template<typename Matr , typename Int >
void	LatticeTester::Triangularization (Matr &W, Matr &V, int64_t lin, int64_t 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	LatticeTester::calcDual (const Matr &A, Matr &B, int64_t d, const Int &m)
	Takes a basis A and computes an m-dual lattice basis B.
Debugging functions
void	LatticeTester::MyExit (int64_t status, std::string msg)
	Special exit function.
Printing functions and operators
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.
template<class T1 , class T2 >
std::ostream &	LatticeTester::operator<< (std::ostream &out, const std::pair< T1, T2 > &x)
	Streaming operator for vectors.
template<class T , class A >
std::ostream &	LatticeTester::operator<< (std::ostream &out, const std::vector< T, A > &x)
	Streaming operator for vectors.
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.

Variables
const double	LatticeTester::MAX_LONG_DOUBLE = 9007199254740992.0
	Maximum integer that can be represented exactly as a double: \(2^{53}\).
const std::int64_t	LatticeTester::TWO_EXP []
	Table of powers of 2: TWO_EXP[ \(i\)] \(= 2^i\), \(i=0, 1, …, 63\).

Macro Definition Documentation

SEPAR

#define SEPAR   "===============================================================\n"