Underlying mathematical gruntwork. More...

Classes
class	regina::Cyclotomic
	Represents an element of a cyclotomic field. More...

struct	regina::InfinityBase< supportInfinity >
	Internal base classes for use with IntegerBase, templated on whether we should support infinity as an allowed value. More...

class	regina::IntegerBase< bool >
	Represents an arbitrary precision integer. More...

class	regina::NativeInteger< bytes >
	A wrapper class for a native, fixed-precision integer type of the given size. More...

class	regina::Laurent< T >
	Represents a single-variable Laurent polynomial with coefficients of type T. More...

class	regina::Laurent2< T >
	Represents a Laurent polynomial in the two variables x, y with coefficients of type T. More...

class	regina::Matrix< typename, bool >
	Represents a matrix of elements of the given type T. More...

class	regina::Matrix2
	Represents a 2-by-2 integer matrix. More...

class	regina::Perm< n >
	Represents a permutation of {0,1,...,n-1}. More...

class	regina::PermClass< n >
	Represents a conjugacy class of permutations on n elements. More...

class	regina::PermGroup< n, cached >
	Represents a group of permutations on n elements. More...

class	regina::Polynomial< T >
	Represents a single-variable polynomial with coefficients of type T. More...

class	regina::Primes
	A helper class for finding primes and factorising integers. More...

class	regina::Rational
	Represents an arbitrary precision rational number. More...

class	regina::Perm< 2 >
	Represents a permutation of {0,1}. More...

class	regina::Perm< 3 >
	Represents a permutation of {0,1,2}. More...

class	regina::Perm< 4 >
	Represents a permutation of {0,1,2,3}. More...

class	regina::Perm< 5 >
	Represents a permutation of {0,1,2,3,4}. More...

class	regina::Perm< 6 >
	Represents a permutation of {0,1,2,3,4,5}. More...

class	regina::Perm< 7 >
	Represents a permutation of {0,1,2,3,4,5,6}. More...

class	regina::Vector< T >
	An optimised vector class of elements from a given ring T. More...

Macros
#define	mpz_cmp_si_cpp(z, si)
	An internal copy of the GMP signed comparison optimisations.

Typedefs
using	regina::LargeInteger = IntegerBase<true>
	LargeInteger is a type alias for IntegerBase<true>, which offers arbitrary precision integers with support for infinity.

using	regina::Integer = IntegerBase<false>
	Integer is a type alias for IntegerBase<false>, which offers arbitrary precision integers without support for infinity.

using	regina::NativeLong = NativeInteger<sizeof(long)>
	NativeLong is a type alias for the NativeInteger template class whose underlying integer type is a native long.

using	regina::MatrixInt = Matrix<Integer, true>
	A matrix of arbitrary-precision integers.

using	regina::MatrixBool = Matrix<bool>
	A matrix of booleans.

using	regina::VectorInt = Vector<Integer>
	A vector of arbitrary-precision integers.

using	regina::VectorLarge = Vector<LargeInteger>
	A vector of arbitrary-precision integers that allows infinite elements.

Enumerations
enum	regina::PermCodeType { regina::PERM_CODE_IMAGES = 1 , regina::PERM_CODE_INDEX = 2 }
	Represents the different kinds of internal permutation codes that are used in Regina's various Perm<n> template classes. More...

Functions
constexpr int	regina::binomSmall (int n, int k)
	Returns the binomial coefficient n choose k in constant time for small arguments (n ≤ 16).

constexpr long	regina::binomMedium (int n, int k)
	Returns the binomial coefficient n choose k in linear time for medium-sized arguments (n ≤ 29).

void	regina::swap (Cyclotomic &a, Cyclotomic &b) noexcept
	Swaps the contents of the given field elements.

Cyclotomic	regina::operator* (Cyclotomic elt, const Rational &scalar)
	Multiplies the given field element by the given rational.

Cyclotomic	regina::operator* (const Rational &scalar, Cyclotomic elt)
	Multiplies the given field element by the given rational.

Cyclotomic	regina::operator/ (Cyclotomic elt, const Rational &scalar)
	Divides the given field element by the given rational.

Cyclotomic	regina::operator+ (const Cyclotomic &lhs, const Cyclotomic &rhs)
	Adds the two given cyclotomic field elements.

Cyclotomic	regina::operator+ (Cyclotomic &&lhs, const Cyclotomic &rhs)
	Adds the two given cyclotomic field elements.

Cyclotomic	regina::operator+ (const Cyclotomic &lhs, Cyclotomic &&rhs)
	Adds the two given cyclotomic field elements.

Cyclotomic	regina::operator+ (Cyclotomic &&lhs, Cyclotomic &&rhs)
	Adds the two given cyclotomic field elements.

Cyclotomic	regina::operator- (Cyclotomic arg)
	Returns the negative of the given field element.

Cyclotomic	regina::operator- (const Cyclotomic &lhs, const Cyclotomic &rhs)
	Subtracts the two given cyclotomic field elements.

Cyclotomic	regina::operator- (Cyclotomic &&lhs, const Cyclotomic &rhs)
	Subtracts the two given cyclotomic field elements.

Cyclotomic	regina::operator- (const Cyclotomic &lhs, Cyclotomic &&rhs)
	Subtracts the two given cyclotomic field elements.

Cyclotomic	regina::operator- (Cyclotomic &&lhs, Cyclotomic &&rhs)
	Subtracts the two given cyclotomic field elements.

Cyclotomic	regina::operator* (const Cyclotomic &lhs, const Cyclotomic &rhs)
	Multiplies the two given cyclotomic field elements.

Cyclotomic	regina::operator/ (const Cyclotomic &lhs, const Cyclotomic &rhs)
	Divides the two given cyclotomic field elements.

template<bool supportInfinity>
void	regina::swap (IntegerBase< supportInfinity > &a, IntegerBase< supportInfinity > &b) noexcept
	Swaps the contents of the given integers.

template<bool supportInfinity>
std::ostream &	regina::operator<< (std::ostream &out, const IntegerBase< supportInfinity > &i)
	Writes the given integer to the given output stream.

template<bool supportInfinity>
IntegerBase< supportInfinity >	regina::operator+ (long lhs, const IntegerBase< supportInfinity > &rhs)
	Adds the given native integer to the given large integer.

template<bool supportInfinity>
IntegerBase< supportInfinity >	regina::operator* (long lhs, const IntegerBase< supportInfinity > &rhs)
	Multiplies the given native integer with the given large integer.

template<bool supportInfinity>
void	regina::tightEncode (std::ostream &out, IntegerBase< supportInfinity > value)
	Writes the tight encoding of the given arbitrary precision integer to the given output stream.

template<bool supportInfinity>
std::string	regina::tightEncoding (IntegerBase< supportInfinity > value)
	Returns the tight encoding of the given arbitrary precision integer.

template<int bytes>
void	regina::swap (NativeInteger< bytes > &a, NativeInteger< bytes > &b) noexcept
	Swaps the contents of the given integers.

template<int bytes>
std::ostream &	regina::operator<< (std::ostream &out, const NativeInteger< bytes > &i)
	Writes the given integer to the given output stream.

template<typename T >
void	regina::swap (Laurent< T > &a, Laurent< T > &b) noexcept
	Swaps the contents of the given polynomials.

template<typename T >
Laurent< T >	regina::operator* (Laurent< T > poly, const typename Laurent< T >::Coefficient &scalar)
	Multiplies the given polynomial by the given scalar constant.

template<typename T >
Laurent< T >	regina::operator* (const typename Laurent< T >::Coefficient &scalar, Laurent< T > poly)
	Multiplies the given polynomial by the given scalar constant.

template<typename T >
Laurent< T >	regina::operator/ (Laurent< T > poly, const typename Laurent< T >::Coefficient &scalar)
	Divides the given polynomial by the given scalar constant.

template<typename T >
Laurent< T >	regina::operator+ (const Laurent< T > &lhs, const Laurent< T > &rhs)
	Adds the two given polynomials.

template<typename T >
Laurent< T >	regina::operator+ (Laurent< T > &&lhs, const Laurent< T > &rhs)
	Adds the two given polynomials.

template<typename T >
Laurent< T >	regina::operator+ (const Laurent< T > &lhs, Laurent< T > &&rhs)
	Adds the two given polynomials.

template<typename T >
Laurent< T >	regina::operator+ (Laurent< T > &&lhs, Laurent< T > &&rhs)
	Adds the two given polynomials.

template<typename T >
Laurent< T >	regina::operator- (Laurent< T > arg)
	Returns the negative of the given polynomial.

template<typename T >
Laurent< T >	regina::operator- (const Laurent< T > &lhs, const Laurent< T > &rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent< T >	regina::operator- (Laurent< T > &&lhs, const Laurent< T > &rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent< T >	regina::operator- (const Laurent< T > &lhs, Laurent< T > &&rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent< T >	regina::operator- (Laurent< T > &&lhs, Laurent< T > &&rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent< T >	regina::operator* (const Laurent< T > &lhs, const Laurent< T > &rhs)
	Multiplies the two given polynomials.

template<typename T >
void	regina::swap (Laurent2< T > &a, Laurent2< T > &b) noexcept
	Swaps the contents of the given polynomials.

template<typename T >
Laurent2< T >	regina::operator* (Laurent2< T > poly, const typename Laurent2< T >::Coefficient &scalar)
	Multiplies the given polynomial by the given scalar constant.

template<typename T >
Laurent2< T >	regina::operator* (const typename Laurent2< T >::Coefficient &scalar, Laurent2< T > poly)
	Multiplies the given polynomial by the given scalar constant.

template<typename T >
Laurent2< T >	regina::operator/ (Laurent2< T > poly, const typename Laurent2< T >::Coefficient &scalar)
	Divides the given polynomial by the given scalar constant.

template<typename T >
Laurent2< T >	regina::operator+ (const Laurent2< T > &lhs, const Laurent2< T > &rhs)
	Adds the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator+ (Laurent2< T > &&lhs, const Laurent2< T > &rhs)
	Adds the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator+ (const Laurent2< T > &lhs, Laurent2< T > &&rhs)
	Adds the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator+ (Laurent2< T > &&lhs, Laurent2< T > &&rhs)
	Adds the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator- (Laurent2< T > arg)
	Returns the negative of the given polynomial.

template<typename T >
Laurent2< T >	regina::operator- (const Laurent2< T > &lhs, const Laurent2< T > &rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator- (Laurent2< T > &&lhs, const Laurent2< T > &rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator- (const Laurent2< T > &lhs, Laurent2< T > &&rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator- (Laurent2< T > &&lhs, Laurent2< T > &&rhs)
	Subtracts the two given polynomials.

template<typename T >
Laurent2< T >	regina::operator* (const Laurent2< T > &lhs, const Laurent2< T > &rhs)
	Multiplies the two given polynomials.

template<typename T >
void	regina::swap (Matrix< T > &a, Matrix< T > &b) noexcept
	Swaps the contents of the given matrices.

void	regina::swap (Matrix2 &a, Matrix2 &b) noexcept
	Swaps the contents of the two given matrices.

std::ostream &	regina::operator<< (std::ostream &out, const Matrix2 &mat)
	Writes the given matrix to the given output stream.

bool	regina::simpler (const Matrix2 &m1, const Matrix2 &m2)
	Determines whether the first given matrix is more aesthetically pleasing than the second.

bool	regina::simpler (const Matrix2 &pair1first, const Matrix2 &pair1second, const Matrix2 &pair2first, const Matrix2 &pair2second)
	Determines whether the first given pair of matrices is more aesthetically pleasing than the second pair.

void	regina::smithNormalForm (MatrixInt &matrix)
	Transforms the given integer matrix into Smith normal form.

void	regina::smithNormalForm (MatrixInt &matrix, MatrixInt &rowSpaceBasis, MatrixInt &rowSpaceBasisInv, MatrixInt &colSpaceBasis, MatrixInt &colSpaceBasisInv)
	A Smith normal form algorithm that also returns change of basis matrices.

void	regina::metricalSmithNormalForm (MatrixInt &matrix, MatrixInt &rowSpaceBasis, MatrixInt &rowSpaceBasisInv, MatrixInt &colSpaceBasis, MatrixInt &colSpaceBasisInv)
	An alternative Smith normal form algorithm that also returns change of basis matrices.

size_t	regina::rowBasis (MatrixInt &matrix)
	Find a basis for the row space of the given matrix.

size_t	regina::rowBasisAndOrthComp (MatrixInt &input, MatrixInt &complement)
	Finds a basis for the row space of the given matrix, as well as an "incremental" basis for its orthogonal complement.

void	regina::columnEchelonForm (MatrixInt &M, MatrixInt &R, MatrixInt &Ri, const std::vector< size_t > &rowList)
	Transforms a given matrix into column echelon form with respect to a collection of rows.

MatrixInt	regina::preImageOfLattice (const MatrixInt &hom, const std::vector< Integer > &sublattice)
	Given a homomorphism from Z^n to Z^k and a sublattice of Z^k, compute the preimage of this sublattice under this homomorphism.

MatrixInt	regina::torsionAutInverse (const MatrixInt &input, const std::vector< Integer > &invF)
	Given an automorphism of an abelian group, this procedure computes the inverse automorphism.

long	regina::reducedMod (long k, long modBase)
	Reduces k modulo modBase to give the smallest possible absolute value.

long	regina::gcd (long a, long b)
	Deprecated routine that calculates the greatest common divisor of two signed integers.

std::tuple< long, long, long >	regina::gcdWithCoeffs (long a, long b)
	Calculates the greatest common divisor of two given integers and finds the smallest coefficients with which these integers combine to give their gcd.

long	regina::lcm (long a, long b)
	Deprecated routine that calculates the lowest common multiple of two signed integers.

unsigned long	regina::modularInverse (unsigned long n, unsigned long k)
	Calculates the multiplicative inverse of one integer modulo another.

constexpr char	regina::digit (int i)
	Returns the character used to express the integer i in a permutation.

constexpr int64_t	regina::factorial (int n)
	Returns the factorial of n.

template<int n>
std::ostream &	regina::operator<< (std::ostream &out, const Perm< n > &p)
	Writes a string representation of the given permutation to the given output stream.

template<int n>
std::ostream &	regina::operator<< (std::ostream &out, const PermClass< n > &c)
	Writes a string representation of the given conjugacy class of permutations to the given output stream.

template<typename T >
void	regina::swap (Polynomial< T > &a, Polynomial< T > &b) noexcept
	Swaps the contents of the given polynomials.

template<typename T >
Polynomial< T >	regina::operator* (Polynomial< T > poly, const typename Polynomial< T >::Coefficient &scalar)
	Multiplies the given polynomial by the given scalar constant.

template<typename T >
Polynomial< T >	regina::operator* (const typename Polynomial< T >::Coefficient &scalar, Polynomial< T > poly)
	Multiplies the given polynomial by the given scalar constant.

template<typename T >
Polynomial< T >	regina::operator/ (Polynomial< T > poly, const typename Polynomial< T >::Coefficient &scalar)
	Divides the given polynomial by the given scalar constant.

template<typename T >
Polynomial< T >	regina::operator+ (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
	Adds the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator+ (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
	Adds the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator+ (const Polynomial< T > &lhs, Polynomial< T > &&rhs)
	Adds the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator+ (Polynomial< T > &&lhs, Polynomial< T > &&rhs)
	Adds the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator- (Polynomial< T > arg)
	Returns the negative of the given polynomial.

template<typename T >
Polynomial< T >	regina::operator- (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
	Subtracts the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator- (Polynomial< T > &&lhs, const Polynomial< T > &rhs)
	Subtracts the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator- (const Polynomial< T > &lhs, Polynomial< T > &&rhs)
	Subtracts the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator- (Polynomial< T > &&lhs, Polynomial< T > &&rhs)
	Subtracts the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator* (const Polynomial< T > &lhs, const Polynomial< T > &rhs)
	Multiplies the two given polynomials.

template<typename T >
Polynomial< T >	regina::operator/ (Polynomial< T > lhs, const Polynomial< T > &rhs)
	Divides the two given polynomials.

void	regina::swap (Rational &a, Rational &b) noexcept
	Swaps the contents of the given rationals.

std::ostream &	regina::operator<< (std::ostream &out, const Rational &rat)
	Writes the given rational to the given output stream.

template<typename T >
void	regina::swap (Vector< T > &a, Vector< T > &b) noexcept
	Swaps the contents of the given vectors.

template<class T >
std::ostream &	regina::operator<< (std::ostream &out, const Vector< T > &vector)
	Writes the given vector to the given output stream.

Variables
constexpr int	regina::detail::binomSmall_ [17][17]
	A lookup table that stores (n choose k) for all n ≤ 16.

Detailed Description

Underlying mathematical gruntwork.

Macro Definition Documentation

◆ mpz_cmp_si_cpp

#define mpz_cmp_si_cpp	(		z,
			si )

An internal copy of the GMP signed comparison optimisations.

This macro should not be used outside this class.

By making our own copy of such optimisation macros we can use C++-style casts instead of C-style casts and avoid noisy compiler warnings. I'd love a better way of doing this.

Typedef Documentation

◆ Integer

using regina::Integer = IntegerBase<false>

Integer is a type alias for IntegerBase<false>, which offers arbitrary precision integers without support for infinity.

◆ LargeInteger

using regina::LargeInteger = IntegerBase<true>

LargeInteger is a type alias for IntegerBase<true>, which offers arbitrary precision integers with support for infinity.

◆ MatrixBool

using regina::MatrixBool = Matrix<bool>

A matrix of booleans.

This is used in a handful of places in Regina to represent incidence or adjacency matrices.

Python: This instance of the Matrix template class is made available to Python.

◆ MatrixInt

typedef Matrix< Integer, true > regina::MatrixInt = Matrix<Integer, true>

A matrix of arbitrary-precision integers.

This is the most common class used by Regina when running algebraic algorithms over integer matrices. Since the underlying type is Regina's Integer class, calculations will be exact regardless of how large the integers become.

Python: This instance of the Matrix template class is made available to Python.

◆ NativeLong

using regina::NativeLong = NativeInteger<sizeof(long)>

NativeLong is a type alias for the NativeInteger template class whose underlying integer type is a native long.

Python: Not present. The NativeInteger classes are not available to Python users.

◆ VectorInt

using regina::VectorInt = Vector<Integer>

A vector of arbitrary-precision integers.

This is the underlying vector class that Regina uses to store angle structures.

Python: This instance of the Vector template class is made available to Python.

◆ VectorLarge

using regina::VectorLarge = Vector<LargeInteger>

A vector of arbitrary-precision integers that allows infinite elements.

This is the underlying vector class that Regina uses to store normal surfaces and hypersurfaces.

Python: This instance of the Vector template class is made available to Python.

Enumeration Type Documentation

◆ PermCodeType

enum regina::PermCodeType

Represents the different kinds of internal permutation codes that are used in Regina's various Perm<n> template classes.

See the Perm<n> class notes for more information on exactly how these codes are constructed. The class constant Perm<n>::codeType indicates which type of code is used for which n.

Enumerator

PERM_CODE_IMAGES

This is a permutation code that packs the images of 0,...,n-1 into a single native integer using a handful of bits per image.

Such codes are easier to manipulate on an element-by-element basis.

Codes of this type can always be queried using Perm<n>::permCode(), and permutations can be recreated from them using Perm<n>::fromPermCode().

PERM_CODE_INDEX

This is a permutation code that stores the index into the full permutation group S_n.

Such codes typically require fewer bytes and are packed together, making them ideal for working with lookup tables.

Codes of this type can be queried using Perm<n>::SnIndex(), and permutations can be recreated from them by indexing into Perm<n>::Sn.

Warning: The routines Perm<n>::permCode() and Perm<n>::fromPermCode() will still be present, but in some classes (e.g., Perm<4> and Perm<5>), these are legacy routines that refer to different types of codes.

Function Documentation

◆ binomMedium()

long regina::binomMedium	(	int	n,
		int	k )

inlineconstexpr

Returns the binomial coefficient n choose k in linear time for medium-sized arguments (n ≤ 29).

This routine computes the binomial coefficient using the standard formula. It works entirely with native long integers; the constraint n ≤ 29 is designed to avoid overflow (since all intermediate results are guaranteed to stay below 2^31).

If n ≤ 16 then this routine will use the same constant-time lookup as binomSmall() (i.e., there is no penalty for calling this routine with very small arguments).

Parameters

n	the parameter n in (n choose k); this must be between 0 and 29 inclusive.
k	the parameter k in (n choose k); this must be between 0 and n inclusive.

Returns: the binomial coefficient n choose k.

◆ binomSmall()

int regina::binomSmall	(	int	n,
		int	k )

inlineconstexpr

Returns the binomial coefficient n choose k in constant time for small arguments (n ≤ 16).

This routine is very fast, since it uses a constant-time lookup. The trade-off is that it can only be used for n ≤ 16.

Note: The constraint n ≤ 16 is large enough for working with triangulations in Regina, since Regina restricts its triangulations to dimension ≤ 15 (where each simplex has 16 vertices).

Parameters

n	the parameter n in (n choose k); this must be between 0 and 16 inclusive.
k	the parameter k in (n choose k); this must be between 0 and n inclusive.

Returns: the binomial coefficient n choose k.

◆ columnEchelonForm()

void regina::columnEchelonForm	(	MatrixInt &	M,
		MatrixInt &	R,
		MatrixInt &	Ri,
		const std::vector< size_t > &	rowList )

Transforms a given matrix into column echelon form with respect to a collection of rows.

The transformation will perform only column operations.

Given the matrix M and the list rowList of rows from M, this algorithm puts M in column echelon form with respect to the rows in rowList. The only purpose of rowList is to clarify and/or weaken precisely what is meant by "column echelon form"; all rows of M are affected by the resulting column operations that take place.

This routine also returns the corresponding change of coordinate matrices R and Ri:

If R and Ri are passed as identity matrices, the returned matrices will be such that original_M * R = final_M and final_M * Ri = original_M (and of course final_M is in column echelon form with respect to the given row list).
If R and Ri are already non-trivial coordinate transformations, they are modified appropriately by the algorithm.

Our convention is that a matrix is in column echelon form if:

each column is either zero or there is a first non-zero entry which is positive (but see the note regarding rowList below);
moving from the leftmost column to the rightmost column, the rows containing the first non-zero entries for these columns have strictly increasing indices in rowList;
given a first non-zero column entry, in that row all the elements to the left are smaller and non-negative (all elements to the right are already zero by the previous condition);
all the zero columns are on the right hand side of the matrix.

By a "zero column" here we simply mean "zero for every row in \a rowList". Likewise, by "first non-zero entry" we mean "first row in \a rowList with a non-zero entry".

In a pinch, you can also use this routine to compute the inverse of an invertible square matrix.

If you just wish to reduce the matrix, you do not care about the order of rows, and you do not want the change-of-basis matrices, then you should call MatrixInt::columnEchelonForm() instead, which is simpler but also more streamlined.

Precondition: Both R and Ri are square matrices with side length M.columns(), and these matrices are inverses of each other.

Parameters

M	the matrix to reduce.
R	used to return the row-reduction matrix, as described above.
Ri	used to return the inverse of R.
rowList	the rows to pay attention to. This list must contain distinct integers, all between 0 and M.rows()-1 inclusive. The integers may appear in any order (though changing the order will change the resulting column echelon form). For a "classical" column echelon form, this would be the list of all rows: 0,...,(M.rows()-1).

Author: Ryan Budney

◆ digit()

char regina::digit ( int i )

inlineconstexpr

Returns the character used to express the integer i in a permutation.

For i = 0,...,9, this will be the usual digit representing i.
For i ≥ 10, this will be a lower-case letter. In particular, for i = 10,...,15, this will be the usual hexadecimal digit representing i.
At present, this routine only supports integers i < 36.

Parameters

i	the integer to represent; this must be between 0 and 35 inclusive.

Returns: the single character used to represent i.

◆ factorial()

int64_t regina::factorial ( int n )

inlineconstexpr

Returns the factorial of n.

Parameters

n	any non-negative integer; this must be at most 20 (since otherwise the factorial will overflow).

Returns: the factorial of n..

◆ gcd()

long regina::gcd	(	long	a,
		long	b )

Deprecated routine that calculates the greatest common divisor of two signed integers.

This routine is not recursive.

Although the arguments may be negative, the result is guaranteed to be non-negative. As a special case, gcd(0,0) is considered to be zero.

Deprecated: Simply use std::gcd(), which was introduced with C++17.

Parameters

a	one of the two integers to work with.
b	the other integer with which to work.

Returns: the greatest common divisor of a and b.

◆ gcdWithCoeffs()

std::tuple< long, long, long > regina::gcdWithCoeffs	(	long	a,
		long	b )

Calculates the greatest common divisor of two given integers and finds the smallest coefficients with which these integers combine to give their gcd.

This routine is not recursive.

Note that the given integers need not be non-negative. However, the gcd returned is guaranteed to be non-negative. As a special case, gcd(0,0) is considered to be zero.

If d is the gcd of a and b, then this routine returns the tuple (d, u, v), where u and v are coefficients for which:

u⋅a + v⋅b = d;
-abs(a)/d < v⋅sign(b) ≤ 0; and
1 ≤ u⋅sign(a) ≤ abs(b)/d.

In the special case where one of the given integers is zero, the corresponding coefficient will also be zero and the other coefficient will be 1 or -1 so that u⋅a + v⋅b = d still holds. If both given integers are zero, both of the coefficients will be set to zero.

Parameters

a	the first integer to compute the gcd of.
b	the second integer to compute the gcd of.

Returns: a tuple containing: the greatest common divisor of a and b; the final coefficient of a; and the final coefficient of b.

◆ lcm()

long regina::lcm	(	long	a,
		long	b )

Deprecated routine that calculates the lowest common multiple of two signed integers.

Although the arguments may be negative, the result is guaranteed to be non-negative.

If either of the arguments is zero, the return value will also be zero.

Regarding possible overflow: This routine does not create any temporary integers that are larger than the final LCM.

Deprecated: Simply use std::lcm(), which was introduced with C++17.

Parameters

a	one of the two integers to work with.
b	the other integer with which to work.

Returns: the lowest common multiple of a and b.

◆ metricalSmithNormalForm()

void regina::metricalSmithNormalForm	(	MatrixInt &	matrix,
		MatrixInt &	rowSpaceBasis,
		MatrixInt &	rowSpaceBasisInv,
		MatrixInt &	colSpaceBasis,
		MatrixInt &	colSpaceBasisInv )

An alternative Smith normal form algorithm that also returns change of basis matrices.

This routine may be preferable for extremely large matrices. This is a variant of Hafner-McCurley and Havas-Holt-Rees's description of pivoting methods.

The only input argument is matrix. The four remaining arguments (the change of basis matrices) will be refilled. All five arguments are used to return information as follows.

Let M be the initial value of matrix, and let S be the Smith normal form of M. After this routine exits:

The argument matrix will contain the Smith normal form S;
colSpaceBasis * M * rowSpaceBasis = S;
colSpaceBasisInv * S * rowSpaceBasisInv = M;
colSpaceBasis * colSpaceBasisInv and rowSpaceBasis * rowSpaceBasisInv are both identity matrices.

Thus, one obtains the Smith normal form the original matrix by multiplying on the left by ColSpaceBasis and on the right by RowSpaceBasis.

The matrices rowSpaceBasis and rowSpaceBasisInv that are passed may be of any size, or they may even be uninitialised; upon return they will both be square with side length matrix.columns(). Likewise, the matrices colSpaceBasis and colSpaceBasisInv that are passed may be of any size or may be uninitialised; upon return they will both be square with side length matrix.rows().

Parameters

matrix	the original matrix to put into Smith Normal Form (this need not be square). When the algorithm terminates, this matrix is in its Smith Normal Form.
rowSpaceBasis	used to return a change of basis matrix (see above for details).
rowSpaceBasisInv	used to return the inverse of rowSpaceBasis.
colSpaceBasis	used to return a change of basis matrix (see above for details).
colSpaceBasisInv	used to return the inverse of colSpaceBasis.

Author: Ryan Budney

◆ modularInverse()

unsigned long regina::modularInverse	(	unsigned long	n,
		unsigned long	k )

Calculates the multiplicative inverse of one integer modulo another.

The inverse returned will be between 0 and n-1 inclusive.

Precondition: n and k are both strictly positive;; n and k have no common factors.

Parameters

n	the modular base in which to work.
k	the number whose multiplicative inverse should be found.

Returns: the inverse v for which k * v == 1 (mod n).

◆ operator*() [1/13]

Cyclotomic regina::operator*	(	const Cyclotomic &	lhs,
		const Cyclotomic &	rhs )

Multiplies the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the first field element to multiply.
rhs	the second field element to multiply.

Returns: the product of both field elements.

◆ operator*() [2/13]

template<typename T >

Laurent2< T > regina::operator*	(	const Laurent2< T > &	lhs,
		const Laurent2< T > &	rhs )

inline

Multiplies the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the first polynomial to multiply.
rhs	the second polynomial to multiply.

Returns: the product of both polynomials.

◆ operator*() [3/13]

template<typename T >

Laurent< T > regina::operator*	(	const Laurent< T > &	lhs,
		const Laurent< T > &	rhs )

Multiplies the two given polynomials.

Parameters

lhs	the first polynomial to multiply.
rhs	the second polynomial to multiply.

Returns: the product of both polynomials.

◆ operator*() [4/13]

template<typename T >

Polynomial< T > regina::operator*	(	const Polynomial< T > &	lhs,
		const Polynomial< T > &	rhs )

Multiplies the two given polynomials.

Parameters

lhs	the first polynomial to multiply.
rhs	the second polynomial to multiply.

Returns: the product of both polynomials.

◆ operator*() [5/13]

Cyclotomic regina::operator*	(	const Rational &	scalar,
		Cyclotomic	elt )

inline

Multiplies the given field element by the given rational.

Parameters

scalar	the rational to multiply by.
elt	the field element to multiply by.

Returns: the product of the given field element and rational.

◆ operator*() [6/13]

template<typename T >

Laurent2< T > regina::operator*	(	const typename Laurent2< T >::Coefficient &	scalar,
		Laurent2< T >	poly )

inline

Multiplies the given polynomial by the given scalar constant.

The scalar is simply of type T; we use the identical type Laurent2<T>::Coefficient here to assist with C++ template type matching.

Parameters

scalar	the scalar to multiply by.
poly	the polynomial to multiply by.

Returns: the product of the given polynomial and scalar.

◆ operator*() [7/13]

template<typename T >

Laurent< T > regina::operator*	(	const typename Laurent< T >::Coefficient &	scalar,
		Laurent< T >	poly )

inline

Multiplies the given polynomial by the given scalar constant.

The scalar is simply of type T; we use the identical type Laurent<T>::Coefficient here to assist with C++ template type matching.

Parameters

scalar	the scalar to multiply by.
poly	the polynomial to multiply by.

Returns: the product of the given polynomial and scalar.

◆ operator*() [8/13]

template<typename T >

Polynomial< T > regina::operator*	(	const typename Polynomial< T >::Coefficient &	scalar,
		Polynomial< T >	poly )

inline

Multiplies the given polynomial by the given scalar constant.

The scalar is simply of type T; we use the identical type Polynomial<T>::Coefficient here to assist with C++ template type matching.

Parameters

scalar	the scalar to multiply by.
poly	the polynomial to multiply by.

Returns: the product of the given polynomial and scalar.

◆ operator*() [9/13]

Cyclotomic regina::operator*	(	Cyclotomic	elt,
		const Rational &	scalar )

inline

Multiplies the given field element by the given rational.

Parameters

elt	the field element to multiply by.
scalar	the rational to multiply by.

Returns: the product of the given field element and rational.

◆ operator*() [10/13]

template<typename T >

Laurent2< T > regina::operator*	(	Laurent2< T >	poly,
		const typename Laurent2< T >::Coefficient &	scalar )

inline

Multiplies the given polynomial by the given scalar constant.

The scalar is simply of type T; we use the identical type Laurent2<T>::Coefficient here to assist with C++ template type matching.

Parameters

poly	the polynomial to multiply by.
scalar	the scalar to multiply by.

Returns: the product of the given polynomial and scalar.

◆ operator*() [11/13]

template<typename T >

Laurent< T > regina::operator*	(	Laurent< T >	poly,
		const typename Laurent< T >::Coefficient &	scalar )

inline

Multiplies the given polynomial by the given scalar constant.

The scalar is simply of type T; we use the identical type Laurent<T>::Coefficient here to assist with C++ template type matching.

Parameters

poly	the polynomial to multiply by.
scalar	the scalar to multiply by.

Returns: the product of the given polynomial and scalar.

◆ operator*() [12/13]

template<bool supportInfinity>

IntegerBase< supportInfinity > regina::operator*	(	long	lhs,
		const IntegerBase< supportInfinity > &	rhs )

inline

Multiplies the given native integer with the given large integer.

If the large integer is infinite, the result will also be infinity.

Parameters

lhs	the native integer to multiply.
rhs	the large integer to multiply.

Returns: the product lhs times rhs.

◆ operator*() [13/13]

template<typename T >

Polynomial< T > regina::operator*	(	Polynomial< T >	poly,
		const typename Polynomial< T >::Coefficient &	scalar )

inline

Multiplies the given polynomial by the given scalar constant.

The scalar is simply of type T; we use the identical type Polynomial<T>::Coefficient here to assist with C++ template type matching.

Parameters

poly	the polynomial to multiply by.
scalar	the scalar to multiply by.

Returns: the product of the given polynomial and scalar.

◆ operator+() [1/17]

Cyclotomic regina::operator+	(	const Cyclotomic &	lhs,
		const Cyclotomic &	rhs )

inline

Adds the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the first field element to add.
rhs	the second field element to add.

Returns: the sum of both field elements.

◆ operator+() [2/17]

Cyclotomic regina::operator+	(	const Cyclotomic &	lhs,
		Cyclotomic &&	rhs )

inline

Adds the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the first field element to add.
rhs	the second field element to add.

Returns: the sum of both field elements.

◆ operator+() [3/17]

template<typename T >

Laurent2< T > regina::operator+	(	const Laurent2< T > &	lhs,
		const Laurent2< T > &	rhs )

inline

Adds the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [4/17]

template<typename T >

Laurent2< T > regina::operator+	(	const Laurent2< T > &	lhs,
		Laurent2< T > &&	rhs )

inline

Adds the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [5/17]

template<typename T >

Laurent< T > regina::operator+	(	const Laurent< T > &	lhs,
		const Laurent< T > &	rhs )

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [6/17]

template<typename T >

Laurent< T > regina::operator+	(	const Laurent< T > &	lhs,
		Laurent< T > &&	rhs )

inline

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [7/17]

template<typename T >

Polynomial< T > regina::operator+	(	const Polynomial< T > &	lhs,
		const Polynomial< T > &	rhs )

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [8/17]

template<typename T >

Polynomial< T > regina::operator+	(	const Polynomial< T > &	lhs,
		Polynomial< T > &&	rhs )

inline

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [9/17]

Cyclotomic regina::operator+	(	Cyclotomic &&	lhs,
		const Cyclotomic &	rhs )

inline

Adds the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the first field element to add.
rhs	the second field element to add.

Returns: the sum of both field elements.

◆ operator+() [10/17]

Cyclotomic regina::operator+	(	Cyclotomic &&	lhs,
		Cyclotomic &&	rhs )

inline

Adds the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the first field element to add.
rhs	the second field element to add.

Returns: the sum of both field elements.

◆ operator+() [11/17]

template<typename T >

Laurent2< T > regina::operator+	(	Laurent2< T > &&	lhs,
		const Laurent2< T > &	rhs )

inline

Adds the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [12/17]

template<typename T >

Laurent2< T > regina::operator+	(	Laurent2< T > &&	lhs,
		Laurent2< T > &&	rhs )

inline

Adds the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [13/17]

template<typename T >

Laurent< T > regina::operator+	(	Laurent< T > &&	lhs,
		const Laurent< T > &	rhs )

inline

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [14/17]

template<typename T >

Laurent< T > regina::operator+	(	Laurent< T > &&	lhs,
		Laurent< T > &&	rhs )

inline

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [15/17]

template<bool supportInfinity>

IntegerBase< supportInfinity > regina::operator+	(	long	lhs,
		const IntegerBase< supportInfinity > &	rhs )

inline

Adds the given native integer to the given large integer.

If the large integer is infinite, the result will also be infinity.

Parameters

lhs	the native integer to add.
rhs	the large integer to add.

Returns: the sum lhs plus rhs.

◆ operator+() [16/17]

template<typename T >

Polynomial< T > regina::operator+	(	Polynomial< T > &&	lhs,
		const Polynomial< T > &	rhs )

inline

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator+() [17/17]

template<typename T >

Polynomial< T > regina::operator+	(	Polynomial< T > &&	lhs,
		Polynomial< T > &&	rhs )

inline

Adds the two given polynomials.

This operator + is sometimes faster than using +=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the first polynomial to add.
rhs	the second polynomial to add.

Returns: the sum of both polynomials.

◆ operator-() [1/20]

Cyclotomic regina::operator-	(	const Cyclotomic &	lhs,
		const Cyclotomic &	rhs )

inline

Subtracts the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the field element to subtract from.
rhs	the field element to subtract.

Returns: the first field element minus the second.

◆ operator-() [2/20]

Cyclotomic regina::operator-	(	const Cyclotomic &	lhs,
		Cyclotomic &&	rhs )

inline

Subtracts the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the field element to subtract from.
rhs	the field element to subtract.

Returns: the first field element minus the second.

◆ operator-() [3/20]

template<typename T >

Laurent2< T > regina::operator-	(	const Laurent2< T > &	lhs,
		const Laurent2< T > &	rhs )

inline

Subtracts the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the polynomial to subtract from.
rhs	the polynomial to subtract.

Returns: the first polynomial minus the second.

◆ operator-() [4/20]

template<typename T >

Laurent2< T > regina::operator-	(	const Laurent2< T > &	lhs,
		Laurent2< T > &&	rhs )

inline

Subtracts the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the polynomial to subtract from.
rhs	the polynomial to subtract.

Returns: the first polynomial minus the second.

◆ operator-() [5/20]

template<typename T >

Laurent< T > regina::operator-	(	const Laurent< T > &	lhs,
		const Laurent< T > &	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [6/20]

template<typename T >

Laurent< T > regina::operator-	(	const Laurent< T > &	lhs,
		Laurent< T > &&	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [7/20]

template<typename T >

Polynomial< T > regina::operator-	(	const Polynomial< T > &	lhs,
		const Polynomial< T > &	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [8/20]

template<typename T >

Polynomial< T > regina::operator-	(	const Polynomial< T > &	lhs,
		Polynomial< T > &&	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [9/20]

Cyclotomic regina::operator-	(	Cyclotomic &&	lhs,
		const Cyclotomic &	rhs )

inline

Subtracts the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the field element to subtract from.
rhs	the field element to subtract.

Returns: the first field element minus the second.

◆ operator-() [10/20]

Cyclotomic regina::operator-	(	Cyclotomic &&	lhs,
		Cyclotomic &&	rhs )

inline

Subtracts the two given cyclotomic field elements.

Precondition: Both arguments belong to the same cyclotomic field.

Parameters

lhs	the field element to subtract from.
rhs	the field element to subtract.

Returns: the first field element minus the second.

◆ operator-() [11/20]

Cyclotomic regina::operator- ( Cyclotomic arg )

inline

Returns the negative of the given field element.

Parameters

arg	the field element to negate.

Returns: the negative of arg.

◆ operator-() [12/20]

template<typename T >

Laurent2< T > regina::operator-	(	Laurent2< T > &&	lhs,
		const Laurent2< T > &	rhs )

inline

Subtracts the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the polynomial to subtract from.
rhs	the polynomial to subtract.

Returns: the first polynomial minus the second.

◆ operator-() [13/20]

template<typename T >

Laurent2< T > regina::operator-	(	Laurent2< T > &&	lhs,
		Laurent2< T > &&	rhs )

inline

Subtracts the two given polynomials.

The two polynomials need not have the same range of non-zero coefficients.

Parameters

lhs	the polynomial to subtract from.
rhs	the polynomial to subtract.

Returns: the first polynomial minus the second.

◆ operator-() [14/20]

template<typename T >

Laurent2< T > regina::operator- ( Laurent2< T > arg )

inline

Returns the negative of the given polynomial.

Parameters

arg	the polynomial to negate.

Returns: the negative of arg.

◆ operator-() [15/20]

template<typename T >

Laurent< T > regina::operator-	(	Laurent< T > &&	lhs,
		const Laurent< T > &	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [16/20]

template<typename T >

Laurent< T > regina::operator-	(	Laurent< T > &&	lhs,
		Laurent< T > &&	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [17/20]

template<typename T >

Laurent< T > regina::operator- ( Laurent< T > arg )

inline

Returns the negative of the given polynomial.

Parameters

arg	the polynomial to negate.

Returns: the negative of arg.

◆ operator-() [18/20]

template<typename T >

Polynomial< T > regina::operator-	(	Polynomial< T > &&	lhs,
		const Polynomial< T > &	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [19/20]

template<typename T >

Polynomial< T > regina::operator-	(	Polynomial< T > &&	lhs,
		Polynomial< T > &&	rhs )

Subtracts the two given polynomials.

This operator - is sometimes faster than using -=, since it has more flexibility to avoid an internal deep copy.

Parameters

lhs	the polynomial to sutract rhs from.
rhs	the polynomial to subtract from lhs.

Returns: the difference of the two given polynomials.

◆ operator-() [20/20]

template<typename T >

Polynomial< T > regina::operator- ( Polynomial< T > arg )

inline

Returns the negative of the given polynomial.

Parameters

arg	the polynomial to negate.

Returns: the negative of arg.

◆ operator/() [1/6]

Cyclotomic regina::operator/	(	const Cyclotomic &	lhs,
		const Cyclotomic &	rhs )

inline

Divides the two given cyclotomic field elements.

Precondition: The second argument rhs is non-zero.; Both arguments belong to the same cyclotomic field.

Parameters

lhs	the field element to divide by rhs.
rhs	the field element to divide lhs by.

Returns: the result of dividing lhs by rhs.

◆ operator/() [2/6]

Cyclotomic regina::operator/	(	Cyclotomic	elt,
		const Rational &	scalar )

inline

Divides the given field element by the given rational.

Precondition: The argument scalar is non-zero.

Parameters

elt	the field element to divide by the given rational.
scalar	the rational to divide by.

Returns: the quotient of the given field element by the given rational.

◆ operator/() [3/6]

template<typename T >

Laurent2< T > regina::operator/	(	Laurent2< T >	poly,
		const typename Laurent2< T >::Coefficient &	scalar )

inline

Divides the given polynomial by the given scalar constant.

This uses the division operator /= for the coefficient type T.

The scalar is simply of type T; we use the identical type Laurent2<T>::Coefficient here to assist with C++ template type matching.

Precondition: The argument scalar is non-zero.

Parameters

poly	the polynomial to divide by the given scalar.
scalar	the scalar factor to divide by.

Returns: the quotient of the given polynomial by the given scalar.

◆ operator/() [4/6]

template<typename T >

Laurent< T > regina::operator/	(	Laurent< T >	poly,
		const typename Laurent< T >::Coefficient &	scalar )

inline

Divides the given polynomial by the given scalar constant.

This uses the division operator /= for the coefficient type T.

The scalar is simply of type T; we use the identical type Laurent<T>::Coefficient here to assist with C++ template type matching.

Precondition: The argument scalar is non-zero.

Parameters

poly	the polynomial to divide by the given scalar.
scalar	the scalar factor to divide by.

Returns: the quotient of the given polynomial by the given scalar.

◆ operator/() [5/6]

template<typename T >

Polynomial< T > regina::operator/	(	Polynomial< T >	lhs,
		const Polynomial< T > &	rhs )

inline

Divides the two given polynomials.

More precisely: suppose there exist polynomials q and r with coefficients of type T for which lhs = q.rhs + r, and where r has smaller degree than rhs. Then we call q the quotient, and r the remainder.

This routine returns the quotient q, and discards the remainder. If you need to keep the remainder also, then call Polynomial::divisionAlg() instead.

Coefficients are divided using the operator /= on type T.

If your coefficient type T is not a field (e.g., if T is Integer), you must be sure to know in advance that the quotient exists (see the precondition below). Otherwise the behaviour of this routine is undefined.

Precondition: The second polynomial rhs is non-zero.; The quotient as defined above exists. If T is a field type (e.g., if T is Rational) then this is true automatically. If not (e.g., if T is Integer) then this requires some prior knowledge about the arguments.

Parameters

lhs	the polynomial to divide by rhs.
rhs	the polynomial that we will divide lhs by.

Returns: the quotient, as described above.

◆ operator/() [6/6]

template<typename T >

Polynomial< T > regina::operator/	(	Polynomial< T >	poly,
		const typename Polynomial< T >::Coefficient &	scalar )

inline

Divides the given polynomial by the given scalar constant.

This uses the division operator /= for the coefficient type T.

The scalar is simply of type T; we use the identical type Polynomial<T>::Coefficient here to assist with C++ template type matching.

Precondition: The argument scalar is non-zero.

Parameters

poly	the polynomial to divide by the given scalar.
scalar	the scalar factor to divide by.

Returns: the quotient of the given polynomial by the given scalar.

◆ operator<<() [1/7]

template<bool supportInfinity>

std::ostream & regina::operator<<	(	std::ostream &	out,
		const IntegerBase< supportInfinity > &	i )

Writes the given integer to the given output stream.

Parameters

out	the output stream to which to write.
i	the integer to write.

Returns: a reference to out.

◆ operator<<() [2/7]

std::ostream & regina::operator<<	(	std::ostream &	out,
		const Matrix2 &	mat )

inline

Writes the given matrix to the given output stream.

The matrix will be written entirely on a single line, with the first row followed by the second row.

Parameters

out	the output stream to which to write.
mat	the matrix to write.

Returns: a reference to out.

◆ operator<<() [3/7]

template<int bytes>

std::ostream & regina::operator<<	(	std::ostream &	out,
		const NativeInteger< bytes > &	i )

inline

Writes the given integer to the given output stream.

Parameters

out	the output stream to which to write.
i	the integer to write.

Returns: a reference to out.

◆ operator<<() [4/7]

template<int n>

std::ostream & regina::operator<<	(	std::ostream &	out,
		const Perm< n > &	p )

inline

Writes a string representation of the given permutation to the given output stream.

The format will be the same as is used by Perm::str().

Parameters

out	the output stream to which to write.
p	the permutation to write.

Returns: a reference to out.

Template Parameters

n	the number of objects being permuted. This must be between 2 and 16 inclusive.

◆ operator<<() [5/7]

template<int n>

std::ostream & regina::operator<<	(	std::ostream &	out,
		const PermClass< n > &	c )

inline

Writes a string representation of the given conjugacy class of permutations to the given output stream.

The format will be the same as is used by PermClass<n>::str().

Parameters

out	the output stream to which to write.
c	the conjugacy class to write.

Returns: a reference to out.

Template Parameters

n	the number of objects being permuted. This must be between 2 and 16 inclusive.

◆ operator<<() [6/7]

std::ostream & regina::operator<<	(	std::ostream &	out,
		const Rational &	rat )

Writes the given rational to the given output stream.

Infinity will be written as Inf. Undefined will be written as Undef. A rational with denominator one will be written as a single integer. All other rationals will be written in the form r/s.

Parameters

out	the output stream to which to write.
rat	the rational to write.

Returns: a reference to out.

◆ operator<<() [7/7]

template<class T >

std::ostream & regina::operator<<	(	std::ostream &	out,
		const Vector< T > &	vector )

Writes the given vector to the given output stream.

The vector will be written on a single line with elements separated by a single space. No newline will be written.

Parameters

out	the output stream to which to write.
vector	the vector to write.

Returns: a reference to out.

◆ preImageOfLattice()

MatrixInt regina::preImageOfLattice	(	const MatrixInt &	hom,
		const std::vector< Integer > &	sublattice )

Given a homomorphism from Z^n to Z^k and a sublattice of Z^k, compute the preimage of this sublattice under this homomorphism.

The homomorphism from Z^n to Z^k is described by the given k by n matrix hom. The sublattice is of the form (p1 Z) * (p2 Z) * ... * (pk Z), where the non-negative integers p1, ..., pk are passed in the given list sublattice.

An equivalent problem is to consider hom to be a homomorphism from Z^n to Z_p1 + ... + Z_pk; this routine then finds the kernel of this homomorphism.

The preimage of the sublattice (equivalently, the kernel described above) is some rank n lattice in Z^n. This algorithm finds and returns a basis for the lattice.

Parameters

hom	the matrix representing the homomorphism from Z^n to Z^k; this must be a k by n matrix.
sublattice	a list of length k describing the sublattice of Z^k; the elements of this list must be the non-negative integers p1, ..., pk as described above.

Returns: a new matrix whose columns are a basis for the preimage lattice. This matrix will have precisely n rows.

Author: Ryan Budney

◆ reducedMod()

long regina::reducedMod	(	long	k,
		long	modBase )

Reduces k modulo modBase to give the smallest possible absolute value.

For instance, reducedMod(4,10) = 4 but reducedMod(6,10) = -4. In the case of a tie, the positive solution is taken.

Precondition: modBase is strictly positive.

Parameters

k	the number to reduce modulo modBase.
modBase	the modular base in which to work.

◆ rowBasis()

size_t regina::rowBasis ( MatrixInt & matrix )

Find a basis for the row space of the given matrix.

This routine will rearrange the rows of the given matrix so that the first rank rows form a basis for the row space (where rank is the rank of the matrix). The rank itself will be returned. No other changes will be made to the matrix aside from swapping rows.

Although this routine takes an integer matrix (and only uses integer operations), we consider the row space to be over the rationals. That is, although we never divide, we act as though we could if we wanted to.

Parameters

matrix the matrix to examine and rearrange.

Returns: the rank of the given matrix.

◆ rowBasisAndOrthComp()

size_t regina::rowBasisAndOrthComp	(	MatrixInt &	input,
		MatrixInt &	complement )

Finds a basis for the row space of the given matrix, as well as an "incremental" basis for its orthogonal complement.

This routine takes an (r by c) matrix input, as well as a square (c by c) matrix complement, and does the following:

The rows of input are rearranged so that the first rank rows form a basis for the row space (where rank is the rank of the matrix). No other changes are made to this matrix aside from swapping rows.
The matrix complement is re-filled (any previous contents are thrown away) so that, for any i between 0 and rank-1 inclusive, the final (c - i) rows of complement form a basis for the orthogonal complement of the first i rows of the rearranged input.
The rank of the matrix input is returned from this routine.

This routine can help with larger procedures that need to build up a row space and simultaneously cut down the complement one dimension at a time.

Although this routine takes integer matrices (and only uses integer operations), we consider all bases to be over the rationals. That is, although we never divide, we act as though we could if we wanted to.

Precondition: The matrix complement is a square matrix, whose size is equal to the number of columns in input.

Parameters

input	the input matrix whose row space we will describe; this matrix will be changed (though only by swapping rows).
complement	the square matrix that will be re-filled with the "incremental" basis for the orthogonal complement of input.

Returns: the rank of the given matrix input.

◆ simpler() [1/2]

bool regina::simpler	(	const Matrix2 &	m1,
		const Matrix2 &	m2 )

Determines whether the first given matrix is more aesthetically pleasing than the second.

The way in which this judgement is made is purely aesthetic on the part of the author, and is subject to change in future versions of Regina.

Parameters

m1	the first matrix to examine.
m2	the second matrix to examine.

Returns: true if m1 is deemed to be more pleasing than m2, or false if either the matrices are equal or m2 is more pleasing than m1.

◆ simpler() [2/2]

bool regina::simpler	(	const Matrix2 &	pair1first,
		const Matrix2 &	pair1second,
		const Matrix2 &	pair2first,
		const Matrix2 &	pair2second )

Determines whether the first given pair of matrices is more aesthetically pleasing than the second pair.

The way in which this judgement is made is purely aesthetic on the part of the author, and is subject to change in future versions of Regina.

Note that pairs are ordered, so the pair (M, N) may be more (or perhaps less) pleasing than the pair (N, M).

Parameters

pair1first	the first matrix of the first pair to examine.
pair1second	the second matrix of the first pair to examine.
pair2first	the first matrix of the second pair to examine.
pair2second	the second matrix of the second pair to examine.

Returns: true if the first pair is deemed to be more pleasing than the second pair, or false if either the ordered pairs are equal or the second pair is more pleasing than the first.

◆ smithNormalForm() [1/2]

void regina::smithNormalForm ( MatrixInt & matrix )

Transforms the given integer matrix into Smith normal form.

Note that the given matrix need not be square and need not be of full rank.

Reading down the diagonal, the final Smith normal form will have a series of non-negative, non-decreasing invariant factors followed by zeroes. "Invariant factor" refers to the convention that the ith term divides the (i+1)th term, and so they are unique.

The algorithm used is due to Hafner and McCurley (1991). It does not use modular arithmetic to control the intermediate coefficient explosion.

Parameters

matrix the matrix to transform.

◆ smithNormalForm() [2/2]

void regina::smithNormalForm	(	MatrixInt &	matrix,
		MatrixInt &	rowSpaceBasis,
		MatrixInt &	rowSpaceBasisInv,
		MatrixInt &	colSpaceBasis,
		MatrixInt &	colSpaceBasisInv )

A Smith normal form algorithm that also returns change of basis matrices.

This is a modification of the one-argument smithNormalForm(MatrixInt&). As well as converting the given matrix matrix into Smith normal form, it also returns the appropriate change-of-basis matrices corresponding to all the row and column operations that were performed.

The only input argument is matrix. The four remaining arguments (the change of basis matrices) will be refilled. All five arguments are used to return information as follows.

Let M be the initial value of matrix, and let S be the Smith normal form of M. After this routine exits:

The argument matrix will contain the Smith normal form S;
colSpaceBasis * M * rowSpaceBasis = S;
colSpaceBasisInv * S * rowSpaceBasisInv = M;
colSpaceBasis * colSpaceBasisInv and rowSpaceBasis * rowSpaceBasisInv are both identity matrices.

Thus, one obtains the Smith normal form of the original matrix by multiplying on the left by ColSpaceBasis and on the right by RowSpaceBasis.

The matrices rowSpaceBasis and rowSpaceBasisInv that are passed may be of any size, or they may even be uninitialised; upon return they will both be square with side length matrix.columns(). Likewise, the matrices colSpaceBasis and colSpaceBasisInv that are passed may be of any size or may be uninitialised; upon return they will both be square with side length matrix.rows().

Parameters

matrix	the original matrix to put into Smith Normal Form (this need not be square). When the algorithm terminates, this matrix is in its Smith Normal Form.
rowSpaceBasis	used to return a change of basis matrix (see above for details).
rowSpaceBasisInv	used to return the inverse of rowSpaceBasis.
colSpaceBasis	used to return a change of basis matrix (see above for details).
colSpaceBasisInv	used to return the inverse of colSpaceBasis.

◆ swap() [1/10]

void regina::swap	(	Cyclotomic &	a,
		Cyclotomic &	b )

inlinenoexcept

Swaps the contents of the given field elements.

This global routine simply calls Cyclotomic::swap(); it is provided so that Cyclotomic meets the C++ Swappable requirements.

Parameters

a	the first field element whose contents should be swapped.
b	the second field element whose contents should be swapped.

◆ swap() [2/10]

template<bool supportInfinity>

void regina::swap	(	IntegerBase< supportInfinity > &	a,
		IntegerBase< supportInfinity > &	b )

inlinenoexcept

Swaps the contents of the given integers.

This global routine simply calls IntegerBase<supportInfinity>::swap(); it is provided so that IntegerBase<supportInfinity> meets the C++ Swappable requirements.

Parameters

a	the first integer whose contents should be swapped.
b	the second integer whose contents should be swapped.

◆ swap() [3/10]

template<typename T >

void regina::swap	(	Laurent2< T > &	a,
		Laurent2< T > &	b )

inlinenoexcept

Swaps the contents of the given polynomials.

This global routine simply calls Laurent2<T>::swap(); it is provided so that Laurent2<T> meets the C++ Swappable requirements.

Parameters

a	the first polynomial whose contents should be swapped.
b	the second polynomial whose contents should be swapped.

◆ swap() [4/10]

template<typename T >

void regina::swap	(	Laurent< T > &	a,
		Laurent< T > &	b )

inlinenoexcept

Swaps the contents of the given polynomials.

This global routine simply calls Laurent<T>::swap(); it is provided so that Laurent<T> meets the C++ Swappable requirements.

Parameters

a	the first polynomial whose contents should be swapped.
b	the second polynomial whose contents should be swapped.

◆ swap() [5/10]

void regina::swap	(	Matrix2 &	a,
		Matrix2 &	b )

inlinenoexcept

Swaps the contents of the two given matrices.

This global routine simply calls Matrix2::swap(); it is provided so that Matrix2 meets the C++ Swappable requirements.

Parameters

a	the first matrix whose contents should be swapped.
b	the second matrix whose contents should be swapped.

◆ swap() [6/10]

template<typename T >

void regina::swap	(	Matrix< T > &	a,
		Matrix< T > &	b )

inlinenoexcept

Swaps the contents of the given matrices.

This global routine simply calls Matrix<T>::swap(); it is provided so that Matrix<T> meets the C++ Swappable requirements.

Parameters

a	the first matrix whose contents should be swapped.
b	the second matrix whose contents should be swapped.

◆ swap() [7/10]

template<int bytes>

void regina::swap	(	NativeInteger< bytes > &	a,
		NativeInteger< bytes > &	b )

inlinenoexcept

Swaps the contents of the given integers.

This global routine simply calls NativeInteger<bytes>::swap(); it is provided so that NativeInteger<bytes> meets the C++ Swappable requirements.

Python: Not present. The NativeInteger classes are not available to Python users.

Parameters

a	the first integer whose contents should be swapped.
b	the second integer whose contents should be swapped.

◆ swap() [8/10]

template<typename T >

void regina::swap	(	Polynomial< T > &	a,
		Polynomial< T > &	b )

inlinenoexcept

Swaps the contents of the given polynomials.

This global routine simply calls Polynomial<T>::swap(); it is provided so that Polynomial<T> meets the C++ Swappable requirements.

Parameters

a	the first polynomial whose contents should be swapped.
b	the second polynomial whose contents should be swapped.

◆ swap() [9/10]

void regina::swap	(	Rational &	a,
		Rational &	b )

inlinenoexcept

Swaps the contents of the given rationals.

This global routine simply calls Rational::swap(); it is provided so that Rational meets the C++ Swappable requirements.

Parameters

a	the first rational whose contents should be swapped.
b	the second rational whose contents should be swapped.

◆ swap() [10/10]

template<typename T >

void regina::swap	(	Vector< T > &	a,
		Vector< T > &	b )

inlinenoexcept

Swaps the contents of the given vectors.

This global routine simply calls Vector<T>::swap(); it is provided so that Vector<T> meets the C++ Swappable requirements.

Parameters

a	the first vector whose contents should be swapped.
b	the second vector whose contents should be swapped.

◆ tightEncode()

template<bool supportInfinity>

void regina::tightEncode	(	std::ostream &	out,
		IntegerBase< supportInfinity >	value )

Writes the tight encoding of the given arbitrary precision integer to the given output stream.

See the page on tight encodings for details.

This global function does the same thing as the member function IntegerBase::tightEncode(). However, this global function is more efficient if the integer argument is an rvalue reference (since the const member function induces an extra deep copy).

Python: Not present. Use tightEncoding() instead.

Parameters

out	the output stream to which the encoded string will be written.
value	the integer to encode.

◆ tightEncoding()

template<bool supportInfinity>

std::string regina::tightEncoding ( IntegerBase< supportInfinity > value )

Returns the tight encoding of the given arbitrary precision integer.

See the page on tight encodings for details.

This global function does the same thing as the member function IntegerBase::tightEncoding(). However, this global function is more efficient if the integer argument is an rvalue reference (since the const member function induces an extra deep copy).

Parameters

value the integer to encode.

Returns: the resulting encoded string.

◆ torsionAutInverse()

MatrixInt regina::torsionAutInverse	(	const MatrixInt &	input,
		const std::vector< Integer > &	invF )

Given an automorphism of an abelian group, this procedure computes the inverse automorphism.

The abelian group is of the form Z_p1 + Z_p2 + ... + Z_pn. The input is an n-by-n matrix A which represents a lift of the automorphism to just some n-by-n matrix. Specifically, you have a little commutative diagram with Z^n --A--> Z^n covering the automorphism of Z_p1 + Z_p2 + ... + Z_pn, where the maps down are the direct sum of the standard quotients Z --> Z_pi. So if you want this procedure to give you meaningful output, A must be a lift of a genuine automorphism of Z_p1 + ... + Z_pn.

Precondition: The list p1, p2, ..., pn is a list of invariant factors, which means that p1|p2, ..., p{n-1}|pn.

Parameters

input	the n-by-n matrix A, which must be a lift of a genuine automorphism as described above.
invF	the list p1, p2, ..., pn.

Returns: the inverse automorphism, also described as an n-by-n matrix as per the discussion above.

Author: Ryan Budney

Variable Documentation

◆ binomSmall_

int regina::detail::binomSmall_[17][17]

inlineconstexpr

Initial value:

= {
    {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,3,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,4,6,4,1,0,0,0,0,0,0,0,0,0,0,0,0},
    {1,5,10,10,5,1,0,0,0,0,0,0,0,0,0,0,0},
    {1,6,15,20,15,6,1,0,0,0,0,0,0,0,0,0,0},
    {1,7,21,35,35,21,7,1,0,0,0,0,0,0,0,0,0},
    {1,8,28,56,70,56,28,8,1,0,0,0,0,0,0,0,0},
    {1,9,36,84,126,126,84,36,9,1,0,0,0,0,0,0,0},
    {1,10,45,120,210,252,210,120,45,10,1,0,0,0,0,0,0},
    {1,11,55,165,330,462,462,330,165,55,11,1,0,0,0,0,0},
    {1,12,66,220,495,792,924,792,495,220,66,12,1,0,0,0,0},
    {1,13,78,286,715,1287,1716,1716,1287,715,286,78,13,1,0,0,0},
    {1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364,91,14,1,0,0},
    {1,15,105,455,1365,3003,5005,6435,6435,5005,3003,1365,455,105,15,1,0},
    {1,16,120,560,1820,4368,8008,11440,12870,11440,8008,4368,1820,560,120,16,1}
}

A lookup table that stores (n choose k) for all n ≤ 16.

For all values 0 ≤ k ≤ n ≤ 16, the value binomSmall_[n][k] is the binomial coefficient (n choose k).

This array is used in the implementation of the function binomSmall(). End users should call binomSmall() instead of referring to this array directly.

Classes

Macros

Typedefs

Enumerations

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ mpz_cmp_si_cpp

Typedef Documentation

◆ Integer

◆ LargeInteger

◆ MatrixBool

◆ MatrixInt

◆ NativeLong

◆ VectorInt

◆ VectorLarge

Enumeration Type Documentation

◆ PermCodeType

Function Documentation

◆ binomMedium()

◆ binomSmall()

◆ columnEchelonForm()

◆ digit()

◆ factorial()

◆ gcd()

◆ gcdWithCoeffs()

◆ lcm()

◆ metricalSmithNormalForm()

◆ modularInverse()

◆ operator*() [1/13]

◆ operator*() [2/13]

◆ operator*() [3/13]

◆ operator*() [4/13]

◆ operator*() [5/13]

◆ operator*() [6/13]

◆ operator*() [7/13]

◆ operator*() [8/13]

◆ operator*() [9/13]

◆ operator*() [10/13]

◆ operator*() [11/13]

◆ operator*() [12/13]

◆ operator*() [13/13]

◆ operator+() [1/17]

◆ operator+() [2/17]

◆ operator+() [3/17]

◆ operator+() [4/17]

◆ operator+() [5/17]

◆ operator+() [6/17]

◆ operator+() [7/17]

◆ operator+() [8/17]

◆ operator+() [9/17]

◆ operator+() [10/17]

◆ operator+() [11/17]

◆ operator+() [12/17]

◆ operator+() [13/17]

◆ operator+() [14/17]

◆ operator+() [15/17]

◆ operator+() [16/17]

◆ operator+() [17/17]

◆ operator-() [1/20]

◆ operator-() [2/20]

◆ operator-() [3/20]

◆ operator-() [4/20]

◆ operator-() [5/20]

◆ operator-() [6/20]

◆ operator-() [7/20]

◆ operator-() [8/20]

◆ operator-() [9/20]

◆ operator-() [10/20]

◆ operator-() [11/20]

◆ operator-() [12/20]

◆ operator-() [13/20]

◆ operator-() [14/20]

◆ operator-() [15/20]

◆ operator-() [16/20]

◆ operator-() [17/20]

◆ operator-() [18/20]

◆ operator-() [19/20]

◆ operator-() [20/20]