|
CGAL 4.12 - Polynomial
|
#include <CGAL/Polynomial.h>
An instance of the data type Polynomial represents a polynomial \( p = a_0 + a_1*x + ...a_i*x^i\) from the ring \( \mathrm{Coeff}[x]\).
Coeff can itself be an instance of Polynomial, yielding a form of multivariate polynomials.
The template argument Coeff must be at least a model of IntegralDomainWithoutDivision. For all operations naturally involving division, an IntegralDomain is required. Polynomial offers a full set of algebraic operators, i.e. binary +, -, *, / as well as +=, -=, *=, /=; not only for polynomials but also for a polynomial and a number of the coefficient type. (The / operator must only be used for integral divisions, i.e. those with remainder zero.) The operations are implemented naively: + and - need a number of Coeff operations which is linear in the degree while * is quadratic. Unary + and - and (in)equality ==, != are provided as well.
Polynomial is a model of LessThanComparable if Coeff is a model of LessThanComparable. In this case Polynomial provides comparison operators <, >, <=, >=, where the comparison amounts to lexicographic comparison of the coefficient sequence, with the coefficient of the highest power taking precedence over those of lower powers.
Polynomial is a model of Fraction if Coeff is a model of Fraction. In this case Polynomial may be decomposed into a (scalar) denominator and a compound numerator with a simpler coefficient type. Often operations can be performed faster on these denominator-free multiples.
Polynomial is a model of Modularizable if Coeff is a model of Modularizable, where the homomorphic map on the polynomials is simply defined as the canonical extension of the homomorphic map which is defined on the coefficient type.
Implementation
Inexact and limited-precision types can be used as coefficients, but at the user's risk. The algorithms implemented were written with exact number types in mind.
This data type is implemented as a handle type with value semantics using CGAL::Handle_with_policy, where HandlePolicy is Handle_policy_no_union. An important invariant to be preserved by all methods is that the coefficient sequence does not contain leading zero coefficients (where leading means at the high-degree end), with the exception that the zero polynomial is represented by a single zero coefficient.
ImplicitInteroperable with int
ImplicitInteroperable with Coeff
Fraction if Coeff is model of Fraction
LessThanComparable if Coeff is model of LessThanComparable
Modularizable if Coeff is model of Modularizable
Related Functions | |
(Note that these are not member functions.) | |
| std::ostream & | operator<< (std::ostream &os, const Polynomial< Coeff > &poly) |
Writes poly to ostream os. More... | |
| std::istream & | operator>> (std::istream &is, const Polynomial< Coeff > &poly) |
Reads poly from istream is in format \( P[d(0,a_0)(1,a_1)\dots(d,a_d)]\), the output format in mode CGAL::IO::ASCII. | |
Creation | |
| Polynomial () | |
| Introduces an variable initialized with 0. | |
| Polynomial (const Polynomial &x) | |
| copy constructor. | |
| Polynomial (const int &i) | |
| Constructor from int. | |
| Polynomial (const Coeff &x) | |
| Constructor from type Coeff. | |
| template<class Forward_iterator > | |
| Polynomial (Forward_iterator first, Forward_iterator last) | |
| Constructor from iterator range with value type Coeff. | |
Operations | |
| const_iterator | begin () const |
| A const random access iterator pointing to the constant coefficient. | |
| const_iterator | end () const |
| A const random access iterator pointing beyond the leading coefficient. | |
| int | degree () const |
| The degree of the polynomial in \( x\). More... | |
| const NT & | operator[] (unsigned int i) const |
| Const access to the coefficient of \( x^i\). | |
| const NT & | lcoeff () const |
| Const access to the leading coefficient. | |
| int CGAL::Polynomial< Coeff >::degree | ( | ) | const |
The degree of the polynomial in \( x\).
The degree of the zero polynomial is 0.
|
related |
Writes poly to ostream os.
The format depends on the CGAL::IO::MODE of os. In case the mode is CGAL::IO::ASCII the format is \( P[d(0,a_0)(1,a_1)\dots(d,a_d)]\), where \( d\) is the degree of the polynomial. The format is output sensitive, that is, coefficients that are zero are not reported. In case the mode is CGAL::IO::PRETTY the format is human readable.
1.8.13