Regina 7.0 Calculation Engine
Public Types | Public Member Functions | Friends | 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< T, supportsUtf8 >

Public Types

using Coefficient = T
 The type of each coefficient of the polynomial. More...
 

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 &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...
 
 Polynomial (Polynomial &&value) noexcept
 Moves the contents of the given polynomial to this new polynomial. More...
 
template<typename iterator >
 Polynomial (iterator begin, iterator end)
 Creates a new polynomial from the given sequence of coefficients. More...
 
 Polynomial (std::initializer_list< T > coefficients)
 Creates a new polynomial from a hard-coded 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 &rhs) const
 Tests whether this and the given polynomial are equal. More...
 
bool operator!= (const Polynomial &rhs) const
 Tests whether this and the given polynomial are not equal. More...
 
Polynomialoperator= (const Polynomial &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...
 
Polynomialoperator= (Polynomial &&value) noexcept
 Moves the contents of the given polynomial to this polynomial. More...
 
void swap (Polynomial &other) noexcept
 Swaps the contents of this and the given polynomial. More...
 
void negate ()
 Negates this 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 &other)
 Adds the given polynomial to this. More...
 
Polynomialoperator-= (const Polynomial &other)
 Subtracts the given polynomial from this. More...
 
Polynomialoperator*= (const Polynomial &other)
 Multiplies this by the given polynomial. More...
 
Polynomialoperator/= (const Polynomial &other)
 Divides this by the given polynomial. More...
 
std::pair< Polynomial, PolynomialdivisionAlg (const Polynomial &divisor) const
 Divides this by the given divisor, and returns both the quotient and the remainder. More...
 
void divisionAlg (const Polynomial &divisor, Polynomial &quotient, Polynomial &remainder) const
 Deprecated function that 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 &gcd, Polynomial &u, Polynomial &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=nullptr) 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...
 

Friends

template<typename U >
Polynomial< U > operator+ (const Polynomial< U > &, const Polynomial< U > &)
 
template<typename U >
Polynomial< U > operator- (const Polynomial< U > &, const Polynomial< U > &)
 
template<typename U >
Polynomial< U > operator- (const Polynomial< U > &, Polynomial< U > &&)
 
template<typename U >
Polynomial< U > operator- (Polynomial< U > &&, Polynomial< U > &&)
 
template<typename U >
Polynomial< U > operator* (const Polynomial< U > &, const Polynomial< U > &)
 

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

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

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

Member Typedef Documentation

◆ Coefficient

template<typename T >
using regina::Polynomial< T >::Coefficient = T

The type of each coefficient of the polynomial.

Constructor & Destructor Documentation

◆ Polynomial() [1/7]

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

Creates the zero polynomial.

◆ Polynomial() [2/7]

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/7]

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

Creates a new copy of the given polynomial.

This constructor induces a deep copy of value.

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/7]

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

Creates a new copy of the given polynomial.

This constructor induces a deep copy of value.

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

◆ Polynomial() [5/7]

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

Moves the contents of the given polynomial to this new polynomial.

This is a fast (constant time) operation.

The polynomial that was passed (value) will no longer be usable.

Parameters
valuethe polynomial to move.

◆ Polynomial() [6/7]

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 be given 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.

This constructor induces a deep copy of the given range.

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() [7/7]

template<typename T >
regina::Polynomial< T >::Polynomial ( std::initializer_list< T >  coefficients)
inline

Creates a new polynomial from a hard-coded sequence of coefficients.

The coefficients should be given 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.

Python
Not available, but there is a Python constructor that takes a list of coefficients (which need not be constant).
Parameters
coefficientsthe full 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
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()

template<class T , bool supportsUtf8 = false>
std::string regina::Output< 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() [1/2]

template<typename T >
std::pair< Polynomial< T >, Polynomial< T > > regina::Polynomial< T >::divisionAlg ( const Polynomial< T > &  divisor) const

Divides this by the given divisor, and returns 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 returns the pair (q, r); that is, the quotient and the remainder.

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.
Parameters
divisorthe polynomial to divide this by.
Returns
a pair holding the quotient and remainder, as described above.

◆ divisionAlg() [2/2]

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

Deprecated function that divides this by the given divisor, and extracts both the quotient and the remainder.

This function performs the same task as the one-argument variant of divisionAlg(); however, instead of send the quotient and remainder back through the return value, it sends them back via the given polynomial references.

See the one-argument variant of divisionAlg() for further details.

Deprecated:
Use the one-argument variant of divisionAlg() instead.
Precondition
Neither quotient nor remainder is a reference to this polynomial.
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.
Python
Not present; instead you can use the one-argument variant of divisionAlg().
Parameters
divisorthe polynomial to divide this by.
quotienta polynomial whose contents will be destroyed and replaced with the quotient.
remaindera polynomial whose contents will be destroyed and replaced with the remainder.

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

This routine induces a deep copy of the given range.

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.

◆ init() [3/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.

◆ isMonic()

template<typename T >
bool regina::Polynomial< T >::isMonic
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
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
inline

Returns the leading coefficient of this polynomial.

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

Python
This routine returns by value, not by reference, since constness is important here and Python cannot enforce it otherwise.
Returns
the leading coefficient of this polynomial.

◆ negate()

template<typename T >
void regina::Polynomial< T >::negate
inline

Negates this polynomial.

This field element is changed directly.

◆ 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 Polynomial< T > &  other)

Multiplies this by the given polynomial.

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

◆ operator*=() [2/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+=()

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.

Warning
This routine may trigger a deep copy (currently this happens when other has higher degree than this). Consider using the binary + operator instead, which is better able to avoid this deep copy where possible.
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 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/=() [2/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=() [1/3]

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

This operator induces a deep copy of the given polynomial.

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/3]

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

This operator induces a deep copy of the given polynomial.

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

◆ operator=() [3/3]

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

Moves the contents of the given polynomial to this polynomial.

This is a fast (constant time) operation.

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

The polynomial that was passed (value) will no longer be usable.

Parameters
valuethe polynomial to move.
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.

Python
Python users can also use this operator to set cofficients; that is, you can write poly[exp] = value. However, when getting a coefficient this operator will return by value (to enforce constness), which means for example you cannot write something like poly[exp].negate().
C++
C++ users must always set coefficients using the separate routine set(), since this square bracket operator is const.
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]

template<class T , bool supportsUtf8 = false>
std::string regina::Output< T, supportsUtf8 >::str ( ) const
inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python str() and repr() functions.

Python
The Python "stringification" function str() will use precisely this function, and for most classes the Python repr() function will incorporate this into its output.
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)
inlinenoexcept

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]

template<class T , bool supportsUtf8 = false>
std::string regina::Output< 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 not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned 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; instead you can call detail() from the subclass T, which returns this output as a string.
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 = nullptr 
) 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; use str() or utf8() instead.
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-2021, 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).