 |
Cornell Cocos
Cornell Extensions to Cocos2d
|
#include <CUPolynomial.h>
Public Member Functions | |
| Polynomial () | |
| Polynomial (long degree) | |
| Polynomial (long degree, float value) | |
| Polynomial (const 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 | constant () 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) const |
| string | toString (bool format=true) 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 |
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) |
| ostream & | operator<< (ostream &os, const Polynomial &poly) |
Class to represent 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
Therefore, 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, we cannot guarantee that any of the polynomial methods (such as root finding) will work properly.
This is the motivation for 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 safe 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 |
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/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.
| quad | the final quadratic divisor chosen |
| result | the result of the final division |
| epsilon | the error tolerance for quad |
|
inline |
Returns true if this polynomial is a constant.
|
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.
| NS_CC_BEGIN Polynomial 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 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 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 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.
| s | The first polynomial to muliply |
| b | The second polynomial to muliply |
| float 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 |
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 & 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 & 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 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 & 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 & Polynomial::operator+= | ( | const Polynomial & | other | ) |
Adds the given polynomial in place.
| other | The polynomial to add |
| Polynomial & Polynomial::operator+= | ( | float | value | ) |
Adds the given constant in place.
| value | The value to add |
|
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 & Polynomial::operator-= | ( | const Polynomial & | other | ) |
Subtracts this polynomial by the given polynomial in place.
| other | The polynomial to subtract |
| Polynomial & 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 & 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 & 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 |
|
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.
| s | The first polynomial to muliply |
| b | The second polynomial to muliply |
| bool Polynomial::roots | ( | vector< float > & | roots, |
| float | 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.
| roots | the vector to store the root values |
| epsilon | the error tolerance for the root values |
|
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 |
| string 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 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.
|
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 |
Outputs this polynomial to the given output stream.
This function uses the toString() method to convert the polynomial into a string
| os | the output stream |
| poly | the polynomial to ouput |
1.8.10
