Util.h File Reference

This module describes various useful functions as well as functions interfacing with NTL. More...

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

Namespaces
	NTL
	The two floowing two classes are copies from NTL::Vec<T> and NTL::Mat<T>, but they contain additional member functions having same names to the ones used in boost library.
	LatticeTester
	Lattice namespace.

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

Functions
template<typename T >
void	LatticeTester::swap9 (T &x, T &y)
	Swaps the values of x and y.
template<class K , class T , class C , class A >
std::ostream &	LatticeTester::operator<< (std::ostream &out, const std::map< K, T, C, A > &x)
	}.
template<class T1 , class T2 >
std::ostream &	LatticeTester::operator<< (std::ostream &out, const std::pair< T1, T2 > &x)
	Streaming operator for vectors. More...
template<class T , class A >
std::ostream &	LatticeTester::operator<< (std::ostream &out, const std::vector< T, A > &x)
	Streaming operator for vectors. More...
template<class K , class C , class A >
std::ostream &	LatticeTester::operator<< (std::ostream &out, const std::set< K, C, A > &x)
	}.
Some other compatibility utilities
void	NTL::conv (std::int64_t &l, const char *c)
	Converts the array of characters (string) c into an std::int64_t l.
void	NTL::conv (double &r, const char *c)
	Converts the array of characters (string) c into a double r.
void	NTL::conv (double &x, long long a)
void	NTL::conv (long long &x, double a)
void	NTL::conv (ZZ &x, long long a)
void	NTL::conv (long long &x, ZZ a)
void	NTL::conv (long &x, long long a)
void	NTL::conv (long long &x, long a)
void	NTL::conv (long long &x, long long a)
Random numbers
double	LatticeTester::RandU01 ()
	Returns a random number in \([0, 1)\). More...
int	LatticeTester::RandInt (int i, int j)
	Return a random integer in \([i, j]\). More...
std::uint64_t	LatticeTester::RandBits (int s)
	Returns random blocks of \(s\) bits ( \(s\)-bit integers).
void	LatticeTester::SetSeed (std::uint64_t seed)
	Sets the seed of the generator. More...
std::int64_t	LatticeTester::IsOdd (const std::int64_t &x)
	Returns 1 if \(x\) is odd, and 0 otherwise.
bool	LatticeTester::IsZero (const std::int64_t &x)
	Return true if \(x = 0\).
void	LatticeTester::clear (double &x)
	Sets \(x\) to 0.
void	LatticeTester::clear (std::int64_t &x)
	Sets \(x\) to 0.
void	LatticeTester::set9 (std::int64_t &x)
	Sets \(x\) to 1.
void	LatticeTester::set9 (NTL::ZZ &x)
	Sets \(x\) to 1.
Mathematical functions
std::int64_t	LatticeTester::power (std::int64_t p, std::int64_t i)
	Returns \(p^i\).
void	LatticeTester::power2 (std::int64_t &z, std::int64_t i)
	Sets \(z = 2^i\).
void	LatticeTester::power2 (NTL::ZZ &z, std::int64_t i)
	Sets \(z = 2^i\).
double	LatticeTester::mysqrt (double x)
	Returns \(\sqrt{x}\) for \(x\ge0\), and \(-1\) for \(x < 0\).
double	LatticeTester::SqrRoot (double x)
	Returns \(\sqrt{x}\). More...
template<typename T >
double	LatticeTester::Lg (const T &x)
	Logarithm of \(x\) in base 2.
double	LatticeTester::Lg (std::int64_t x)
	Logarithm of \(x\) in base 2.
template<typename Scal >
Scal	LatticeTester::abs (Scal x)
	Returns the absolute value.
template<typename T >
std::int64_t	LatticeTester::sign (const T &x)
	Returns 1, 0 or \(-1\) depending on whether \(x> 0\), \(x= 0\) or \(x< 0\) respectively.
template<typename Real >
Real	LatticeTester::Round (Real x)
	Rounds to the nearest integer value.
std::int64_t	LatticeTester::Factorial (int t)
	Calculates \(t!\), the factorial of \(t\).
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 std::int64_t. The negative quotient differs by 1 and the remainder also differs. Thus the following small inline functions for division and remainder. 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.
template<typename Int >
void	LatticeTester::Quotient (const Int &a, const Int &b, Int &q)
	Computes \(q = a/b\) by dropping the fractionnal part, i.e. More...
void	LatticeTester::Quotient (const NTL::ZZ &a, const NTL::ZZ &b, NTL::ZZ &q)
	Computes \(q = a/b\) by dropping the fractionnal part, i.e. More...
template<typename Real >
void	LatticeTester::Modulo (const Real &a, const Real &b, Real &r)
void	LatticeTester::Modulo (const std::int64_t &a, const std::int64_t &b, std::int64_t &r)
	Computes the "positive" remainder \(r = a \bmod b\), i.e. More...
void	LatticeTester::Modulo (const NTL::ZZ &a, const NTL::ZZ &b, NTL::ZZ &r)
	Computes the "positive" remainder \(r = a \bmod b\), i.e. More...
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\). More...
void	LatticeTester::Divide (std::int64_t &q, std::int64_t &r, const std::int64_t &a, const std::int64_t &b)
	Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\) by truncating \(q\) towards 0. More...
void	LatticeTester::Divide (NTL::ZZ &q, NTL::ZZ &r, const NTL::ZZ &a, const NTL::ZZ &b)
	Computes the quotient \(q = a/b\) and remainder \(r = a \bmod b\) by truncating \(q\) towards 0. More...
void	LatticeTester::div (std::int64_t &a, const std::int64_t &b, const std::int64_t &d)
	Integer division: \(a = b/d\).
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\).
void	LatticeTester::DivideRound (const std::int64_t &a, const std::int64_t &b, std::int64_t &q)
	Computes \(a/b\), rounds the result to the nearest integer and returns the result in \(q\).
void	LatticeTester::DivideRound (const NTL::ZZ &a, const NTL::ZZ &b, NTL::ZZ &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\). More...
template<typename Int >
void	LatticeTester::Euclide (const Int &A, const Int &B, Int &C, Int &D, Int &E, Int &F, Int &G)
	For given \(a\) and \(b\), returns the values \(C\), \(D\), \(E\), \(F\) and \(G\) such that: \begin{align*} C a + D b & = G = \mbox{GCD } (a,b) \\ E a + F b & = 0. \end{align*} .
Vectors
template<typename Real >
void	LatticeTester::CreateVect (Real *&A, int d)
	Allocates memory for the vector \(A\) of dimensions \(d\) 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::CreateVect (Vect &A, int d)
	Creates the vector \(A\) of dimensions \(d+1\) and initializes its elements to 0.
template<typename Vect >
void	LatticeTester::DeleteVect (Vect &A)
	Frees the memory used by the vector \(A\).
template<typename Real >
void	LatticeTester::SetZero (Real *A, int d)
	Sets components \([0..d-1]\) of \(A\) to 0.
template<typename Vect >
void	LatticeTester::SetZero (Vect &A, int d)
	Sets components \([0..d-1]\) of \(A\) to 0.
template<typename Real >
void	LatticeTester::SetValue (Real *A, int d, const Real &x)
	Sets all components \([0..d]\) of \(A\) to the value \(x\).
template<typename Vect >
std::string	LatticeTester::toString (const Vect &A, int c, int d, const char *sep)
	Prints components \([c..d-1]\) of vector \(A\) as a string. More...
template<typename Vect >
std::string	LatticeTester::toString (const Vect &A, int c, int d)
	Prints components \([c..d]\) of vector \(A\) as a string.
template<typename Vect >
std::string	LatticeTester::toString (const Vect &A, int d)
	Prints components \([0..d-1]\) of vector \(A\) as a string.
template<typename Int , typename Vect1 , typename Vect2 , typename Scal >
void	LatticeTester::ProdScal (const Vect1 &A, const Vect2 &B, int n, Scal &D)
	Computes the scalar product of vectors \(A\) and \(B\), using components \([0..n-1]\), and puts the result in \(D\). More...
template<typename IntVec >
void	LatticeTester::Invert (const IntVec &A, IntVec &B, int n)
	Transforms the polynomial \(A_0 + A_1x^1 + \cdots+ A_nx^n\) into \(x^n - A_1x^{n-1} - \cdots- A_n\). More...
template<typename Vect , typename Scal >
void	LatticeTester::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\).
template<typename Vect >
void	LatticeTester::CopyVect (Vect &A, const Vect &B, int n)
	Copies vector \(B\) into vector \(A\) using components \([0..n-1]\).
template<typename Vect1 , typename Vect2 , typename Scal >
void	LatticeTester::ModifVect (Vect1 &A, const Vect2 &B, Scal x, int n)
	Adds vector \(B\) multiplied by \(x\) to vector \(A\) using components \([0..n-1]\), and puts the result in \(A\).
template<typename Vect >
void	LatticeTester::ChangeSign (Vect &A, int n)
	Changes the sign of the components \([0..n-1]\) of vector \(A\).
std::int64_t	LatticeTester::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	LatticeTester::CreateMatr (Real **&A, int d)
	Allocates memory for the square matrix \(A\) of dimensions \((d+1)\times(d+1)\). More...
template<typename Real >
void	LatticeTester::DeleteMatr (Real **&A, int d)
	Frees the memory used by the \(d\times d\) matrix \(A\).
template<typename Real >
void	LatticeTester::CreateMatr (Real **&A, int line, int col)
	Allocates memory for the matrix \(A\) of dimensions (line) \(\times\) (col). More...
template<typename Real >
void	LatticeTester::DeleteMatr (Real **&A, int line, int col)
	Frees the memory used by the matrix \(A\).
template<typename IntMat >
void	LatticeTester::CreateMatr (IntMat &A, int d)
	Creates the square matrix \(A\) of dimensions \(d\times d\) and initializes its elements to 0.
template<typename IntMat >
void	LatticeTester::CreateMatr (IntMat &A, int line, int col)
	Creates the matrix \(A\) of dimensions (line) \(\times\) (col). More...
template<typename IntMat >
void	LatticeTester::DeleteMatr (IntMat &A)
	Deletes the matrix \(A\).
template<typename Matr >
void	LatticeTester::CopyMatr (Matr &A, const Matr &B, int n)
	As above. More...
template<typename Matr >
void	LatticeTester::CopyMatr (Matr &A, const Matr &B, int line, int col)
	As above.
template<typename MatT >
std::string	LatticeTester::toStr (const MatT &mat, int d1, int d2)
	Transforms mat into a string. More...
template<typename Matr , typename Int >
bool	LatticeTester::CheckTriangular (const Matr &A, int dim, const Int &m)
	Checks that square matrix \(A\) is upper triangular (modulo \(m\)) for dimensions 1 to dim.
template<typename Matr , typename Int >
void	LatticeTester::Triangularization (Matr &W, Matr &V, int lin, int col, const Int &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 , typename Int >
void	LatticeTester::CalcDual (const Matr &A, Matr &B, int d, const Int &m)
	Calculates the \(m\)-dual of the matrix A. More...
Debugging functions
void	LatticeTester::MyExit (int status, std::string msg)
	Special exit function. More...

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

Detailed Description

This module describes various useful functions as well as functions interfacing with NTL.