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