Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL

CGAL::Polynomial<Coeff>

Definition

An instance of the data type Polynomial represents a polynomial p = a0 + a1*x + ...ai*xi from the ring 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 for the Concepts

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.

Creation

Polynomial<Coeff> fo;
Introduces an variable initialized with 0.

Polynomial<Coeff> fo ( Polynomial x);
copy constructor.

Polynomial<Coeff> fo ( int i);
Constructor from int.

Polynomial<Coeff> fo ( Coeff x);
Constructor from type Coeff.

template <class Forward_iterator>
Polynomial<Coeff> fo ( Forward_iterator first, Forward_iterator last);
Constructor from iterator range with value type Coeff.

Types

Operations

const_iterator fo.begin () A const random access iterator pointing to the constant coefficient.
const_iterator fo.end () A const random access iterator pointing beyond the leading coefficient.
int fo.degree () The degree of the polynomial in x. The degree of the zero polynomial is 0.
NT fo.operator[] ( unsigned int i) Const access to the coefficient of xi.
NT fo.lcoeff () Const access to the leading coefficient.
std::ostream& operator<< ( std::ostream& os, poly)
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,a0, … ,ad], where d is the degree of the polynomial. In case the mode is CGAL::IO::PRETTY the format is human readable.

std::istream& operator>> ( std::istream& is, poly)
Reads poly from istream is in format POLY[d,a0, … ,ad], the output format in mode CGAL::IO::ASCII

Next: Polynomial_traits_d<Polynomial_d>
Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
CGAL Open Source Project. Release 3.5. 1 October 2009.