Regina Calculation Engine
Public Member Functions | List of all members
regina::Polynomial< T > Class Template Reference

Represents a single-variable polynomial with coefficients of type T. More...

#include <maths/polynomial.h>

Inheritance diagram for regina::Polynomial< T >:
regina::ShortOutput< Polynomial< T >, true > regina::Output< Polynomial< T >, supportsUtf8 >

Public Member Functions

 Polynomial ()
 Creates the zero polynomial. More...
 
 Polynomial (size_t degree)
 Creates the polynomial x^d for the given degree d. More...
 
 Polynomial (const Polynomial< T > &value)
 Creates a new copy of the given polynomial. More...
 
template<typename U >
 Polynomial (const Polynomial< U > &value)
 Creates a new copy of the given polynomial. More...
 
template<typename iterator >
 Polynomial (iterator begin, iterator end)
 Creates a new polynomial from the given sequence of coefficients. More...
 
 ~Polynomial ()
 Destroys this polynomial. More...
 
void init ()
 Sets this to become the zero polynomial. More...
 
void init (size_t degree)
 Sets this to become the polynomial x^d for the given degree d. More...
 
template<typename iterator >
void init (iterator begin, iterator end)
 Sets this to become the polynomial described by the given sequence of coefficients. More...
 
size_t degree () const
 Returns the degree of this polynomial. More...
 
bool isZero () const
 Returns whether this is the zero polynomial. More...
 
bool isMonic () const
 Returns whether this polynomial is monic. More...
 
const T & leading () const
 Returns the leading coefficient of this polynomial. More...
 
const T & operator[] (size_t exp) const
 Returns the given coefficient of this polynomial. More...
 
void set (size_t exp, const T &value)
 Changes the given coefficient of this polynomial. More...
 
bool operator== (const Polynomial< T > &rhs) const
 Tests whether this and the given polynomial are equal. More...
 
bool operator!= (const Polynomial< T > &rhs) const
 Tests whether this and the given polynomial are not equal. More...
 
Polynomialoperator= (const Polynomial< T > &value)
 Sets this to be a copy of the given polynomial. More...
 
template<typename U >
Polynomialoperator= (const Polynomial< U > &value)
 Sets this to be a copy of the given polynomial. More...
 
void swap (Polynomial< T > &other)
 Swaps the contents of this and the given polynomial. More...
 
Polynomialoperator*= (const T &scalar)
 Multiplies this polynomial by the given constant. More...
 
Polynomialoperator/= (const T &scalar)
 Divides this polynomial by the given constant. More...
 
Polynomialoperator+= (const Polynomial< T > &other)
 Adds the given polynomial to this. More...
 
Polynomialoperator-= (const Polynomial< T > &other)
 Subtracts the given polynomial from this. More...
 
Polynomialoperator*= (const Polynomial< T > &other)
 Multiplies this by the given polynomial. More...
 
Polynomialoperator/= (const Polynomial< T > &other)
 Divides this by the given polynomial. More...
 
void divisionAlg (const Polynomial< T > &divisor, Polynomial< T > &quotient, Polynomial< T > &remainder) const
 Divides this by the given divisor, and extracts both the quotient and the remainder. More...
 
template<typename U >
void gcdWithCoeffs (const Polynomial< U > &other, Polynomial< T > &gcd, Polynomial< T > &u, Polynomial< T > &v) const
 Calculates the greatest common divisor of this and the given polynomial, and finds a linear combination of these polynomials that gives this gcd. More...
 
void writeTextShort (std::ostream &out, bool utf8=false, const char *variable=0) const
 Writes this polynomial to the given output stream, using the given variable name instead of x. More...
 
std::string str (const char *variable) const
 Returns this polynomial as a human-readable string, using the given variable name instead of x. More...
 
std::string utf8 (const char *variable) const
 Returns this polynomial as a human-readable string using unicode characters, using the given variable name instead of x. More...
 
template<typename U >
Polynomial< T > & operator= (const Polynomial< U > &value)
 
void writeTextLong (std::ostream &out) const
 A default implementation for detailed output. More...
 
std::string str () const
 Returns a short text representation of this object. More...
 
std::string utf8 () const
 Returns a short text representation of this object using unicode characters. More...
 
std::string detail () const
 Returns a detailed text representation of this object. More...
 

Detailed Description

template<typename T>
class regina::Polynomial< T >

Represents a single-variable polynomial with coefficients of type T.

All exponents in the polynomial must be non-negative (so you can represent 2+3x but not 1+1/x).

The type T must represent a ring with no zero divisors. In particular, it must:

This means that Regina's numerical types such as Integer and Rational are supported, but native data types such as int and long are not (since they have no zero-initialising default constructor).

The underlying storage method for this class is dense (i.e., all coefficients are explicitly stored, including zero coefficients).

Python:
In Python, the class Polynomial refers to the specific template class Polynomial<Rational>.

Constructor & Destructor Documentation

§ Polynomial() [1/5]

template<typename T >
regina::Polynomial< T >::Polynomial ( )
inline

Creates the zero polynomial.

§ Polynomial() [2/5]

template<typename T >
regina::Polynomial< T >::Polynomial ( size_t  degree)
inlineexplicit

Creates the polynomial x^d for the given degree d.

Parameters
degreethe degree of the new polynomial.

§ Polynomial() [3/5]

template<typename T >
regina::Polynomial< T >::Polynomial ( const Polynomial< T > &  value)
inline

Creates a new copy of the given polynomial.

A note for developers: even though this routine is identical to the templated copy constructor, it must be declared and implemented separately. Otherwise the compiler might create its own (incorrect) copy constructor automatically.

Parameters
valuethe polynomial to clone.

§ Polynomial() [4/5]

template<typename T >
template<typename U >
regina::Polynomial< T >::Polynomial ( const Polynomial< U > &  value)
inline

Creates a new copy of the given polynomial.

Precondition
Objects of type T can be assigned values of type U.
Parameters
valuethe polynomial to clone.

§ Polynomial() [5/5]

template<typename T >
template<typename iterator >
regina::Polynomial< T >::Polynomial ( iterator  begin,
iterator  end 
)
inline

Creates a new polynomial from the given sequence of coefficients.

The coefficients should appear in order from the constant coefficient to the leading coefficient.

There is no problem if the leading coefficient (i.e., the last coefficient in the sequence) is zero. An empty sequence will be treated as the zero polynomial.

Precondition
Objects of type T can be assigned values from dereferenced iterators of type iterator.
Python:
Instead of a pair of iterators, this routine takes a python list of coefficients.
Parameters
beginthe beginning of the sequence of coefficients.
enda past-the-end iterator indicating the end of the sequence of coefficients.

§ ~Polynomial()

template<typename T >
regina::Polynomial< T >::~Polynomial ( )
inline

Destroys this polynomial.

Member Function Documentation

§ degree()

template<typename T >
size_t regina::Polynomial< T >::degree ( ) const
inline

Returns the degree of this polynomial.

This is the largest exponent with a non-zero coefficient.

For the purposes of this class, the zero polynomial is considered to have degree zero.

Returns
the degree of this polynomial.

§ detail()

std::string regina::Output< Polynomial< T > , supportsUtf8 >::detail ( ) const
inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns
a detailed text representation of this object.

§ divisionAlg()

template<typename T >
void regina::Polynomial< T >::divisionAlg ( const Polynomial< T > &  divisor,
Polynomial< T > &  quotient,
Polynomial< T > &  remainder 
) const

Divides this by the given divisor, and extracts both the quotient and the remainder.

More precisely: suppose there exist polynomials q and r with coefficients of type T for which this = q.divisor + r, and where r has smaller degree than divisor. Then this routine sets the given polynomial quotient to q, and sets the given polynomial remainder to r.

If you do not need the remainder (e.g., if you know in advance that divisor divides into this polynomial exactly), then you can use the division operator /= instead, which will be a little faster.

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.

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

Precondition
The given divisor is not the zero polynomial.
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.
Neither quotient nor remainder is a reference to this polynomial.
Python:
The arguments quotient and remainder are missing; instead these are passed back through the return value of the function. Specifically, this function returns a (quotient, remainder) pair.
Parameters
divisorthe polynomial to divide by this.
quotienta polynomial whose contents will be destroyed and replaced with the quotient q, as described above.
remaindera polynomial whose contents will be destroyed and replaced with the remainder r, as described above.

§ gcdWithCoeffs()

template<typename T >
template<typename U >
void regina::Polynomial< T >::gcdWithCoeffs ( const Polynomial< U > &  other,
Polynomial< T > &  gcd,
Polynomial< T > &  u,
Polynomial< T > &  v 
) const

Calculates the greatest common divisor of this and the given polynomial, and finds a linear combination of these polynomials that gives this gcd.

The greatest common divisor will be a monic polynomial. The polynomials returned in u and v will satisfy u*this + v*other = gcd.

As a special case, gcd(0,0) is considered to be zero.

Precondition
The coefficient type T represents a field. In particular, Rational is supported but Integer is not.
Parameters
otherthe polynomial whose greatest common divisor with this polynomial we should compute.
gcda polynomial whose contents will be destroyed and replaced with the greatest common divisor d, as described above.
ua polynomial whose contents will be destroyed and replaced with u, as described above.
va polynomial whose contents will be destroyed and replaced with v, as described above.

§ init() [1/3]

template<typename T >
void regina::Polynomial< T >::init ( )
inline

Sets this to become the zero polynomial.

§ init() [2/3]

template<typename T >
void regina::Polynomial< T >::init ( size_t  degree)
inline

Sets this to become the polynomial x^d for the given degree d.

Parameters
degreethe new degree of this polynomial.

§ init() [3/3]

template<typename T >
template<typename iterator >
void regina::Polynomial< T >::init ( iterator  begin,
iterator  end 
)

Sets this to become the polynomial described by the given sequence of coefficients.

The coefficients should appear in order from the constant coefficient to the leading coefficient.

There is no problem if the leading coefficient (i.e., the last coefficient in the sequence) is zero. An empty sequence will be treated as the zero polynomial.

Precondition
Objects of type T can be assigned values from dereferenced iterators of type iterator.
Python:
Instead of a pair of iterators, this routine takes a python list of coefficients.
Parameters
beginthe beginning of the sequence of coefficients.
enda past-the-end iterator indicating the end of the sequence of coefficients.

§ isMonic()

template<typename T >
bool regina::Polynomial< T >::isMonic ( ) const
inline

Returns whether this polynomial is monic.

A monic polynomial is a non-zero polynomial whose leading coefficient is one.

Returns
true if and only if this is monic.

§ isZero()

template<typename T >
bool regina::Polynomial< T >::isZero ( ) const
inline

Returns whether this is the zero polynomial.

Returns
true if and only if this is the zero polynomial.

§ leading()

template<typename T >
const T & regina::Polynomial< T >::leading ( ) const
inline

Returns the leading coefficient of this polynomial.

If this is the zero polynomial, then the leading coefficient will be zero.

Returns
the leading coefficient of this polynomial.

§ operator!=()

template<typename T >
bool regina::Polynomial< T >::operator!= ( const Polynomial< T > &  rhs) const
inline

Tests whether this and the given polynomial are not equal.

Parameters
rhsthe polynomial to compare with this.
Returns
true if and only if this and the given polynomial are not equal.

§ operator*=() [1/2]

template<typename T >
Polynomial< T > & regina::Polynomial< T >::operator*= ( const T &  scalar)

Multiplies this polynomial by the given constant.

Parameters
scalarthe scalar factor to multiply by.
Returns
a reference to this polynomial.

§ operator*=() [2/2]

template<typename T >
Polynomial< T > & regina::Polynomial< T >::operator*= ( const Polynomial< T > &  other)

Multiplies this by the given polynomial.

Parameters
otherthe polynomial to multiply this by.
Returns
a reference to this polynomial.

§ operator+=()

template<typename T >
Polynomial< T > & regina::Polynomial< T >::operator+= ( const Polynomial< T > &  other)

Adds the given polynomial to this.

The given polynomial need not have the same degree as this. Note that the degree of this polynomial might change as a result of this operation.

Parameters
otherthe polynomial to add to this.
Returns
a reference to this polynomial.

§ operator-=()

template<typename T >
Polynomial< T > & regina::Polynomial< T >::operator-= ( const Polynomial< T > &  other)

Subtracts the given polynomial from this.

The given polynomial need not have the same degree as this. Note that the degree of this polynomial might change as a result of this operation.

Parameters
otherthe polynomial to subtract from this.
Returns
a reference to this polynomial.

§ operator/=() [1/2]

template<typename T >
Polynomial< T > & regina::Polynomial< T >::operator/= ( const T &  scalar)
inline

Divides this polynomial by the given constant.

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

Precondition
The argument scalar is non-zero.
Parameters
scalarthe scalar factor to divide by.
Returns
a reference to this polynomial.

§ operator/=() [2/2]

template<typename T >
Polynomial< T > & regina::Polynomial< T >::operator/= ( const Polynomial< T > &  other)

Divides this by the given polynomial.

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

This routine replaces this polynomial with the quotient q, and discards the remainder. If you need to keep the remainder also, then call 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 given polynomial is not the zero polynomial.
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
otherthe polynomial to divide this by.
Returns
a reference to this polynomial.

§ operator=() [1/2]

template<typename T >
Polynomial< T > & regina::Polynomial< T >::operator= ( const Polynomial< T > &  value)

Sets this to be a copy of the given polynomial.

This and the given polynomial need not have the same degree (but if they do not, then the degree of this polynomial will of course change).

A note to developers: although this is identical to the templated assignment operator, it must be declared and implemented separately. See the copy constructor for further details.

Parameters
valuethe polynomial to copy.
Returns
a reference to this polynomial.

§ operator=() [2/2]

template<typename T >
template<typename U >
Polynomial& regina::Polynomial< T >::operator= ( const Polynomial< U > &  value)

Sets this to be a copy of the given polynomial.

This and the given polynomial need not have the same degree (but if they do not, then the degree of this polynomial will of course change).

Parameters
valuethe polynomial to copy.
Returns
a reference to this polynomial.

§ operator==()

template<typename T >
bool regina::Polynomial< T >::operator== ( const Polynomial< T > &  rhs) const
inline

Tests whether this and the given polynomial are equal.

Parameters
rhsthe polynomial to compare with this.
Returns
true if and only if this and the given polynomial are equal.

§ operator[]()

template<typename T >
const T & regina::Polynomial< T >::operator[] ( size_t  exp) const
inline

Returns the given coefficient of this polynomial.

Parameters
expthe exponent of the term whose coefficient should be returned. This must be between 0 and degree() inclusive.
Returns
the coefficient of the given term.

§ set()

template<typename T >
void regina::Polynomial< T >::set ( size_t  exp,
const T &  value 
)

Changes the given coefficient of this polynomial.

It is fine to set the leading coefficient to zero, though note that degree() will now return a smaller value as a result.

It is also fine to set a coefficient whose exponent is larger than the current degree; this time degree() will now return a larger value (unless the given coefficient is zero). Such an operation is expensive, however, since it will require deallocating and reallocating the full list of coefficients.

Python:
This set() routine is available, but you can also set coefficients directly using syntax of the form p[exp] = value.
Parameters
expthe exponent of the term whose coefficient should be changed.
valuethe new value of this coefficient.

§ str() [1/2]

std::string regina::Output< Polynomial< T > , supportsUtf8 >::str ( ) const
inherited

Returns a short text representation of this object.

This text should be human-readable, should fit on a single line, and should not end with a newline. Where possible, it should use plain ASCII characters.

Python:
In addition to str(), this is also used as the Python "stringification" function __str__().
Returns
a short text representation of this object.

§ str() [2/2]

template<typename T >
std::string regina::Polynomial< T >::str ( const char *  variable) const
inline

Returns this polynomial as a human-readable string, using the given variable name instead of x.

Note
There is also the usual variant of str() which takes no arguments; that variant is inherited from the Output class.
Parameters
variablethe symbol to use for the variable in this polynomial. This may be null, in which case the default variable x will be used.
Returns
this polynomial as a human-readable string.

§ swap()

template<typename T >
void regina::Polynomial< T >::swap ( Polynomial< T > &  other)
inline

Swaps the contents of this and the given polynomial.

This is a fast (constant time) operation.

This and the given polynomial do not need to have the same degree.

Parameters
otherthe polynomial whose contents should be swapped with this.

§ utf8() [1/2]

std::string regina::Output< Polynomial< T > , supportsUtf8 >::utf8 ( ) const
inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should fit on a single line, and should not end with a newline. In addition, it may use unicode characters to make the output more pleasant to read. This string will be encoded in UTF-8.

Returns
a short text representation of this object.

§ utf8() [2/2]

template<typename T >
std::string regina::Polynomial< T >::utf8 ( const char *  variable) const
inline

Returns this polynomial as a human-readable string using unicode characters, using the given variable name instead of x.

This is similar to the output from str(), except that it uses unicode characters to make the output more pleasant to read. In particular, it makes use of superscript digits for exponents.

The string is encoded in UTF-8.

Note
There is also the usual variant of utf8() which takes no arguments; that variant is inherited from the Output class.
Parameters
variablethe symbol to use for the variable in this polynomial. This may be null, in which case the default variable x will be used.
Returns
this polynomial as a unicode-enabled human-readable string.

§ writeTextLong()

void regina::ShortOutput< Polynomial< T > , supportsUtf8 >::writeTextLong ( std::ostream &  out) const
inlineinherited

A default implementation for detailed output.

This routine simply calls T::writeTextShort() and appends a final newline.

Python:
Not present.
Parameters
outthe output stream to which to write.

§ writeTextShort()

template<typename T >
void regina::Polynomial< T >::writeTextShort ( std::ostream &  out,
bool  utf8 = false,
const char *  variable = 0 
) const

Writes this polynomial to the given output stream, using the given variable name instead of x.

If utf8 is passed as true then unicode superscript characters will be used for exponents; these will be encoded using UTF-8. This will make the output nicer, but will require more complex fonts to be available on the user's machine.

Python:
Not present.
Parameters
outthe output stream to which to write.
utf8true if unicode superscript characters may be used.
variablethe symbol to use for the variable in this polynomial. This may be null, in which case the default variable x will be used.

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

Copyright © 1999-2016, 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).