CUGL 2.3
Cornell University Game Library

#include <CUPolynomial.h>
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 
Polynomial &  operator= (const Polynomial &poly) 
Polynomial &  operator= (Polynomial &&poly) 
Polynomial &  operator= (float value) 
Polynomial &  set (float *array, int size) 
Polynomial &  set (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 
Polynomial &  operator+= (const Polynomial &other) 
Polynomial &  operator= (const Polynomial &other) 
Polynomial &  operator*= (const Polynomial &other) 
Polynomial &  operator/= (const Polynomial &other) 
Polynomial &  operator%= (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 
Polynomial &  operator+= (float value) 
Polynomial &  operator= (float value) 
Polynomial &  operator*= (float value) 
Polynomial &  operator/= (float value) 
Polynomial &  operator%= (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  
Polynomial &  synthetic_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) 
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 wellformed, a polynomial vector must have at least one element. Furthermore, if it has more than one element, the first element must be nonzero. 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.

inline 
Creates a zero polynomial

inline 
Creates the polynomial x^d where is the degree.
The first coefficient is 1. All other coefficients are 0.
degree  the degree of the polynomial 

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.
degree  the degree of the polynomial 
value  the coefficient of each term 

inline 
Creates a copy of the given polynomial.
poly  the polynomial to copy 

inline 
Takes then resources from the given polynomial.
poly  the polynomial to take from 

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.
first  the beginning iterator 
last  the terminating iterator 

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

inlinevirtual 
Deletes this polynomial

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/numericalanalysis/Rathishkumar/ratish1/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.
quad  the final quadratic divisor chosen 
result  the result of the final division 
epsilon  the error tolerance for quad 

inline 
Returns the degree of this polynomial.
The degree is 1 less than the size. We make the degree a long instead of sizetype so that it is safe to use in math formulas where the degree may go negative.
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.
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.

inline 
Returns true if this polynomial is a constant.

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.

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.

staticprotected 
Returns the product of polynomials a and b.
This method multiplies the two polynomials with a nested forloop. It is O(nm) where n is the degree of a and m the degree of b. It is, however, faster on small polynomials.
a  The first polynomial to muliply 
b  The second polynomial to muliply 
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.

inline 
Cast from a Polynomial to a string.

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

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

inline 
Returns the remainder when dividing this polynomial by value.
value  The value to divide by 
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.
other  The polynomial to divide by 
Polynomial & cugl::Polynomial::operator%=  (  float  value  ) 
Assigns this polynomial the division remainder of value.
If value is zero, then this method will fail.
value  The value to divide by 
Polynomial cugl::Polynomial::operator*  (  const Polynomial &  other  )  const 
Returns the product of this polynomial and other.
other  The polynomial to multiply 

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

inline 
Multiplies the given polynomial in place.
other  The polynomial to multiply 
Polynomial & cugl::Polynomial::operator*=  (  float  value  ) 
Multiplies the given value in place.
value  The value to multiply 

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

inline 
Returns the sum of this polynomial and value.
value  The value to add 
Polynomial & cugl::Polynomial::operator+=  (  const Polynomial &  other  ) 
Adds the given polynomial in place.
other  The polynomial to add 
Polynomial & cugl::Polynomial::operator+=  (  float  value  ) 
Adds the given constant in place.
value  The value to add 
Polynomial cugl::Polynomial::operator  (  )  const 
Returns the negation of this polynomial.

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

inline 
Returns the result of subtracting value from this.
value  The value to subtract 
Polynomial & cugl::Polynomial::operator=  (  const Polynomial &  other  ) 
Subtracts this polynomial by the given polynomial in place.
other  The polynomial to subtract 
Polynomial & cugl::Polynomial::operator=  (  float  value  ) 
Subtracts this polynomial by the given value in place.
value  The value to subtract 

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

inline 
Returns the result of dividing this polynomial by value.
value  The value to divide by 
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.
other  The polynomial to divide by 
Polynomial & cugl::Polynomial::operator/=  (  float  value  ) 
Divides this polynomial by the given value in place.
If value is zero, then this method will fail.
value  The value to divide by 
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.
p  The polynomial to compare against. 

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.
value  The float to compare against. 
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().
p  The polynomial to compare against. 

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.
value  The float to compare against. 

inline 
Sets this polynomial to be a copy of the one specified
poly  The polynomial to copy. 

inline 
Sets this polynomial to be the given constant value.
value  The float to copy. 

inline 
Sets this polynomial to have the resources of the one specified
poly  The polynomial to take from. 

inline 
Returns true if this polynomial is a constant equal to this float.
value  The float to compare 
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().
p  The polynomial to compare against. 

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.
value  The float to compare against. 
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().
p  The polynomial to compare against. 

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.
value  The float to compare against. 

staticprotected 
Returns the product of polynomials a and b.
This method multiplies the two polynomials with recursively using a divideandconquer 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.
a  The first polynomial to muliply 
b  The second polynomial to muliply 
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/numericalanalysis/Rathishkumar/ratish1/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.
roots  the vector to store the root values 
epsilon  the error tolerance for the root values 
Polynomial & cugl::Polynomial::set  (  float *  array, 
int  size  
) 
Sets the elements of this polynomial to those in the specified array.
array  The array to copy. 
size  The number of elements in the array. 

inline 
Sets this polynomial to be the given constant value.
value  The float to copy. 

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.
roots  the vector to store the root values 

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.
other  the polynomial to divide by 
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.
format  whether to format as a polynomial 
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 nonzero value, or there is only one value left.

friend 
Returns the remainder when dividing value by the polynomial.
The value will be the polynomial unless the polynomial is constant.
left  The initial value 
right  The polynomial to divide by 

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

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

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

friend 
Returns the result of dividing value by the polynomial.
The result will always be 0, unless the polynomial is a constant.
left  The initial value 
right  The polynomial to divide by 

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.
left  The float to compare against 
right  The polynomial to compare 

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.
left  The float to compare against 
right  The polynomial to compare 

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.
left  The float to compare against 
right  The polynomial to compare 

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.
left  The float to compare against 
right  The polynomial to compare 

static 
The unit polynomial

static 
The zero polynomial