123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176 |
- [section:rational Polynomial and Rational Function Evaluation]
- [h4 Synopsis]
- ``
- #include <boost/math/tools/rational.hpp>
- ``
- // Polynomials:
- template <std::size_t N, class T, class V>
- V evaluate_polynomial(const T(&poly)[N], const V& val);
- template <std::size_t N, class T, class V>
- V evaluate_polynomial(const boost::array<T,N>& poly, const V& val);
- template <class T, class U>
- U evaluate_polynomial(const T* poly, U z, std::size_t count);
- // Even polynomials:
- template <std::size_t N, class T, class V>
- V evaluate_even_polynomial(const T(&poly)[N], const V& z);
- template <std::size_t N, class T, class V>
- V evaluate_even_polynomial(const boost::array<T,N>& poly, const V& z);
- template <class T, class U>
- U evaluate_even_polynomial(const T* poly, U z, std::size_t count);
- // Odd polynomials
- template <std::size_t N, class T, class V>
- V evaluate_odd_polynomial(const T(&a)[N], const V& z);
- template <std::size_t N, class T, class V>
- V evaluate_odd_polynomial(const boost::array<T,N>& a, const V& z);
- template <class T, class U>
- U evaluate_odd_polynomial(const T* poly, U z, std::size_t count);
- // Rational Functions:
- template <std::size_t N, class T, class V>
- V evaluate_rational(const T(&a)[N], const T(&b)[N], const V& z);
- template <std::size_t N, class T, class V>
- V evaluate_rational(const boost::array<T,N>& a, const boost::array<T,N>& b, const V& z);
- template <class T, class U, class V>
- V evaluate_rational(const T* num, const U* denom, V z, unsigned count);
- [h4 Description]
- Each of the functions come in three variants: a pair of overloaded functions
- where the order of the polynomial or rational function is evaluated at
- compile time, and an overload that accepts a runtime variable for the size
- of the coefficient array. Generally speaking, compile time evaluation of the
- array size results in better type safety, is less prone to programmer errors,
- and may result in better optimised code. The polynomial evaluation functions
- in particular, are specialised for various array sizes, allowing for
- loop unrolling, and one hopes, optimal inline expansion.
- template <std::size_t N, class T, class V>
- V evaluate_polynomial(const T(&poly)[N], const V& val);
- template <std::size_t N, class T, class V>
- V evaluate_polynomial(const boost::array<T,N>& poly, const V& val);
- template <class T, class U>
- U evaluate_polynomial(const T* poly, U z, std::size_t count);
- Evaluates the [@http://en.wikipedia.org/wiki/Polynomial polynomial] described by
- the coefficients stored in /poly/.
- If the size of the array is specified at runtime, then the polynomial
- most have order /count-1/ with /count/ coefficients. Otherwise it has
- order /N-1/ with /N/ coefficients.
- Coefficients should be stored such that the coefficients for the x[super i] terms
- are in poly[i].
- The types of the coefficients and of variable
- /z/ may differ as long as /*poly/ is convertible to type /U/.
- This allows, for example, for the coefficient table
- to be a table of integers if this is appropriate.
- template <std::size_t N, class T, class V>
- V evaluate_even_polynomial(const T(&poly)[N], const V& z);
- template <std::size_t N, class T, class V>
- V evaluate_even_polynomial(const boost::array<T,N>& poly, const V& z);
- template <class T, class U>
- U evaluate_even_polynomial(const T* poly, U z, std::size_t count);
- As above, but evaluates an even polynomial: one where all the powers
- of /z/ are even numbers. Equivalent to calling
- `evaluate_polynomial(poly, z*z, count)`.
- template <std::size_t N, class T, class V>
- V evaluate_odd_polynomial(const T(&a)[N], const V& z);
- template <std::size_t N, class T, class V>
- V evaluate_odd_polynomial(const boost::array<T,N>& a, const V& z);
- template <class T, class U>
- U evaluate_odd_polynomial(const T* poly, U z, std::size_t count);
- As above but evaluates a polynomial where all the powers are odd numbers.
- Equivalent to `evaluate_polynomial(poly+1, z*z, count-1) * z + poly[0]`.
- template <std::size_t N, class T, class U, class V>
- V evaluate_rational(const T(&num)[N], const U(&denom)[N], const V& z);
- template <std::size_t N, class T, class U, class V>
- V evaluate_rational(const boost::array<T,N>& num, const boost::array<U,N>& denom, const V& z);
- template <class T, class U, class V>
- V evaluate_rational(const T* num, const U* denom, V z, unsigned count);
- Evaluates the rational function (the ratio of two polynomials) described by
- the coefficients stored in /num/ and /demom/.
- If the size of the array is specified at runtime then both
- polynomials most have order /count-1/ with /count/ coefficients.
- Otherwise both polynomials have order /N-1/ with /N/ coefficients.
- Array /num/ describes the numerator, and /demon/ the denominator.
- Coefficients should be stored such that the coefficients for the x[super i ] terms
- are in num[i] and denom[i].
- The types of the coefficients and of variable
- /v/ may differ as long as /*num/ and /*denom/ are convertible to type /V/.
- This allows, for example, for one or both of the coefficient tables
- to be a table of integers if this is appropriate.
- These functions are designed to safely evaluate the result, even when the value
- /z/ is very large. As such they do not take advantage of compile time array
- sizes to make any optimisations. These functions are best reserved for situations
- where /z/ may be large: if you can be sure that numerical overflow will not occur
- then polynomial evaluation with compile-time array sizes may offer slightly
- better performance.
- [h4 Implementation]
- Polynomials are evaluated by
- [@http://en.wikipedia.org/wiki/Horner_algorithm Horners method].
- If the array size is known at
- compile time then the functions dispatch to size-specific implementations
- that unroll the evaluation loop.
- Rational evaluation is by
- [@http://en.wikipedia.org/wiki/Horner_algorithm Horners method]:
- with the two polynomials being evaluated
- in parallel to make the most of the processors floating-point pipeline.
- If /v/ is greater than one, then the polynomials are evaluated in reverse
- order as polynomials in ['1\/v]: this avoids unnecessary numerical overflow when the
- coefficients are large.
- Both the polynomial and rational function evaluation algorithms can be
- tuned using various configuration macros to provide optimal performance
- for a particular combination of compiler and platform. This includes
- support for second-order Horner's methods. The various options are
- [link math_toolkit.tuning documented here]. However, the performance
- benefits to be gained from these are marginal on most current hardware,
- consequently it's best to run the
- [link math_toolkit.perf_test_app performance test application] before
- changing the default settings.
- [endsect] [/section:rational Polynomial and Rational Function Evaluation]
- [/
- Copyright 2006 John Maddock and Paul A. Bristow.
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt).
- ]
|