regina::Polynomial< T > Class Template Reference
Mathematical Support

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

`#include <maths/polynomial.h>`

Inheritance diagram for regina::Polynomial< T >:

## 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...
Polynomial & | operator= (const Polynomial< T > &value)
| Sets this to be a copy of the given polynomial. More...
template<typename U >
Polynomial & | operator= (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...
Polynomial & | operator*= (const T &scalar)
| Multiplies this polynomial by the given constant. More...
Polynomial & | operator/= (const T &scalar)
| Divides this polynomial by the given constant. More...
Polynomial & | operator+= (const Polynomial< T > &other)
| Adds the given polynomial to this. More...
Polynomial & | operator-= (const Polynomial< T > &other)
| Subtracts the given polynomial from this. More...
Polynomial & | operator*= (const Polynomial< T > &other)
| Multiplies this by the given polynomial. More...
Polynomial & | operator/= (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:

- support basic arithmetic operations;
- support assignments of the form `x = int` and tests of the form `x == int` and `x < int`;
- have a default constructor that assigns an explicit value of zero.

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

inline explicit

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

Parameters

  degree | the 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

  value | the 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

  value | the 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

  begin | the beginning of the sequence of coefficients.
  end | a 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

  divisor | the polynomial to divide by this.
  quotient | a polynomial whose contents will be destroyed and replaced with the quotient q, as described above.
  remainder | a 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

  other | the polynomial whose greatest common divisor with this polynomial we should compute.
  gcd | a polynomial whose contents will be destroyed and replaced with the greatest common divisor d, as described above.
  u | a polynomial whose contents will be destroyed and replaced with u, as described above.
  v | a 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

  degree | the 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

  begin | the beginning of the sequence of coefficients.
  end | a 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

  rhs | the 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

  scalar | the 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

  other | the 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

  other | the 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

  other | the 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

  scalar | the 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

  other | the 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

  value | the 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

  value | the 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

  rhs | the 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

  exp | the 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

  exp | the exponent of the term whose coefficient should be changed.
  value | the 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

  variable | the 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

  other | the 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

  variable | the 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

inline inherited

A default implementation for detailed output.

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

Python:
  Not present.

Parameters

  out | the 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

  out | the output stream to which to write.
  utf8 | `true` if unicode superscript characters may be used.
  variable | the 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:

- maths/polynomial.h

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