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

#include <maths/polynomial.h>

Inheritance diagram for regina::Polynomial< T >:

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

Polynomial &	operator= (const Polynomial &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...

Polynomial &	operator= (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...

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 &other)
	Adds the given polynomial to this. More...

Polynomial &	operator-= (const Polynomial &other)
	Subtracts the given polynomial from this. More...

Polynomial &	operator*= (const Polynomial &other)
	Multiplies this by the given polynomial. More...

Polynomial &	operator/= (const Polynomial &other)
	Divides this by the given polynomial. More...

std::pair< Polynomial, Polynomial >	divisionAlg (const Polynomial &divisor) const
	Divides this by the given divisor, and returns 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...

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:

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

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

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

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

Python: Not present. Python only supports polynomials with one type of coefficient (the case where T is Rational). Therefore Python users can use the non-templated copy constructor.

Parameters

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

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

begin	the beginning of the sequence of coefficients.
end	a 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 present. Instead, use the Python constructor that takes a list of coefficients (which need not be constant).

Parameters

coefficients the 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()

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 >

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

divisor the polynomial to divide this by.

Returns: a pair holding the quotient and remainder, 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 >

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

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

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

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

Multiplies this by the given polynomial.

Parameters

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

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

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

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

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

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

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

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.

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++: For C++ users, this operator is read-only. To set coefficients, you must use the separate routine set().

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

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 )

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

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

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

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

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 = `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

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

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ Coefficient

Constructor & Destructor Documentation

◆ Polynomial() [1/7]

◆ Polynomial() [2/7]

◆ Polynomial() [3/7]

◆ Polynomial() [4/7]

◆ Polynomial() [5/7]

◆ Polynomial() [6/7]

◆ Polynomial() [7/7]

◆ ~Polynomial()

Member Function Documentation

◆ degree()

◆ detail()

◆ divisionAlg()

◆ gcdWithCoeffs()

◆ init() [1/3]

◆ init() [2/3]

◆ init() [3/3]

◆ isMonic()

◆ isZero()

◆ leading()

◆ negate()

◆ operator!=()

◆ operator*=() [1/2]

◆ operator*=() [2/2]

◆ operator+=()

◆ operator-=()

◆ operator/=() [1/2]

◆ operator/=() [2/2]

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ operator==()

◆ operator[]()

◆ set()

◆ str() [1/2]

◆ str() [2/2]

◆ swap()

◆ utf8() [1/2]

◆ utf8() [2/2]

◆ writeTextLong()

◆ writeTextShort()