CGAL 6.1 - Polynomial

Loading...
Searching...
No Matches
List of all members | Related Functions
CGAL::Polynomial< Coeff > Class Template Reference
Reference Manual » Classes

`#include <CGAL/Polynomial.h>`

## Definition

template<typename Coeff>
class CGAL::Polynomial< Coeff >

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.

Is model of
  `Polynomial_d`
  `Assignable`
  `CopyConstructible`
  `DefaultConstructible`
  `EqualityComparable`
  `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`.
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\).
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.

## Member Function Documentation

## ◆ degree()

template<typename Coeff >

int CGAL::Polynomial< Coeff >::degree | ( |  | ) | const

The degree of the polynomial in \( x\).

The degree of the zero polynomial is 0.

## Friends And Related Function Documentation

## ◆ operator<<()

template<typename Coeff >

std::ostream & operator<< | ( | std::ostream & | os,
|  | const Polynomial< Coeff > & | poly
| ) |  |
| 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.