\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.9 - Polynomial
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Polynomial< Coeff > Class Template Reference

#include <CGAL/Polynomial.h>

Definition

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

Member Function Documentation

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

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.