]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
51 | Each of the functions come in three variants: a pair of overloaded functions | |
52 | where the order of the polynomial or rational function is evaluated at | |
53 | compile time, and an overload that accepts a runtime variable for the size | |
54 | of the coefficient array. Generally speaking, compile time evaluation of the | |
55 | array size results in better type safety, is less prone to programmer errors, | |
56 | and may result in better optimised code. The polynomial evaluation functions | |
57 | in particular, are specialised for various array sizes, allowing for | |
58 | loop 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 | ||
69 | Evaluates the [@http://en.wikipedia.org/wiki/Polynomial polynomial] described by | |
70 | the coefficients stored in /poly/. | |
71 | ||
72 | If the size of the array is specified at runtime, then the polynomial | |
73 | most have order /count-1/ with /count/ coefficients. Otherwise it has | |
74 | order /N-1/ with /N/ coefficients. | |
75 | ||
76 | Coefficients should be stored such that the coefficients for the x[super i] terms | |
77 | are in poly[i]. | |
78 | ||
79 | The types of the coefficients and of variable | |
80 | /z/ may differ as long as /*poly/ is convertible to type /U/. | |
81 | This allows, for example, for the coefficient table | |
82 | to 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 | ||
93 | As above, but evaluates an even polynomial: one where all the powers | |
94 | of /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 | ||
106 | As above but evaluates a polynomial where all the powers are odd numbers. | |
107 | Equivalent 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 | ||
118 | Evaluates the rational function (the ratio of two polynomials) described by | |
119 | the coefficients stored in /num/ and /demom/. | |
120 | ||
121 | If the size of the array is specified at runtime then both | |
122 | polynomials most have order /count-1/ with /count/ coefficients. | |
123 | Otherwise both polynomials have order /N-1/ with /N/ coefficients. | |
124 | ||
125 | Array /num/ describes the numerator, and /demon/ the denominator. | |
126 | ||
127 | Coefficients should be stored such that the coefficients for the x[super i ] terms | |
128 | are in num[i] and denom[i]. | |
129 | ||
130 | The types of the coefficients and of variable | |
131 | /v/ may differ as long as /*num/ and /*denom/ are convertible to type /V/. | |
132 | This allows, for example, for one or both of the coefficient tables | |
133 | to be a table of integers if this is appropriate. | |
134 | ||
135 | These 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 | |
137 | sizes to make any optimisations. These functions are best reserved for situations | |
138 | where /z/ may be large: if you can be sure that numerical overflow will not occur | |
139 | then polynomial evaluation with compile-time array sizes may offer slightly | |
140 | better performance. | |
141 | ||
142 | [h4 Implementation] | |
143 | ||
144 | Polynomials are evaluated by | |
145 | [@http://en.wikipedia.org/wiki/Horner_algorithm Horners method]. | |
146 | If the array size is known at | |
147 | compile time then the functions dispatch to size-specific implementations | |
148 | that unroll the evaluation loop. | |
149 | ||
150 | Rational evaluation is by | |
151 | [@http://en.wikipedia.org/wiki/Horner_algorithm Horners method]: | |
152 | with the two polynomials being evaluated | |
153 | in parallel to make the most of the processors floating-point pipeline. | |
154 | If /v/ is greater than one, then the polynomials are evaluated in reverse | |
155 | order as polynomials in ['1\/v]: this avoids unnecessary numerical overflow when the | |
156 | coefficients are large. | |
157 | ||
158 | Both the polynomial and rational function evaluation algorithms can be | |
159 | tuned using various configuration macros to provide optimal performance | |
160 | for a particular combination of compiler and platform. This includes | |
161 | support for second-order Horner's methods. The various options are | |
162 | [link math_toolkit.tuning documented here]. However, the performance | |
163 | benefits to be gained from these are marginal on most current hardware, | |
164 | consequently it's best to run the | |
165 | [link math_toolkit.perf_test_app performance test application] before | |
166 | changing 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 |