Polynomial Class Reference

Polynomials of degree lower than or equal to 11. More...

#include <polynomial.h>

Public Member Functions
	Polynomial ()
	Creates a null polynomial.
	~Polynomial ()
	Empty.
	Polynomial (const double &, const double &, const double &, const double &, const double &, const double &, const double &, const double &, const double &, const double &)
	Creates a degree 9 polynomial.
	Polynomial (const double &, const double &, const double &, const double &, const double &, const double &, const double &, const double &, const double &)
	Creates a degree 8 polynomial.
	Polynomial (const double &, const double &, const double &, const double &, const double &, const double &, const double &, const double &)
	Creates a septic.
	Polynomial (const double &, const double &, const double &, const double &, const double &, const double &, const double &)
	Creates a sextic.
	Polynomial (const double &, const double &, const double &, const double &, const double &, const double &)
	Creates a quintic.
	Polynomial (const double &, const double &, const double &, const double &, const double &)
	Creates a quartic.
	Polynomial (const double &, const double &, const double &, const double &)
	Creates a cubic.
	Polynomial (const double &, const double &, const double &)
	Creates a quadric.
	Polynomial (const double &, const double &)
	Creates a linear polynomial.
	Polynomial (const double &)
	Creates a constant polynomial.
	Polynomial (const Linear &)
	Creates a polynomial given a linear.
	Polynomial (const Quadric &)
	Creates a polynomial given a quadric.
	Polynomial (const Cubic &)
	Creates a polynomial given a cubic.
	Polynomial (const Quartic &)
	Creates a polynomial given a quartic.
	Polynomial (const Quintic &)
	Creates a polynomial given a quintic.
	Polynomial (const Sextic &)
	Creates a polynomial given a sextic.
	Polynomial (const Septic &)
	Creates a polynomial given a septic.
	Polynomial (const Octic &)
	Creates a polynomial given an octic.
	Polynomial (const Nonic &)
	Creates a polynomial given a nonic.
constexpr double &	operator[] (int)
	Access to the coefficients of the polynomial.
constexpr double	operator[] (int) const
	Overloaded.
Polynomial	operator+ () const
	Overloaded.
Polynomial	operator- () const
	Unary.
Polynomial &	operator+= (const Polynomial &)
	Destructive sum of two polynomials.
Polynomial &	operator-= (const Polynomial &)
	Destructive difference of two polynomials.
Polynomial &	operator*= (const Polynomial &)
	Overloaded.
Polynomial &	operator*= (const double &)
	Scale a polynomial by a double value.
Polynomial &	operator/= (const double &)
	Scale a polynomial by a double value.
Polynomial	Prime () const
	Compute the derivative of the polynomial.
Polynomial	Integral (const double &=0.0) const
	Compute the antiderivative of the polynomial, with a given constant term.
Polynomial	Compose (const Polynomial &) const
	Compose the polynomial by the argument polynomial.
Polynomial	Reversed () const
	Reverse the terms of the polynomial.
double	operator() (const double &) const
	Evaluates the polynomial.
int	Solve (double *) const
	Search the roots of a polynomial equation.
int	SturmSolve (double *) const
	Search the roots of a polynomial equation using Sturm sequences.
int	Solve (double *, const double &, const double &) const
	Search the roots of a polynomial equation over a given interval.
int	Degree () const
	Returns the degree of the polynomial.
bool	IsNull () const
	Returns if the polynomials as 0 at every coefficient.
void	Check ()
	Decrease the stored degree n while the leading coefficient is zero. Call after any operation that may cancel the dominant term.
void	Range (double &, double &, const double &=0.0, const double &=1.0) const
	This function computes the range of values taken by a polynomial over a given interval.
int	Bissection (double, double, double &, const double &) const
	Find a root of the polynomial in an interval using the regula falsi method.

Static Public Member Functions
static Polynomial	Compose (const Quartic &, const Quadric &)
	Compose the quartic by a quadric.

Static Public Attributes
static const Polynomial	Null
	The zero polynomial (degree 0, all coefficients zero).

Protected Attributes
int	n = 0
	The degree of the polynomial.
double	c [MaxDegree+1] = { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 }
	Array of coefficients.

Static Protected Attributes
static constexpr int	MaxDegree = 11
	Maximum degree.

Friends
Polynomial	operator+ (const Polynomial &u, const Polynomial &v)
	Overloaded.
Polynomial	operator- (const Polynomial &u, const Polynomial &v)
	Overloaded.
Polynomial	operator* (const Polynomial &u, const Polynomial &v)
	Multiply two polynomials.
Polynomial	operator* (const Polynomial &u, const double &e)
	Multiply a polynomial by a scalar value.
Polynomial	operator* (const double &a, const Polynomial &p)
	Overloaded.
Polynomial	operator/ (const Polynomial &p, const double &a)
	Overloaded.
std::ostream &	operator<< (std::ostream &s, const Polynomial &p)
	Overloaded output-stream operator.

Detailed Description

Polynomials of degree lower than or equal to 11.

This class is defined as a fixed size data-structure to speed-up and facilitate memory management. It is more memory and computationally efficient to use Linear, Quadric, Cubic, and Quartic classes whenever possible.

When using constructors, the coefficients are given in descending order, i.e. start from the highest degree coefficient to the lowest degree.

Example of how to code the quartic polynomial \( 3x^4 - x + 1 \):

Polynomial p(3.0,0.0,0.0,-1.0,1.0);

Warning

The degree n is set to match the number of constructor arguments and is not verified: if the leading coefficient is zero the stored degree will be higher than the actual degree. Call Check() after construction whenever the leading coefficient may be zero.

Polynomial p(0.0, 2.0, -1.0, 1.0); // 4 args → n=3, but leading coeff is 0
p.Check();                          // reduces to n=2 : 2x^2 - x + 1

See also

Septic, Sextic, Quintic, Quartic, Cubic, Quadric, Linear.

Constructor & Destructor Documentation

Polynomial() [1/9]

Polynomial::Polynomial ( const Linear & p )

inline

Creates a polynomial given a linear.

Parameters

p	Linear polynomial.

Polynomial() [2/9]

Polynomial::Polynomial ( const Quadric & p )

inline

Creates a polynomial given a quadric.

Parameters

p	Quadric polynomial.

Polynomial() [3/9]

Polynomial::Polynomial ( const Cubic & p )

inline

Creates a polynomial given a cubic.

Parameters

p	Cubic polynomial.

Polynomial() [4/9]

Polynomial::Polynomial ( const Quartic & p )

inline

Creates a polynomial given a quartic.

Parameters

p	Quartic polynomial.

Polynomial() [5/9]

Polynomial::Polynomial ( const Quintic & p )

inline

Creates a polynomial given a quintic.

Parameters

p	Quintic polynomial.

Polynomial() [6/9]

Polynomial::Polynomial ( const Sextic & p )

inline

Creates a polynomial given a sextic.

Parameters

p	Sextic polynomial.

Polynomial() [7/9]

Polynomial::Polynomial ( const Septic & p )

inline

Creates a polynomial given a septic.

Parameters

p	Septic polynomial.

Polynomial() [8/9]

Polynomial::Polynomial ( const Octic & p )

inline

Creates a polynomial given an octic.

Parameters

p	Octic polynomial.

Polynomial() [9/9]

Polynomial::Polynomial ( const Nonic & p )

inline

Creates a polynomial given a nonic.

Parameters

p	Nonic polynomial.

Member Function Documentation

Bissection()

int Polynomial::Bissection	(	double	a,
		double	b,
		double &	val,
		const double &	epsilon ) const

Find a root of the polynomial in an interval using the regula falsi method.

The next estimate is the root of the line through the end points of the interval, and the function value at the end point which is kept for two successive iterations is divided by two (Illinois variant), which avoids the slow convergence of the plain method. The iteration stops after 50 steps, when the relative error on the value is lower than the precision, or when the interval is smaller than the precision. The values of the polynomial at the two ends of the interval should have opposite signs.

Parameters

a,b	Interval.
val	Returned root.
epsilon	Precision, which is not the static member Polynomial::epsilon.

Returns

1 if a root has been found, and 0 otherwise.

Check()

void Polynomial::Check

(

)

Decrease the stored degree n while the leading coefficient is zero. Call after any operation that may cancel the dominant term.

Check the degree of the polynomial.

The function decreases the degree if higher coefficients are null.

Compose() [1/2]

Polynomial Polynomial::Compose

(

const Polynomial &

v

)

const

Compose the polynomial by the argument polynomial.

Parameters

v	Argument polynomial.

Compose() [2/2]

Polynomial Polynomial::Compose ( const Quartic & p, const Quadric & q )

static

Compose the quartic by a quadric.

This function computes p ( q(x) ), where p denotes the quartic and q the quadric.

Parameters

p	The quartic.
q	The quadric.

Integral()

Polynomial Polynomial::Integral

(

const double &

a0 = 0.0

)

const

Compute the antiderivative of the polynomial, with a given constant term.

The degree of the antiderivative is the degree of the polynomial plus one, which should not exceed the maximum degree (MaxDegree, which is 11): the degree of the polynomial should therefore be strictly less than 11, i.e., at most 10. If the degree of the polynomial is 11, the term of degree 12 of the antiderivative cannot be stored: as for the product of two polynomials, this term is dropped and the result is truncated to degree 11.

Parameters

a0	Constant term of the antiderivative.

Returns

The antiderivative, which is the polynomial of null value at the origin plus a0.

operator()()

double Polynomial::operator()

(

const double &

x

)

const

Evaluates the polynomial.

Parameters

x	Parameter.

Range()

void Polynomial::Range	(	double &	x,
		double &	y,
		const double &	a = 0.0,
		const double &	b = 1.0 ) const

This function computes the range of values taken by a polynomial over a given interval.

Computes the roots of the first derivative, and evaluates the polynomial at the roots if they are within the interval bounds.

Parameters

a,b	Interval.
x,y	Returned range.

Solve() [1/2]

int Polynomial::Solve

(

double *

roots

)

const

Search the roots of a polynomial equation.

This function calls other root solving functions, invoking Quartic::Solve(), Cubic::Solve() or Quadric::Solve() as appropriate if the degree is lower or equal than four (which means that closed form expressions of the roots exist).

Otherwise, rely on a numeric root finder to isolate roots and converge using the Sturm sequences. In that case only the roots in the interval [-1e7,1e7] are found.

The roots are not guaranteed to be sorted for a degree lower or equal than four.

Parameters

roots

Array for storing the roots.

Returns

The number of roots.

Solve() [2/2]

int Polynomial::Solve	(	double *	roots,
		const double &	a,
		const double &	b ) const

Search the roots of a polynomial equation over a given interval.

Parameters

roots	The array of roots.
a,b	The search interval.

Returns

The number of roots.

SturmSolve()

int Polynomial::SturmSolve

(

double *

roots

)

const

Search the roots of a polynomial equation using Sturm sequences.

Only roots in \( [-10^7, 10^7] \) are found; roots outside this range are silently ignored.

Parameters

roots

Array for storing the roots.

Returns

The number of roots found in \( [-10^7, 10^7] \).

Friends And Related Symbol Documentation

operator*

Polynomial operator* ( const Polynomial & u, const Polynomial & v )

friend

Multiply two polynomials.

The result is truncated to degree MaxDegree when the exact degree of the product exceeds MaxDegree. Terms of degree greater than MaxDegree are silently dropped.

operator<<

std::ostream & operator<< ( std::ostream & s, const Polynomial & p )

friend

Overloaded output-stream operator.

Parameters

s	Stream.
p	The polynomial.

Member Data Documentation

Null

const Polynomial Polynomial::Null

static

The zero polynomial (degree 0, all coefficients zero).

Set the null polynomial member constant.