Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

Mathematical Support

Underlying mathematical gruntwork. More...

Classes

class  regina::NMatrix< T >
 Represents a matrix of elements of the given type T. More...

class  regina::NMatrixRing< T >
 Represents a matrix of elements from a given ring T. More...

class  regina::NMatrixField< T >
 Represents a matrix of elements from a given field T. More...

class  regina::NMatrixInt
 Represents a matrix of arbitrary precision integers. More...

class  regina::NRay
 Represents a ray rooted at the origin whose coordinates are rational. More...

class  regina::NVector< T >
 A vector of elements from a given ring T. More...

class  regina::NVectorDense< T >
 A dense vector of objects of type T. More...

class  regina::NVectorMatrix_Illegal_Modification
 An exception thrown when a matrix row or column vector is modified. More...

class  regina::NVectorMatrix< T >
 A vector that corresponds to a row or column of a matrix. More...

class  regina::NVectorMatrixRow< T >
 A vector that corresponds to a row of a matrix. More...

class  regina::NVectorMatrixCol< T >
 A vector that corresponds to a column of a matrix. More...

class  regina::NVectorUnit_Illegal_Modification
 An exception thrown when a unit vector is modified. More...

class  regina::NVectorUnit< T >
 A unit vector of type T. More...


Functions

template<class R> bool regina::isZero (R x)
 Determines whether the given real or complex number is zero.

template<class R> bool regina::isNonZero (R x)
 Determines whether the given real or complex number is non-zero.

template<class R> bool regina::isPositive (R x)
 Determines whether the given real or complex number is strictly positive.

template<class R> bool regina::isNegative (R x)
 Determines whether the given real or complex number is strictly negative.

template<class R> bool regina::isNonNegative (R x)
 Determines whether the given real or complex number is non-negative.

template<class R> bool regina::isNonPositive (R x)
 Determines whether the given real or complex number is non-positive.

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

NRay * regina::intersect (const NRay &pos, const NRay &neg, const NVector< NLargeInteger > &hyperplane)
 Returns a newly allocated ray representing the intersection of the hyperplane joining two given rays with the given additional hyperplane.

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

unsigned long regina::gcd (unsigned long a, unsigned long b)
 Calculates the greatest common divisor of two given integers.

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

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

void regina::factorise (unsigned long n, std::list< unsigned long > &factors)
 Calculates the prime factorisation of the given integer.

void regina::primesUpTo (const NLargeInteger &roof, std::list< NLargeInteger > &primes)
 Determines all primes up to and including the given upper bound.

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

 regina::NMatrixInt::NMatrixInt (unsigned long rows, unsigned long cols)
 Creates a new matrix of the given size.

 regina::NMatrixInt::NMatrixInt (const NMatrixInt &cloneMe)
 Creates a new matrix that is a clone of the given matrix.

virtual void regina::NMatrixInt::writeTextShort (std::ostream &out) const
 Writes this object in short text format to the given output stream.

virtual void regina::NMatrixInt::writeTextLong (std::ostream &out) const
 Writes this object in long text format to the given output stream.


Variables

const double regina::epsilon
 A very small positive real designed to accommodate for rounding error.

regina::NMatrixRing::zero
 Zero in the underlying ring.

regina::NMatrixRing::one
 One (the multiplicative identity) in the underlying ring.

regina::NVector::zero
 Zero in the underlying number system.

regina::NVector::one
 One in the underlying number system.

regina::NVector::minusOne
 Negative one in the underlying number system.


Detailed Description

Underlying mathematical gruntwork.


Function Documentation

void factorise unsigned long  n,
std::list< unsigned long > &  factors
 

Calculates the prime factorisation of the given integer.

All the prime factors will be inserted into the given list. The algorithm used is very neanderthal and should only be used with reasonably sized integers. Don't use it to do RSA!

If a prime factor is repeated, it will be inserted multiple times into the list. The primes in the list are not guaranteed to appear in any specific order, nor are multiple occurrences of the same prime guaranteed to appear together.

Note that once finished the list will contain the prime factors as well as whatever happened to be in the list before this function was called.

Precondition:
The given integer is at least 1.
Python:
Argument factors is not present; instead this routine returns a python list containing the prime factors.
Parameters:
n the integer to factorise.
factors the list into which prime factors will be inserted.

unsigned long gcd unsigned long  a,
unsigned long  b
 

Calculates the greatest common divisor of two given integers.

This routine is not recursive.

Precondition:
Both integers are non-negative.

Test:
Test suite contains thorough tests.
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.

long gcdWithCoeffs long  a,
long  b,
long &  u,
long &  v
 

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.

If d is the gcd of a and b, the values placed in u and v will be those 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.

Test:
Test suite contains thorough tests.
Parameters:
a one of the integers to work with.
b the other integer with which to work.
u a variable into which the final coefficient of a will be placed.
v a variable into which the final coefficient of b will be placed.
Returns:
the greatest common divisor of a and b.

NRay* intersect const NRay &  pos,
const NRay &  neg,
const NVector< NLargeInteger > &  hyperplane
 

Returns a newly allocated ray representing the intersection of the hyperplane joining two given rays with the given additional hyperplane.

The resulting ray will be in its smallest integral form.

The given additional hyperplane must pass through the origin, and is represented by a vector perpendicular to it.

If the arguments pos and neg are on the positive and negative sides of the hyperplane respectively (where positive and negative sides are determined by the sign of the dot product of a ray vector with the hyperplane representation vector), the resulting ray is guaranteed to be a positive multiple of a convex combination of the two original rays.

The resulting ray is guaranteed to be of the same subclass of NRay as argument neg.

Precondition:
The two given rays lie on opposite sides of the given additional hyperplane; neither actually lies within the given additional hyperplane.
Python:
Not present.
Parameters:
pos one of the two given rays.
neg the other of the two given rays.
hyperplane a perpendicular to the given additional hyperplane.
Returns:
a newly allocated ray representing the intersection of hyperplane with the hyperplane joining a and b.

template<class R>
bool isNegative x  )  [inline]
 

Determines whether the given real or complex number is strictly negative.

Any number within regina::epsilon of zero is considered to be zero.

Precondition:
R must be of a floating point real or complex type.
Python:
Not present.
Parameters:
x the number to examine.
Returns:
true if and only if the given number is strictly negative.

template<class R>
bool isNonNegative x  )  [inline]
 

Determines whether the given real or complex number is non-negative.

Any number within regina::epsilon of zero is considered to be zero.

Precondition:
R must be of a floating point real or complex type.
Python:
Not present.
Parameters:
x the number to examine.
Returns:
true if and only if the given number is non-negative.

template<class R>
bool isNonPositive x  )  [inline]
 

Determines whether the given real or complex number is non-positive.

Any number within regina::epsilon of zero is considered to be zero.

Precondition:
R must be of a floating point real or complex type.
Python:
Not present.
Parameters:
x the number to examine.
Returns:
true if and only if the given number is non-positive.

template<class R>
bool isNonZero x  )  [inline]
 

Determines whether the given real or complex number is non-zero.

Any number within regina::epsilon of zero is considered to be zero.

Precondition:
R must be of a floating point real or complex type.
Python:
Not present.
Parameters:
x the number to examine.
Returns:
true if and only if the given number is approximately non-zero.

template<class R>
bool isPositive x  )  [inline]
 

Determines whether the given real or complex number is strictly positive.

Any number within regina::epsilon of zero is considered to be zero.

Precondition:
R must be of a floating point real or complex type.
Python:
Not present.
Parameters:
x the number to examine.
Returns:
true if and only if the given number is strictly positive.

template<class R>
bool isZero x  )  [inline]
 

Determines whether the given real or complex number is zero.

Any number within regina::epsilon of zero is considered to be zero.

Precondition:
R must be of a floating point real or complex type.
Python:
Not present.
Parameters:
x the number to examine.
Returns:
true if and only if the given number is approximately zero.

unsigned long 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.

Test:
Test suite contains thorough tests.
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).

regina::NMatrixInt::NMatrixInt const NMatrixInt cloneMe  )  [inline, inherited]
 

Creates a new matrix that is a clone of the given matrix.

Parameters:
cloneMe the matrix to clone.

regina::NMatrixInt::NMatrixInt unsigned long  rows,
unsigned long  cols
[inline, inherited]
 

Creates a new matrix of the given size.

All entries will be initialised to zero.

Precondition:
The given number of rows and columns are both strictly positive.
Parameters:
rows the number of rows in the new matrix.
cols the number of columns in the new matrix.

template<class T>
std::ostream& operator<< std::ostream &  out,
const NVector< 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.

Python:
Not present.
Parameters:
out the output stream to which to write.
vector the vector to write.
Returns:
a reference to out.

void primesUpTo const NLargeInteger &  roof,
std::list< NLargeInteger > &  primes
 

Determines all primes up to and including the given upper bound.

All the primes found will be inserted into the given list in increasing order.

The algorithm currently used is fairly neanderthal.

Precondition:
The given list is empty.
Python:
Argument primes is not present; instead this routine returns a python list containing the primes up to and including roof.
Parameters:
roof the upper bound up to which primes will be found.
primes the list into which the primes will be inserted.

long 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.

Test:
Test suite contains thorough tests.
Parameters:
k the number to reduce modulo modBase.
modBase the modular base in which to work.

void smithNormalForm NMatrixInt &  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.

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.

void regina::NMatrixInt::writeTextLong std::ostream &  out  )  const [inline, virtual, inherited]
 

Writes this object in long text format to the given output stream.

The output should provided the user with all the information they could want. The output should end with a newline.

The default implementation of this routine merely calls writeTextShort() and adds a newline.

Python:
The parameter out does not exist; standard output will be used.
Parameters:
out the output stream to which to write.

Reimplemented from regina::ShareableObject.

void regina::NMatrixInt::writeTextShort std::ostream &  out  )  const [inline, virtual, inherited]
 

Writes this object in short text format to the given output stream.

The output should fit on a single line and no newline should be written.

Python:
The parameter out does not exist; standard output will be used.
Parameters:
out the output stream to which to write.

Implements regina::ShareableObject.


Variable Documentation

const double regina::epsilon
 

A very small positive real designed to accommodate for rounding error.

Any two numbers within epsilon of each other are considred to be equal.

template<class T>
T regina::NVector< T >::minusOne [static, inherited]
 

Negative one in the underlying number system.

This would be const if it weren't for the fact that some compilers don't like this. It should never be modified!

template<class T>
T regina::NVector< T >::one [static, inherited]
 

One in the underlying number system.

This would be const if it weren't for the fact that some compilers don't like this. It should never be modified!

template<class T>
T regina::NMatrixRing< T >::one [static, inherited]
 

One (the multiplicative identity) in the underlying ring.

This would be const if it weren't for the fact that some compilers don't like this. It should never be modified!

template<class T>
T regina::NVector< T >::zero [static, inherited]
 

Zero in the underlying number system.

This would be const if it weren't for the fact that some compilers don't like this. It should never be modified!

template<class T>
T regina::NMatrixRing< T >::zero [static, inherited]
 

Zero in the underlying ring.

This would be const if it weren't for the fact that some compilers don't like this. It should never be modified!


Copyright © 1999-2004, Ben Burton
This software is released under the GNU General Public License.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).