CUGL 2.3 Cornell University Game Library
Searching...
No Matches
cugl::Polynomial Class Reference

`#include <CUPolynomial.h>`

Inheritance diagram for cugl::Polynomial:

## Public Member Functions

Polynomial ()

Polynomial (long degree)

Polynomial (long degree, float value)

Polynomial (const Polynomial &poly)

Polynomial (Polynomial &&poly)

Polynomial (const_iterator first, const_iterator last)

Polynomial (float *array, unsigned int size, unsigned int offset=0)

virtual ~Polynomial ()

long degree () const

bool isConstant () const

bool isValid () const

bool isZero () const

Polynomial derivative () const

float evaluate (float value) const

void validate ()

float normalize ()

bool roots (vector< float > &roots, float epsilon=CU_MATH_EPSILON) const

Polynomialoperator= (const Polynomial &poly)

Polynomialoperator= (Polynomial &&poly)

Polynomialoperator= (float value)

Polynomialset (float *array, int size)

Polynomialset (float value)

bool operator< (const Polynomial &p) const

bool operator< (float value) const

bool operator<= (const Polynomial &p) const

bool operator<= (float value) const

bool operator> (const Polynomial &p) const

bool operator> (float value) const

bool operator>= (const Polynomial &p) const

bool operator>= (float value) const

bool operator== (float value) const

bool operator!= (float value) const

Polynomialoperator+= (const Polynomial &other)

Polynomialoperator-= (const Polynomial &other)

Polynomialoperator*= (const Polynomial &other)

Polynomialoperator/= (const Polynomial &other)

Polynomialoperator%= (const Polynomial &other)

Polynomial operator+ (const Polynomial &other) const

Polynomial operator- (const Polynomial &other) const

Polynomial operator* (const Polynomial &other) const

Polynomial operator/ (const Polynomial &other) const

Polynomial operator% (const Polynomial &other) const

Polynomialoperator+= (float value)

Polynomialoperator-= (float value)

Polynomialoperator*= (float value)

Polynomialoperator/= (float value)

Polynomialoperator%= (float value)

Polynomial operator+ (float value) const

Polynomial operator- (float value) const

Polynomial operator* (float value) const

Polynomial operator/ (float value) const

Polynomial operator% (float value) const

Polynomial operator- () const

std::string toString (bool format=true) const

operator std::string () const

## Static Public Attributes

static const Polynomial ZERO

static const Polynomial ONE

## Protected Member Functions

Polynomialsynthetic_divide (const Polynomial &other)

bool bairstow_factor (Polynomial &quad, Polynomial &result, float epsilon) const

void solve_quadratic (vector< float > &roots) const

## Static Protected Member Functions

static Polynomial iterative_multiply (const Polynomial &a, const Polynomial &b)

static Polynomial recursive_multiply (const Polynomial &a, const Polynomial &b)

## Friends

Polynomial operator+ (float left, const Polynomial &right)

Polynomial operator- (float left, const Polynomial &right)

Polynomial operator* (float left, const Polynomial &right)

Polynomial operator/ (float left, const Polynomial &right)

Polynomial operator% (float left, const Polynomial &right)

bool operator< (float left, const Polynomial &right)

bool operator<= (float left, const Polynomial &right)

bool operator> (float left, const Polynomial &right)

bool operator>= (float left, const Polynomial &right)

## Detailed Description

This class represents a polynomial.

A polynomial is a vector of floats. This vector represents the polynomial from highest degree to constant. For example, the vector [1, -1, 2, 0, -3] is equivalent to

1*x^4 - 1*x^3 + 2*x^2 + 0*x - 3

Hence the degree of the polynomial is one less than the length of the list.

We make all of the vector methods still available. However, note that there is some danger in using the vector methods carelessly. In order to be well-formed, a polynomial vector must have at least one element. Furthermore, if it has more than one element, the first element must be non-zero. If this is not the case, there is no guarantee that any of the polynomial methods (such as root finding) will work properly.

To avoid this problem, we have provided the isValid() and validate() methods. If you believe there is some possibility of the polynomial being corrupted, you should use these.

## ◆ Polynomial() [1/7]

 cugl::Polynomial::Polynomial ( )
inline

Creates a zero polynomial

## ◆ Polynomial() [2/7]

 cugl::Polynomial::Polynomial ( long degree )
inline

Creates the polynomial x^d where is the degree.

The first coefficient is 1. All other coefficients are 0.

Parameters
 degree the degree of the polynomial

## ◆ Polynomial() [3/7]

 cugl::Polynomial::Polynomial ( long degree, float value )
inline

Creates the polynomial x^d where is the degree.

The value is the coefficient of all terms. This has a chance of making an invalid polynomial (e.g. if value is 0). However, this constructor does not enforce validity. Hence it is a way to create a 0 polynomial with multiple terms.

Parameters
 degree the degree of the polynomial value the coefficient of each term

## ◆ Polynomial() [4/7]

 cugl::Polynomial::Polynomial ( const Polynomial & poly )
inline

Creates a copy of the given polynomial.

Parameters
 poly the polynomial to copy

## ◆ Polynomial() [5/7]

 cugl::Polynomial::Polynomial ( Polynomial && poly )
inline

Takes then resources from the given polynomial.

Parameters
 poly the polynomial to take from

## ◆ Polynomial() [6/7]

 cugl::Polynomial::Polynomial ( const_iterator first, const_iterator last )
inline

Creates a polynomial from the given iterators.

The elements are copied in order. A valid iterator must have at least one element, and the first element cannot be 0 if there is more than one element.

This constructor is provided for fast copying from other vectors.

Parameters
 first the beginning iterator last the terminating iterator

## ◆ Polynomial() [7/7]

 cugl::Polynomial::Polynomial ( float * array, unsigned int size, unsigned int offset = `0` )
inline

Creates a polynomial from the given array.

The elements are copied in order. A valid array must have at least one element, and the first element cannot be 0 if there is more than one element.

Parameters
 array the array of polynomial coefficients size the number of elements to copy from the array offset the offset position to start in the array

## ◆ ~Polynomial()

 virtual cugl::Polynomial::~Polynomial ( )
inlinevirtual

Deletes this polynomial

## ◆ bairstow_factor()

 bool cugl::Polynomial::bairstow_factor ( Polynomial & quad, Polynomial & result, float epsilon ) const
protected

Uses Bairstow's method to find a quadratic polynomial dividing this one.

Bairstow's method iteratively divides this polynomial by quadratic factors, until it finds one that divides it within epsilon. This method can fail (takes to many iterations; the Jacobian is singular), hence the return value. For more information, see

http://nptel.ac.in/courses/122104019/numerical-analysis/Rathish-kumar/ratish-1/f3node9.html

When calling this method, quad must be provided as an initial guess, while result can be empty. This method will modify both quad and result. quad is the final quadratic divider. result is the result of the division.

Parameters
 quad the final quadratic divisor chosen result the result of the final division epsilon the error tolerance for quad
Returns
true if Bairstow's method completes successfully

## ◆ degree()

 long cugl::Polynomial::degree ( ) const
inline

Returns the degree of this polynomial.

The degree is 1 less than the size. We make the degree a long instead of size-type so that it is safe to use in math formulas where the degree may go negative.

Returns
the degree of this polynomial.

## ◆ derivative()

 Polynomial cugl::Polynomial::derivative ( ) const

Returns the derivative of this polynomial

The derivative has degree one less than original, unless it the original has degree 1. In that case, the derivative is 0.

Returns
the derivative of this polynomial

## ◆ evaluate()

 float cugl::Polynomial::evaluate ( float value ) const

Returns the evaluation of the polynomial on the given value.

Evaluation plugs the value in for the polynomial variable.

Returns
the evaluation of the polynomial on the given value.

## ◆ isConstant()

 bool cugl::Polynomial::isConstant ( ) const
inline

Returns true if this polynomial is a constant.

Returns
true if this polynomial is a constant.

## ◆ isValid()

 bool cugl::Polynomial::isValid ( ) const
inline

Returns true if the polynomial is valid.

A valid polynomial is a vector of at least one element, and the first element cannot be 0 if there is more than one element.

Returns
true if the polynomial is valid.

## ◆ isZero()

 bool cugl::Polynomial::isZero ( ) const
inline

Returns true if the polynomial is the zero polynomial.

The zero polynomial has exactly one element and the value is 0. An invalid polynomial will return false if this method is called.

Returns
true if the polynomial is the zero polynomial.

## ◆ iterative_multiply()

 static Polynomial cugl::Polynomial::iterative_multiply ( const Polynomial & a, const Polynomial & b )
staticprotected

Returns the product of polynomials a and b.

This method multiplies the two polynomials with a nested for-loop. It is O(nm) where n is the degree of a and m the degree of b. It is, however, faster on small polynomials.

Parameters
 a The first polynomial to muliply b The second polynomial to muliply
Returns
the product of polynomials a and b

## ◆ normalize()

 float cugl::Polynomial::normalize ( )

Converts this polynomial into the associated mononomial.

This method divides the polynomial by the coefficient of the first term. If the polynomial is invalid, this method will fail.

Returns
the coefficient divider of the original polynomial

## ◆ operator std::string()

 cugl::Polynomial::operator std::string ( ) const
inline

Cast from a Polynomial to a string.

## ◆ operator!=()

 bool cugl::Polynomial::operator!= ( float value ) const
inline

Returns true if this polynomial is nonconstant or not equal to this float.

Parameters
 value The float to compare
Returns
true if this polynomial is nonconstant or not equal to this float.

## ◆ operator%() [1/2]

 Polynomial cugl::Polynomial::operator% ( const Polynomial & other ) const
inline

Returns the remainder when dividing this polynomial by other.

Parameters
 other The polynomial to divide by
Returns
the remainder when dividing this polynomial by other.

## ◆ operator%() [2/2]

 Polynomial cugl::Polynomial::operator% ( float value ) const
inline

Returns the remainder when dividing this polynomial by value.

Parameters
 value The value to divide by
Returns
the remainder when dividing this polynomial by value.

## ◆ operator%=() [1/2]

 Polynomial & cugl::Polynomial::operator%= ( const Polynomial & other )

Assigns this polynomial the division remainder of the other polynomial.

If other is not valid, then this method will fail.

Parameters
 other The polynomial to divide by
Returns
This polynomial, modified.

## ◆ operator%=() [2/2]

 Polynomial & cugl::Polynomial::operator%= ( float value )

Assigns this polynomial the division remainder of value.

If value is zero, then this method will fail.

Parameters
 value The value to divide by
Returns
This polynomial, modified.

## ◆ operator*() [1/2]

 Polynomial cugl::Polynomial::operator* ( const Polynomial & other ) const

Returns the product of this polynomial and other.

Parameters
 other The polynomial to multiply
Returns
the product of this polynomial and other.

## ◆ operator*() [2/2]

 Polynomial cugl::Polynomial::operator* ( float value ) const
inline

Returns the product of this polynomial and value.

Parameters
 value The value to multiply
Returns
the product of this polynomial and value.

## ◆ operator*=() [1/2]

 Polynomial & cugl::Polynomial::operator*= ( const Polynomial & other )
inline

Multiplies the given polynomial in place.

Parameters
 other The polynomial to multiply
Returns
This polynomial, modified.

## ◆ operator*=() [2/2]

 Polynomial & cugl::Polynomial::operator*= ( float value )

Multiplies the given value in place.

Parameters
 value The value to multiply
Returns
This polynomial, modified.

## ◆ operator+() [1/2]

 Polynomial cugl::Polynomial::operator+ ( const Polynomial & other ) const
inline

Returns the sum of this polynomial and other.

Parameters
 other The polynomial to add
Returns
the sum of this polynomial and other.

## ◆ operator+() [2/2]

 Polynomial cugl::Polynomial::operator+ ( float value ) const
inline

Returns the sum of this polynomial and value.

Parameters
 value The value to add
Returns
the sum of this polynomial and value.

## ◆ operator+=() [1/2]

 Polynomial & cugl::Polynomial::operator+= ( const Polynomial & other )

Adds the given polynomial in place.

Parameters
 other The polynomial to add
Returns
This polynomial, modified.

## ◆ operator+=() [2/2]

 Polynomial & cugl::Polynomial::operator+= ( float value )

Adds the given constant in place.

Parameters
 value The value to add
Returns
This polynomial, modified.

## ◆ operator-() [1/3]

 Polynomial cugl::Polynomial::operator- ( ) const

Returns the negation of this polynomial.

Returns
the negation of this polynomial.

## ◆ operator-() [2/3]

 Polynomial cugl::Polynomial::operator- ( const Polynomial & other ) const
inline

Returns the result of subtracting other from this.

Parameters
 other The polynomial to subtract
Returns
the result of subtracting other from this.

## ◆ operator-() [3/3]

 Polynomial cugl::Polynomial::operator- ( float value ) const
inline

Returns the result of subtracting value from this.

Parameters
 value The value to subtract
Returns
the result of subtracting value from this.

## ◆ operator-=() [1/2]

 Polynomial & cugl::Polynomial::operator-= ( const Polynomial & other )

Subtracts this polynomial by the given polynomial in place.

Parameters
 other The polynomial to subtract
Returns
This polynomial, modified.

## ◆ operator-=() [2/2]

 Polynomial & cugl::Polynomial::operator-= ( float value )

Subtracts this polynomial by the given value in place.

Parameters
 value The value to subtract
Returns
This polynomial, modified.

## ◆ operator/() [1/2]

 Polynomial cugl::Polynomial::operator/ ( const Polynomial & other ) const
inline

Returns the result of dividing this polynomial by other.

Parameters
 other The polynomial to divide by
Returns
the result of dividing this polynomial by other.

## ◆ operator/() [2/2]

 Polynomial cugl::Polynomial::operator/ ( float value ) const
inline

Returns the result of dividing this polynomial by value.

Parameters
 value The value to divide by
Returns
the result of dividing this polynomial by value.

## ◆ operator/=() [1/2]

 Polynomial & cugl::Polynomial::operator/= ( const Polynomial & other )

Divides this polynomial by the given polynomial in place.

If other is not valid, then this method will fail.

Parameters
 other The polynomial to divide by
Returns
This polynomial, modified.

## ◆ operator/=() [2/2]

 Polynomial & cugl::Polynomial::operator/= ( float value )

Divides this polynomial by the given value in place.

If value is zero, then this method will fail.

Parameters
 value The value to divide by
Returns
This polynomial, modified.

## ◆ operator<() [1/2]

 bool cugl::Polynomial::operator< ( const Polynomial & p ) const

Returns true if this polynomial is less than the given polynomial.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 p The polynomial to compare against.
Returns
True if this polynomial is less than the given polynomial.

## ◆ operator<() [2/2]

 bool cugl::Polynomial::operator< ( float value ) const
inline

Returns true if this polynomial is less than the given float.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 value The float to compare against.
Returns
True if this polynomial is less than the given float.

## ◆ operator<=() [1/2]

 bool cugl::Polynomial::operator<= ( const Polynomial & p ) const

Returns true if this polynomial is less than or equal the given polynomial.

This comparison uses the lexicographical order. To test if all components in this vector are less than those of v, use the method under().

Parameters
 p The polynomial to compare against.
Returns
True if polynomial vector is less than or equal the given polynomial.

## ◆ operator<=() [2/2]

 bool cugl::Polynomial::operator<= ( float value ) const
inline

Returns true if this polynomial is less than or equal the given float.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 value The float to compare against.
Returns
True if this polynomial is less than or equal the given float.

## ◆ operator=() [1/3]

 Polynomial & cugl::Polynomial::operator= ( const Polynomial & poly )
inline

Sets this polynomial to be a copy of the one specified

Parameters
 poly The polynomial to copy.
Returns
A reference to this (modified) Polynomial for chaining.

## ◆ operator=() [2/3]

 Polynomial & cugl::Polynomial::operator= ( float value )
inline

Sets this polynomial to be the given constant value.

Parameters
 value The float to copy.
Returns
A reference to this (modified) Polynomial for chaining.

## ◆ operator=() [3/3]

 Polynomial & cugl::Polynomial::operator= ( Polynomial && poly )
inline

Sets this polynomial to have the resources of the one specified

Parameters
 poly The polynomial to take from.
Returns
A reference to this (modified) Polynomial for chaining.

## ◆ operator==()

 bool cugl::Polynomial::operator== ( float value ) const
inline

Returns true if this polynomial is a constant equal to this float.

Parameters
 value The float to compare
Returns
true if this polynomial is a constant equal to this float.

## ◆ operator>() [1/2]

 bool cugl::Polynomial::operator> ( const Polynomial & p ) const

Determines if this polynomial is greater than the given polynomial.

This comparison uses the lexicographical order. To test if all components in this vector are greater than those of v, use the method over().

Parameters
 p The polynomial to compare against.
Returns
True if this polynomial is greater than the given polynomial.

## ◆ operator>() [2/2]

 bool cugl::Polynomial::operator> ( float value ) const
inline

Returns true if this polynomial is greater than the given float.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 value The float to compare against.
Returns
True if this polynomial is greater than the given float.

## ◆ operator>=() [1/2]

 bool cugl::Polynomial::operator>= ( const Polynomial & p ) const

Determines if this polynomial is greater than or equal the given polynomial.

This comparison uses the lexicographical order. To test if all components in this vector are greater than those of v, use the method over().

Parameters
 p The polynomial to compare against.
Returns
True if this polynomial is greater than or equal the given polynomial.

## ◆ operator>=() [2/2]

 bool cugl::Polynomial::operator>= ( float value ) const
inline

Returns true if this polynomial is greater than or equal the given float.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 value The float to compare against.
Returns
True if this polynomial is greater than or equal the given float.

## ◆ recursive_multiply()

 static Polynomial cugl::Polynomial::recursive_multiply ( const Polynomial & a, const Polynomial & b )
staticprotected

Returns the product of polynomials a and b.

This method multiplies the two polynomials with recursively using a divide-and-conquer algorithm. The algorithm is described here:

http://algorithm.cs.nthu.edu.tw/~course/Extra_Info/Divide%20and%20Conquer_supplement.pdf

This algorithm is θ(n) where n is the maximum degree of a and b. It is, however, slower on small polynomials.

Parameters
 a The first polynomial to muliply b The second polynomial to muliply
Returns
the product of polynomials a and b

## ◆ roots()

 bool cugl::Polynomial::roots ( vector< float > & roots, float epsilon = `CU_MATH_EPSILON` ) const

Computes the roots of this polynomial using Bairstow's method

Bairstow's method is an approximate root finding technique. The value epsilon is the error value for all of the roots. A good description of Bairstow's method can be found here:

http://nptel.ac.in/courses/122104019/numerical-analysis/Rathish-kumar/ratish-1/f3node9.html

The roots are stored in the provided vector. When complete, the vector will have degree many elements. If any root is complex, this method will have added NaN in its place.

It is possible for Bairstow's method to fail, which is why this method has a return value.

Parameters
 roots the vector to store the root values epsilon the error tolerance for the root values
Returns
true if Bairstow's method completes successfully

## ◆ set() [1/2]

 Polynomial & cugl::Polynomial::set ( float * array, int size )

Sets the elements of this polynomial to those in the specified array.

Parameters
 array The array to copy. size The number of elements in the array.
Returns
A reference to this (modified) Polynomial for chaining.

## ◆ set() [2/2]

 Polynomial & cugl::Polynomial::set ( float value )
inline

Sets this polynomial to be the given constant value.

Parameters
 value The float to copy.
Returns
A reference to this (modified) Polynomial for chaining.

 void cugl::Polynomial::solve_quadratic ( vector< float > & roots ) const
protected

Solve for the roots of this polynomial with the quadratic formula.

Obviously, this method will fail if the polynomial is not quadratic. The roots are added to the provided vector (the original contents are not erased). If any root is complex, this method will have added NaN in its place.

Parameters
 roots the vector to store the root values

## ◆ synthetic_divide()

 Polynomial & cugl::Polynomial::synthetic_divide ( const Polynomial & other )
protected

Returns the synthetic division of this polynomial by other

This method is adopted from the python code provided at

https://en.wikipedia.org/wiki/Synthetic_division

Synthetic division preserves the length of the vector. The beginning is the result, and the tail is the remainder. This value must be broken up to implement the / and % operators. However, some algorithms (like Bairstow's method) prefer this method just the way it is.

Parameters
 other the polynomial to divide by
Returns
the synthetic division of this polynomial by other

## ◆ toString()

 std::string cugl::Polynomial::toString ( bool format = `true` ) const

Returns a string representation of this polynomial.

There are two ways to represent a polynomial. One is in polynomial form, like

x^4 - x^3 + 2x^2 - 3

Alternatively, we could represent the same polynomial as its vector contents [1, -1, 2, 0, -3]. This is the purpose of the optional parameter.

Parameters
 format whether to format as a polynomial
Returns
a string representation of this polynomial

## ◆ validate()

 void cugl::Polynomial::validate ( )

Converts this polynomial into an equivalent valid polynomial.

This method trims the zero values from the front of the vector until reaching a non-zero value, or there is only one value left.

## ◆ operator%

 Polynomial operator% ( float left, const Polynomial & right )
friend

Returns the remainder when dividing value by the polynomial.

The value will be the polynomial unless the polynomial is constant.

Parameters
 left The initial value right The polynomial to divide by
Returns
the remainder when dividing value by the polynomial.

## ◆ operator*

 Polynomial operator* ( float left, const Polynomial & right )
friend

Returns the product of the polynomial and value.

Parameters
 left The value to multiply right The polynomial
Returns
the product of the polynomial and value.

## ◆ operator+

 Polynomial operator+ ( float left, const Polynomial & right )
friend

Returns the sum of the polynomial and value.

Parameters
 left The value to add right The polynomial
Returns
the sum of the polynomial and value.

## ◆ operator-

 Polynomial operator- ( float left, const Polynomial & right )
friend

Returns the result of subtracting the polynomial from value.

Parameters
 left The initial value right The polynomial to subtract
Returns
the result of subtracting the polynomial from value.

## ◆ operator/

 Polynomial operator/ ( float left, const Polynomial & right )
friend

Returns the result of dividing value by the polynomial.

The result will always be 0, unless the polynomial is a constant.

Parameters
 left The initial value right The polynomial to divide by
Returns
the result of dividing value by the polynomial.

## ◆ operator<

 bool operator< ( float left, const Polynomial & right )
friend

Returns true if the float is less than the given polynomial.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 left The float to compare against right The polynomial to compare
Returns
True if the float is less than the given polynomial.

## ◆ operator<=

 bool operator<= ( float left, const Polynomial & right )
friend

Returns true if the float is less than or equal the given polynomial.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 left The float to compare against right The polynomial to compare
Returns
True if the float is less than or equal the given polynomial.

## ◆ operator>

 bool operator> ( float left, const Polynomial & right )
friend

Returns true if the float is greater than the given polynomial.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 left The float to compare against right The polynomial to compare
Returns
True if the float is greater than the given polynomial.

## ◆ operator>=

 bool operator>= ( float left, const Polynomial & right )
friend

Returns true if the float is greater than or equal the given polynomial.

Polynomials are compared by degree, so that larger polynomials are always greater. Then they are compared coefficient by coefficient, starting at the coefficient of highest degree.

Parameters
 left The float to compare against right The polynomial to compare
Returns
True if the float is greater than or equal the given polynomial.

## ◆ ONE

 const Polynomial cugl::Polynomial::ONE
static

The unit polynomial

## ◆ ZERO

 const Polynomial cugl::Polynomial::ZERO
static

The zero polynomial

The documentation for this class was generated from the following file: