1 |
tim |
1744 |
/* |
2 |
|
|
* Copyright (C) 2000-2004 Object Oriented Parallel Simulation Engine (OOPSE) project |
3 |
|
|
* |
4 |
|
|
* Contact: oopse@oopse.org |
5 |
|
|
* |
6 |
|
|
* This program is free software; you can redistribute it and/or |
7 |
|
|
* modify it under the terms of the GNU Lesser General Public License |
8 |
|
|
* as published by the Free Software Foundation; either version 2.1 |
9 |
|
|
* of the License, or (at your option) any later version. |
10 |
|
|
* All we ask is that proper credit is given for our work, which includes |
11 |
|
|
* - but is not limited to - adding the above copyright notice to the beginning |
12 |
|
|
* of your source code files, and to any copyright notice that you may distribute |
13 |
|
|
* with programs based on this work. |
14 |
|
|
* |
15 |
|
|
* This program is distributed in the hope that it will be useful, |
16 |
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
17 |
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
18 |
|
|
* GNU Lesser General Public License for more details. |
19 |
|
|
* |
20 |
|
|
* You should have received a copy of the GNU Lesser General Public License |
21 |
|
|
* along with this program; if not, write to the Free Software |
22 |
|
|
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
23 |
|
|
* |
24 |
|
|
*/ |
25 |
|
|
|
26 |
|
|
/** |
27 |
|
|
* @file Polynomial.hpp |
28 |
tim |
1746 |
* @author teng lin |
29 |
|
|
* @date 11/16/2004 |
30 |
tim |
1744 |
* @version 1.0 |
31 |
|
|
*/ |
32 |
|
|
|
33 |
|
|
#ifndef MATH_POLYNOMIAL_HPP |
34 |
|
|
#define MATH_POLYNOMIAL_HPP |
35 |
|
|
|
36 |
|
|
#include <list> |
37 |
|
|
#include <utility> |
38 |
|
|
|
39 |
|
|
namespace oopse { |
40 |
|
|
|
41 |
tim |
1746 |
template<typename ElemType> pow(ElemType x, int N) { |
42 |
tim |
1744 |
ElemType result(1); |
43 |
|
|
|
44 |
|
|
for (int i = 0; i < N; ++i) { |
45 |
|
|
result *= x; |
46 |
|
|
} |
47 |
|
|
|
48 |
|
|
return result; |
49 |
|
|
} |
50 |
|
|
|
51 |
tim |
1746 |
/** |
52 |
|
|
* @class Polynomial Polynomial.hpp "math/Polynomial.hpp" |
53 |
|
|
* A generic Polynomial class |
54 |
|
|
*/ |
55 |
tim |
1744 |
template<typename ElemType> |
56 |
|
|
class Polynomial { |
57 |
|
|
|
58 |
|
|
public: |
59 |
|
|
|
60 |
|
|
typedef int ExponentType; |
61 |
tim |
1746 |
typedef ElemType CoefficientType; |
62 |
|
|
typedef std::map<ExponentType, CoefficientType> PolynomialPairMap; |
63 |
tim |
1744 |
typedef PolynomialPairMap::iterator PolynomialIterator; |
64 |
|
|
|
65 |
|
|
/** |
66 |
tim |
1746 |
* Calculates the value of this Polynomial evaluated at the given x value. |
67 |
|
|
* @return The value of this Polynomial evaluates at the given x value |
68 |
|
|
* @param x the value of the independent variable for this Polynomial function |
69 |
tim |
1744 |
*/ |
70 |
|
|
ElemType evaluate(const ElemType& x) { |
71 |
|
|
ElemType result; |
72 |
|
|
double exponent; |
73 |
tim |
1746 |
double coefficient; |
74 |
tim |
1744 |
|
75 |
|
|
for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) { |
76 |
|
|
exponent = i->first; |
77 |
tim |
1746 |
coefficient = i->second; |
78 |
|
|
result += pow(x, exponent) * coefficient; |
79 |
tim |
1744 |
} |
80 |
|
|
|
81 |
|
|
return result; |
82 |
|
|
} |
83 |
|
|
|
84 |
tim |
1746 |
/** |
85 |
|
|
* Returns the first derivative of this polynomial. |
86 |
|
|
* @return the first derivative of this polynomial |
87 |
|
|
* @param x |
88 |
|
|
*/ |
89 |
|
|
ElemType evaluateDerivative(const ElemType& x) { |
90 |
tim |
1744 |
ElemType result; |
91 |
|
|
double exponent; |
92 |
tim |
1746 |
double coefficient; |
93 |
tim |
1744 |
|
94 |
|
|
for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) { |
95 |
|
|
exponent = i->first; |
96 |
tim |
1746 |
coefficient = i->second; |
97 |
|
|
result += pow(x, exponent - 1) * coefficient * exponent; |
98 |
tim |
1744 |
} |
99 |
|
|
|
100 |
|
|
return result; |
101 |
|
|
} |
102 |
|
|
|
103 |
tim |
1746 |
/** |
104 |
tim |
1747 |
* Set the coefficent of the specified exponent, if the coefficient is already there, it |
105 |
|
|
* will be overwritten. |
106 |
tim |
1746 |
* @param exponent exponent of a term in this Polynomial |
107 |
|
|
* @param coefficient multiplier of a term in this Polynomial |
108 |
|
|
*/ |
109 |
|
|
|
110 |
|
|
void setCoefficient(int exponent, const ElemType& coefficient) { |
111 |
|
|
polyPairMap_.insert(PolynomialPairMap::value_type(exponent, coefficient)); |
112 |
tim |
1744 |
} |
113 |
|
|
|
114 |
tim |
1746 |
/** |
115 |
tim |
1747 |
* Set the coefficent of the specified exponent. If the coefficient is already there, just add the |
116 |
|
|
* new coefficient to the old one, otherwise, just call setCoefficent |
117 |
|
|
* @param exponent exponent of a term in this Polynomial |
118 |
|
|
* @param coefficient multiplier of a term in this Polynomial |
119 |
|
|
*/ |
120 |
|
|
|
121 |
|
|
void addCoefficient(int exponent, const ElemType& coefficient) { |
122 |
|
|
PolynomialIterator i = find(exponent); |
123 |
|
|
|
124 |
|
|
if (i != end()) { |
125 |
|
|
i->second += coefficient; |
126 |
|
|
} else { |
127 |
|
|
setCoefficient(exponent, coefficient); |
128 |
|
|
} |
129 |
|
|
} |
130 |
|
|
|
131 |
|
|
|
132 |
|
|
/** |
133 |
tim |
1746 |
* Returns the coefficient associated with the given power for this Polynomial. |
134 |
|
|
* @return the coefficient associated with the given power for this Polynomial |
135 |
|
|
* @exponent exponent of any term in this Polynomial |
136 |
|
|
*/ |
137 |
|
|
ElemType getCoefficient(ExponentType exponent) { |
138 |
|
|
PolynomialIterator i = find(exponent); |
139 |
tim |
1744 |
|
140 |
tim |
1746 |
if (i != end()) { |
141 |
|
|
return i->second; |
142 |
|
|
} else { |
143 |
|
|
return ElemType(0); |
144 |
|
|
} |
145 |
tim |
1744 |
} |
146 |
|
|
|
147 |
|
|
PolynomialIterator begin() { |
148 |
|
|
return polyPairMap_.begin(); |
149 |
|
|
} |
150 |
|
|
|
151 |
|
|
PolynomialIterator end() { |
152 |
|
|
return polyPairMap_.end(); |
153 |
|
|
} |
154 |
|
|
|
155 |
|
|
PolynomialIterator find(ExponentType exponent) { |
156 |
|
|
return polyPairMap_.find(); |
157 |
|
|
} |
158 |
tim |
1746 |
|
159 |
|
|
size_t size() { |
160 |
|
|
return polyPairMap_.size(); |
161 |
|
|
} |
162 |
|
|
|
163 |
tim |
1744 |
private: |
164 |
|
|
|
165 |
|
|
PolynomialPairMap polyPairMap_; |
166 |
|
|
}; |
167 |
|
|
|
168 |
tim |
1746 |
|
169 |
|
|
/** |
170 |
|
|
* Generates and returns the product of two given Polynomials. |
171 |
|
|
* @return A Polynomial containing the product of the two given Polynomial parameters |
172 |
|
|
*/ |
173 |
|
|
template<typename ElemType> |
174 |
|
|
Polynomial<ElemType> operator *(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
175 |
|
|
typename Polynomial<ElemType>::PolynomialIterator i; |
176 |
|
|
typename Polynomial<ElemType>::PolynomialIterator j; |
177 |
|
|
typename Polynomial<ElemType>::PolynomialIterator k; |
178 |
|
|
Polynomial<ElemType> p; |
179 |
|
|
int exponent; |
180 |
|
|
int coefficient; |
181 |
|
|
|
182 |
|
|
for (i = p1.begin(); i !=p1.end(); ++i) { |
183 |
tim |
1747 |
for (j = p1.begin(); j !=p1.end(); ++j) { |
184 |
tim |
1746 |
exponent = i->first + j->first; |
185 |
|
|
coefficient = i->second * j->second; |
186 |
|
|
k = p->find(exponent); |
187 |
|
|
|
188 |
|
|
if (k != p.end()) { |
189 |
|
|
p[exponent] = coefficient; |
190 |
|
|
} else { |
191 |
|
|
k->second += coefficient; |
192 |
|
|
} |
193 |
|
|
} |
194 |
|
|
} |
195 |
|
|
} |
196 |
|
|
|
197 |
|
|
/** |
198 |
|
|
* Generates and returns the sum of two given Polynomials. |
199 |
|
|
* @param p1 the first polynomial |
200 |
|
|
* @param p2 the second polynomial |
201 |
|
|
*/ |
202 |
|
|
template<typename ElemType> |
203 |
|
|
Polynomial<ElemType> operator +(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
204 |
|
|
Polynomial<ElemType> p(p1); |
205 |
|
|
|
206 |
|
|
typename Polynomial<ElemType>::PolynomialIterator i; |
207 |
|
|
typename Polynomial<ElemType>::PolynomialIterator j; |
208 |
|
|
|
209 |
|
|
for (i = p2.begin(); i != p2.end(); ++i) { |
210 |
|
|
j = p.find(i->first); |
211 |
|
|
if (j == p.end()) { |
212 |
|
|
p[j] = i->second; |
213 |
|
|
} else { |
214 |
|
|
j->second += i->second; |
215 |
|
|
} |
216 |
|
|
} |
217 |
|
|
|
218 |
|
|
return p; |
219 |
|
|
|
220 |
|
|
} |
221 |
|
|
|
222 |
|
|
/** |
223 |
|
|
* Generates and returns the difference of two given Polynomials. |
224 |
|
|
* @return |
225 |
|
|
* @param p1 the first polynomial |
226 |
|
|
* @param p2 the second polynomial |
227 |
|
|
*/ |
228 |
|
|
template<typename ElemType> |
229 |
|
|
Polynomial<ElemType> operator -(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
230 |
|
|
Polynomial<ElemType> p(p1); |
231 |
|
|
|
232 |
|
|
typename Polynomial<ElemType>::PolynomialIterator i; |
233 |
|
|
typename Polynomial<ElemType>::PolynomialIterator j; |
234 |
|
|
|
235 |
|
|
for (i = p2.begin(); i != p2.end(); ++i) { |
236 |
|
|
j = p.find(i->first); |
237 |
|
|
if (j == p.end()) { |
238 |
|
|
p[j] = -i->second; |
239 |
|
|
} else { |
240 |
|
|
j->second -= i->second; |
241 |
|
|
} |
242 |
|
|
} |
243 |
|
|
|
244 |
|
|
return p; |
245 |
|
|
|
246 |
|
|
} |
247 |
|
|
|
248 |
|
|
/** |
249 |
|
|
* Tests if two polynomial have the same exponents |
250 |
|
|
* @return true if these all of the exponents in these Polynomial are identical |
251 |
|
|
* @param p1 the first polynomial |
252 |
|
|
* @param p2 the second polynomial |
253 |
|
|
* @note this function does not compare the coefficient |
254 |
|
|
*/ |
255 |
|
|
template<typename ElemType> |
256 |
|
|
bool equal(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
257 |
|
|
|
258 |
|
|
typename Polynomial<ElemType>::PolynomialIterator i; |
259 |
|
|
typename Polynomial<ElemType>::PolynomialIterator j; |
260 |
|
|
|
261 |
|
|
if (p1.size() !== p2.size() ) { |
262 |
|
|
return false; |
263 |
|
|
} |
264 |
|
|
|
265 |
|
|
for (i = p1.begin(), j = p2.begin(); i != p1.end() && j != p2.end(); ++i, ++j) { |
266 |
|
|
if (i->first != j->first) { |
267 |
|
|
return false; |
268 |
|
|
} |
269 |
|
|
} |
270 |
|
|
|
271 |
|
|
return true; |
272 |
|
|
} |
273 |
|
|
|
274 |
|
|
typedef Polynomial<double> DoublePolynomial; |
275 |
|
|
|
276 |
tim |
1744 |
} //end namespace oopse |
277 |
|
|
#endif //MATH_POLYNOMIAL_HPP |