Regina Calculation Engine
Public Member Functions | Static Public Member Functions | Static Public Attributes | Friends | List of all members
regina::IntegerBase< supportInfinity > Class Template Reference

Represents an arbitrary precision integer. More...

#include <maths/integer.h>

Inheritance diagram for regina::IntegerBase< supportInfinity >:
regina::InfinityBase< false >

Public Member Functions

 IntegerBase ()
 Initialises this integer to zero. More...
 
 IntegerBase (int value)
 Initialises this integer to the given value. More...
 
 IntegerBase (unsigned value)
 Initialises this integer to the given value. More...
 
 IntegerBase (long value)
 Initialises this integer to the given value. More...
 
 IntegerBase (unsigned long value)
 Initialises this integer to the given value. More...
 
 IntegerBase (const IntegerBase< supportInfinity > &value)
 Initialises this integer to the given value. More...
 
 IntegerBase (const IntegerBase<! supportInfinity > &value)
 Initialises this integer to the given value. More...
 
template<int bytes>
 IntegerBase (const NativeInteger< bytes > &value)
 Initialises this integer to the given value. More...
 
 IntegerBase (Long value)
 Initialises this to the given Python arbitrary-precision integer. More...
 
 IntegerBase (double value)
 Initialises this integer to the truncation of the given real number. More...
 
 IntegerBase (const char *value, int base=10, bool *valid=nullptr)
 Initialises this integer to the given value which is represented as a string of digits in a given base. More...
 
 IntegerBase (const std::string &value, int base=10, bool *valid=nullptr)
 Initialises this integer to the given value which is represented as a string of digits in a given base. More...
 
 ~IntegerBase ()
 Destroys this integer. More...
 
bool isNative () const
 Returns whether we are currently working with a native C/C++ long, or whether we have switched to GMP large integer arithmetic for this integer. More...
 
bool isZero () const
 Returns whether or not this integer is zero. More...
 
int sign () const
 Returns the sign of this integer. More...
 
bool isInfinite () const
 Returns whether this integer is infinity. More...
 
void makeInfinite ()
 Sets this integer to be infinity. More...
 
long longValue () const
 Returns the value of this integer as a long. More...
 
template<int bytes>
IntOfSize< bytes >::type nativeValue () const
 Returns the value of this integer as a native integer of some fixed byte length. More...
 
std::string stringValue (int base=10) const
 Returns the value of this integer as a string in the given base. More...
 
IntegerBaseoperator= (const IntegerBase &value)
 Sets this integer to the given value. More...
 
IntegerBaseoperator= (const IntegerBase<! supportInfinity > &value)
 Sets this integer to the given value. More...
 
IntegerBaseoperator= (int value)
 Sets this integer to the given value. More...
 
IntegerBaseoperator= (unsigned value)
 Sets this integer to the given value. More...
 
IntegerBaseoperator= (long value)
 Sets this integer to the given value. More...
 
IntegerBaseoperator= (unsigned long value)
 Sets this integer to the given value. More...
 
IntegerBaseoperator= (const char *value)
 Sets this integer to the given value which is represented as a string of digits in base 10. More...
 
IntegerBaseoperator= (const std::string &value)
 Sets this integer to the given value which is represented as a string of digits in base 10. More...
 
void swap (IntegerBase &other)
 Swaps the values of this and the given integer. More...
 
bool operator== (const IntegerBase &rhs) const
 Determines if this is equal to the given integer. More...
 
bool operator== (const IntegerBase<! supportInfinity > &rhs) const
 Determines if this is equal to the given integer. More...
 
bool operator== (long rhs) const
 Determines if this is equal to the given integer. More...
 
bool operator!= (const IntegerBase &rhs) const
 Determines if this is not equal to the given integer. More...
 
bool operator!= (const IntegerBase<! supportInfinity > &rhs) const
 Determines if this is not equal to the given integer. More...
 
bool operator!= (long rhs) const
 Determines if this is not equal to the given integer. More...
 
bool operator< (const IntegerBase &rhs) const
 Determines if this is less than the given integer. More...
 
bool operator< (long rhs) const
 Determines if this is less than the given integer. More...
 
bool operator> (const IntegerBase &rhs) const
 Determines if this is greater than the given integer. More...
 
bool operator> (long rhs) const
 Determines if this is greater than the given integer. More...
 
bool operator<= (const IntegerBase &rhs) const
 Determines if this is less than or equal to the given integer. More...
 
bool operator<= (long rhs) const
 Determines if this is less than or equal to the given integer. More...
 
bool operator>= (const IntegerBase &rhs) const
 Determines if this is greater than or equal to the given integer. More...
 
bool operator>= (long rhs) const
 Determines if this is greater than or equal to the given integer. More...
 
IntegerBaseoperator++ ()
 The preincrement operator. More...
 
IntegerBase operator++ (int)
 The postincrement operator. More...
 
IntegerBaseoperator-- ()
 The predecrement operator. More...
 
IntegerBase operator-- (int)
 The postdecrement operator. More...
 
IntegerBase operator+ (const IntegerBase &other) const
 Adds this to the given integer and returns the result. More...
 
IntegerBase operator+ (long other) const
 Adds this to the given integer and returns the result. More...
 
IntegerBase operator- (const IntegerBase &other) const
 Subtracts the given integer from this and returns the result. More...
 
IntegerBase operator- (long other) const
 Subtracts the given integer from this and returns the result. More...
 
IntegerBase operator* (const IntegerBase &other) const
 Multiplies this by the given integer and returns the result. More...
 
IntegerBase operator* (long other) const
 Multiplies this by the given integer and returns the result. More...
 
IntegerBase operator/ (const IntegerBase &other) const
 Divides this by the given integer and returns the result. More...
 
IntegerBase operator/ (long other) const
 Divides this by the given integer and returns the result. More...
 
IntegerBase divExact (const IntegerBase &other) const
 Divides this by the given integer and returns the result. More...
 
IntegerBase divExact (long other) const
 Divides this by the given integer and returns the result. More...
 
IntegerBase operator% (const IntegerBase &other) const
 Determines the remainder when this integer is divided by the given integer. More...
 
IntegerBase operator% (long other) const
 Determines the remainder when this integer is divided by the given integer. More...
 
IntegerBase< supportInfinity > divisionAlg (const IntegerBase< supportInfinity > &divisor, IntegerBase< supportInfinity > &remainder) const
 Uses the division algorithm to obtain a quotient and remainder when dividing by the given integer. More...
 
IntegerBase operator- () const
 Determines the negative of this integer. More...
 
IntegerBaseoperator+= (const IntegerBase &other)
 Adds the given integer to this. More...
 
IntegerBaseoperator+= (long other)
 Adds the given integer to this. More...
 
IntegerBaseoperator-= (const IntegerBase &other)
 Subtracts the given integer from this. More...
 
IntegerBaseoperator-= (long other)
 Subtracts the given integer from this. More...
 
IntegerBaseoperator*= (const IntegerBase &other)
 Multiplies the given integer by this. More...
 
IntegerBaseoperator*= (long other)
 Multiplies the given integer by this. More...
 
IntegerBaseoperator/= (const IntegerBase &other)
 Divides this by the given integer. More...
 
IntegerBaseoperator/= (long other)
 Divides this by the given integer. More...
 
IntegerBasedivByExact (const IntegerBase &other)
 Divides this by the given integer. More...
 
IntegerBasedivByExact (long other)
 Divides this by the given integer. More...
 
IntegerBaseoperator%= (const IntegerBase &other)
 Reduces this integer modulo the given integer. More...
 
IntegerBaseoperator%= (long other)
 Reduces this integer modulo the given integer. More...
 
void negate ()
 Negates this integer. More...
 
void raiseToPower (unsigned long exp)
 Raises this integer to the power of the given exponent. More...
 
IntegerBase abs () const
 Determines the absolute value of this integer. More...
 
void gcdWith (const IntegerBase &other)
 Sets this integer to be the greatest common divisor of this and the given integer. More...
 
IntegerBase gcd (const IntegerBase &other) const
 Determines the greatest common divisor of this and the given integer. More...
 
void lcmWith (const IntegerBase &other)
 Sets this integer to be the lowest common multiple of this and the given integer. More...
 
IntegerBase lcm (const IntegerBase &other) const
 Determines the lowest common multiple of this and the given integer. More...
 
IntegerBase< supportInfinity > gcdWithCoeffs (const IntegerBase< supportInfinity > &other, IntegerBase< supportInfinity > &u, IntegerBase< supportInfinity > &v) const
 Determines the greatest common divisor of this and the given integer and finds the smallest coefficients with which these integers combine to give their gcd. More...
 
int legendre (const IntegerBase< supportInfinity > &p) const
 Returns the Legendre symbol (a/p), where a is this integer and p is an odd prime. More...
 
IntegerBase< supportInfinity > randomBoundedByThis () const
 Generate a pseudo-random integer that is uniformly distributed in the interval [0,*this). More...
 
void setRaw (mpz_srcptr fromData)
 Set this to a copy of the given raw GMP integer. More...
 
mpz_srcptr rawData () const
 Returns the raw GMP data that describes this integer. More...
 
mpz_ptr rawData ()
 Returns the raw GMP data that describes this integer. More...
 
void makeLarge ()
 Converts this integer to use a GMP large integer representation, regardless of whether this is actually necessary. More...
 
void tryReduce ()
 Converts this integer to use a native C/C++ long representation, if this is possible. More...
 

Static Public Member Functions

static IntegerBase< supportInfinity > randomBinary (unsigned long n)
 Generate a pseudo-random integer that is uniformly distributed in the interval [0,2^n). More...
 
static IntegerBase< supportInfinity > randomCornerBinary (unsigned long n)
 Generate a pseudo-random integer that is distributed in the interval [0,2^n), with a tendency to have long strings of 0s and 1s in its binary expansion. More...
 

Static Public Attributes

static const IntegerBase< supportInfinity > zero
 Globally available zero. More...
 
static const IntegerBase< supportInfinity > one
 Globally available one. More...
 
static const IntegerBase< supportInfinity > infinity
 Globally available infinity. More...
 

Friends

template<int bytes>
class NativeInteger
 
template<bool supportInfinity_>
std::ostream & operator<< (std::ostream &out, const IntegerBase< supportInfinity_ > &large)
 

Detailed Description

template<bool supportInfinity = false>
class regina::IntegerBase< supportInfinity >

Represents an arbitrary precision integer.

Calculations are always guaranteed to be exact, regardless of how large the integers become.

The current implementation uses fast native integer arithmetic wherever possible, whilst always testing for potential overflow. If a potential overflow is detected, this class switches to using the GNU multiple precision arithmetic library (libgmp) instead.

This class takes a single boolean argument supportInfinity. If this is true, then this class will support infinity as an allowed value. If this is false (the default), then infinity is not supported, and any attempt to work with infinity will lead to undefined behaviour. Supporting infinity is more flexible, but also comes with a slight performance cost (very roughly estimated at around 10%-20%).

For the purposes of comparison, infinity is considered larger than any other integer but equal to itself.

All routines in this class, including random number generation, are thread-safe.

The opportunistic use of native arithmetic where possible was inspired by the (much more complex and powerful) lazy exact arithmetic in CGAL. Thanks to Menelaos Karavelas for encouraging me to take another look at these ideas.

Headers:\n Parts of this template class are implemented in a C++ source
file that is not available through the headers. However, this should not affect users since the calculation engine includes explicit instantiations for all possible template parameters.
Python:\n Both variants of this template are available through Python.
For supportInfinity = false, use the name Integer. For supportInfinity = true, use the name LargeInteger.

The documentation for this class was generated from the following file:

Copyright © 1999-2018, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).