Regina 7.0 Calculation Engine
|
Represents a single-variable polynomial with coefficients of type T. More...
#include <maths/polynomial.h>
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... | |
void | divisionAlg (const Polynomial &divisor, Polynomial "ient, 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 > &) |
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:
x = int
and tests of the form x == int
and x < int
;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.
using regina::Polynomial< T >::Coefficient = T |
The type of each coefficient of the polynomial.
|
inline |
Creates the zero polynomial.
|
inlineexplicit |
Creates the polynomial x^d
for the given degree d.
degree | the degree of the new polynomial. |
|
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.
value | the polynomial to clone. |
|
inline |
Creates a new copy of the given polynomial.
This constructor induces a deep copy of value.
value | the polynomial to clone. |
|
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.
value | the polynomial to move. |
|
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.
begin | the beginning of the sequence of coefficients. |
end | a past-the-end iterator indicating the end of the sequence of 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.
coefficients | the full sequence of coefficients. |
|
inline |
Destroys this polynomial.
|
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.
|
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.
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.
divisor | the polynomial to divide this by. |
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.
divisor | the polynomial to divide this by. |
quotient | a polynomial whose contents will be destroyed and replaced with the quotient. |
remainder | a polynomial whose contents will be destroyed and replaced with the remainder. |
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.
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. |
|
inline |
Sets this to become the zero polynomial.
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.
begin | the beginning of the sequence of coefficients. |
end | a past-the-end iterator indicating the end of the sequence of coefficients. |
|
inline |
Sets this to become the polynomial x^d
for the given degree d.
degree | the new degree of this polynomial. |
|
inline |
Returns whether this polynomial is monic.
A monic polynomial is a non-zero polynomial whose leading coefficient is one.
true
if and only if this is monic.
|
inline |
Returns whether this is the zero polynomial.
true
if and only if this is the zero polynomial.
|
inline |
Returns the leading coefficient of this polynomial.
If this is the zero polynomial, then the leading coefficient will be zero.
|
inline |
Negates this polynomial.
This field element is changed directly.
|
inline |
Tests whether this and the given polynomial are not equal.
rhs | the polynomial to compare with this. |
true
if and only if this and the given polynomial are not equal. Polynomial< T > & regina::Polynomial< T >::operator*= | ( | const Polynomial< T > & | other | ) |
Multiplies this by the given polynomial.
other | the polynomial to multiply this by. |
Polynomial< T > & regina::Polynomial< T >::operator*= | ( | const T & | scalar | ) |
Multiplies this polynomial by the given constant.
scalar | the scalar factor to multiply by. |
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.
+
operator instead, which is better able to avoid this deep copy where possible.other | the polynomial to add to this. |
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.
other | the polynomial to subtract from this. |
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.
other | the polynomial to divide this by. |
|
inline |
Divides this polynomial by the given constant.
This uses the division operator /= for the coefficient type T.
scalar | the scalar factor to divide by. |
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.
value | the polynomial to copy. |
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.
value | the polynomial to copy. |
|
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.
value | the polynomial to move. |
|
inline |
Tests whether this and the given polynomial are equal.
rhs | the polynomial to compare with this. |
true
if and only if this and the given polynomial are equal.
|
inline |
Returns the given coefficient of this polynomial.
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()
.exp | the exponent of the term whose coefficient should be returned. This must be between 0 and degree() inclusive. |
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.
p[exp] = value
.exp | the exponent of the term whose coefficient should be changed. |
value | the new value of this coefficient. |
|
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.
str()
will use precisely this function, and for most classes the Python repr()
function will incorporate this into its output.
|
inline |
Returns this polynomial as a human-readable string, using the given variable name instead of x
.
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. |
|
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.
other | the polynomial whose contents should be swapped with this. |
|
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.
|
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.
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. |
|
inlineinherited |
A default implementation for detailed output.
This routine simply calls T::writeTextShort() and appends a final newline.
out | the output stream to which to write. |
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.
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. |