1[section:rational Polynomial and Rational Function Evaluation] 2 3[h4 Synopsis] 4 5`` 6#include <boost/math/tools/rational.hpp> 7`` 8 9 // Polynomials: 10 template <std::size_t N, class T, class V> 11 V evaluate_polynomial(const T(&poly)[N], const V& val); 12 13 template <std::size_t N, class T, class V> 14 V evaluate_polynomial(const boost::array<T,N>& poly, const V& val); 15 16 template <class T, class U> 17 U evaluate_polynomial(const T* poly, U z, std::size_t count); 18 19 // Even polynomials: 20 template <std::size_t N, class T, class V> 21 V evaluate_even_polynomial(const T(&poly)[N], const V& z); 22 23 template <std::size_t N, class T, class V> 24 V evaluate_even_polynomial(const boost::array<T,N>& poly, const V& z); 25 26 template <class T, class U> 27 U evaluate_even_polynomial(const T* poly, U z, std::size_t count); 28 29 // Odd polynomials 30 template <std::size_t N, class T, class V> 31 V evaluate_odd_polynomial(const T(&a)[N], const V& z); 32 33 template <std::size_t N, class T, class V> 34 V evaluate_odd_polynomial(const boost::array<T,N>& a, const V& z); 35 36 template <class T, class U> 37 U evaluate_odd_polynomial(const T* poly, U z, std::size_t count); 38 39 // Rational Functions: 40 template <std::size_t N, class T, class V> 41 V evaluate_rational(const T(&a)[N], const T(&b)[N], const V& z); 42 43 template <std::size_t N, class T, class V> 44 V evaluate_rational(const boost::array<T,N>& a, const boost::array<T,N>& b, const V& z); 45 46 template <class T, class U, class V> 47 V evaluate_rational(const T* num, const U* denom, V z, unsigned count); 48 49[h4 Description] 50 51Each of the functions come in three variants: a pair of overloaded functions 52where the order of the polynomial or rational function is evaluated at 53compile time, and an overload that accepts a runtime variable for the size 54of the coefficient array. Generally speaking, compile time evaluation of the 55array size results in better type safety, is less prone to programmer errors, 56and may result in better optimised code. The polynomial evaluation functions 57in particular, are specialised for various array sizes, allowing for 58loop unrolling, and one hopes, optimal inline expansion. 59 60 template <std::size_t N, class T, class V> 61 V evaluate_polynomial(const T(&poly)[N], const V& val); 62 63 template <std::size_t N, class T, class V> 64 V evaluate_polynomial(const boost::array<T,N>& poly, const V& val); 65 66 template <class T, class U> 67 U evaluate_polynomial(const T* poly, U z, std::size_t count); 68 69Evaluates the [@http://en.wikipedia.org/wiki/Polynomial polynomial] described by 70the coefficients stored in /poly/. 71 72If the size of the array is specified at runtime, then the polynomial 73most have order /count-1/ with /count/ coefficients. Otherwise it has 74order /N-1/ with /N/ coefficients. 75 76Coefficients should be stored such that the coefficients for the x[super i] terms 77are in poly[i]. 78 79The types of the coefficients and of variable 80/z/ may differ as long as /*poly/ is convertible to type /U/. 81This allows, for example, for the coefficient table 82to be a table of integers if this is appropriate. 83 84 template <std::size_t N, class T, class V> 85 V evaluate_even_polynomial(const T(&poly)[N], const V& z); 86 87 template <std::size_t N, class T, class V> 88 V evaluate_even_polynomial(const boost::array<T,N>& poly, const V& z); 89 90 template <class T, class U> 91 U evaluate_even_polynomial(const T* poly, U z, std::size_t count); 92 93As above, but evaluates an even polynomial: one where all the powers 94of /z/ are even numbers. Equivalent to calling 95`evaluate_polynomial(poly, z*z, count)`. 96 97 template <std::size_t N, class T, class V> 98 V evaluate_odd_polynomial(const T(&a)[N], const V& z); 99 100 template <std::size_t N, class T, class V> 101 V evaluate_odd_polynomial(const boost::array<T,N>& a, const V& z); 102 103 template <class T, class U> 104 U evaluate_odd_polynomial(const T* poly, U z, std::size_t count); 105 106As above but evaluates a polynomial where all the powers are odd numbers. 107Equivalent to `evaluate_polynomial(poly+1, z*z, count-1) * z + poly[0]`. 108 109 template <std::size_t N, class T, class U, class V> 110 V evaluate_rational(const T(&num)[N], const U(&denom)[N], const V& z); 111 112 template <std::size_t N, class T, class U, class V> 113 V evaluate_rational(const boost::array<T,N>& num, const boost::array<U,N>& denom, const V& z); 114 115 template <class T, class U, class V> 116 V evaluate_rational(const T* num, const U* denom, V z, unsigned count); 117 118Evaluates the rational function (the ratio of two polynomials) described by 119the coefficients stored in /num/ and /demom/. 120 121If the size of the array is specified at runtime then both 122polynomials most have order /count-1/ with /count/ coefficients. 123Otherwise both polynomials have order /N-1/ with /N/ coefficients. 124 125Array /num/ describes the numerator, and /demon/ the denominator. 126 127Coefficients should be stored such that the coefficients for the x[super i ] terms 128are in num[i] and denom[i]. 129 130The types of the coefficients and of variable 131/v/ may differ as long as /*num/ and /*denom/ are convertible to type /V/. 132This allows, for example, for one or both of the coefficient tables 133to be a table of integers if this is appropriate. 134 135These functions are designed to safely evaluate the result, even when the value 136/z/ is very large. As such they do not take advantage of compile time array 137sizes to make any optimisations. These functions are best reserved for situations 138where /z/ may be large: if you can be sure that numerical overflow will not occur 139then polynomial evaluation with compile-time array sizes may offer slightly 140better performance. 141 142[h4 Implementation] 143 144Polynomials are evaluated by 145[@http://en.wikipedia.org/wiki/Horner_algorithm Horners method]. 146If the array size is known at 147compile time then the functions dispatch to size-specific implementations 148that unroll the evaluation loop. 149 150Rational evaluation is by 151[@http://en.wikipedia.org/wiki/Horner_algorithm Horners method]: 152with the two polynomials being evaluated 153in parallel to make the most of the processors floating-point pipeline. 154If /v/ is greater than one, then the polynomials are evaluated in reverse 155order as polynomials in ['1\/v]: this avoids unnecessary numerical overflow when the 156coefficients are large. 157 158Both the polynomial and rational function evaluation algorithms can be 159tuned using various configuration macros to provide optimal performance 160for a particular combination of compiler and platform. This includes 161support for second-order Horner's methods. The various options are 162[link math_toolkit.tuning documented here]. However, the performance 163benefits to be gained from these are marginal on most current hardware, 164consequently it's best to run the 165[link math_toolkit.perf_test_app performance test application] before 166changing the default settings. 167 168[endsect] [/section:rational Polynomial and Rational Function Evaluation] 169 170[/ 171 Copyright 2006 John Maddock and Paul A. Bristow. 172 Distributed under the Boost Software License, Version 1.0. 173 (See accompanying file LICENSE_1_0.txt or copy at 174 http://www.boost.org/LICENSE_1_0.txt). 175] 176 177