KrisLibrary  1.0.0
Polynomial.h
1 #ifndef SPLINE_POLYNOMIAL_H
2 #define SPLINE_POLYNOMIAL_H
3 
4 #include <KrisLibrary/Logger.h>
5 #include <vector>
6 #include <iostream>
7 #include <assert.h>
8 
9 namespace Spline {
10 
13 template <class T=double>
15 {
16  public:
17  std::vector<T> coef;
18 
22  Polynomial(T c);
24  Polynomial(const std::vector<T>& _coef);
26  Polynomial(const Polynomial<T>& p);
27 
29  template <class T2>
31  {
32  coef.resize(p.coef.size());
33  for(size_t i=0;i<coef.size();i++)
34  coef[i] = T(p.coef[i]);
35  }
36 
37  void Resize(size_t s);
39  size_t Size() const;
41  int Degree() const;
42 
44  void SetCoef(size_t i,T value);
46  T GetCoef(size_t i) const;
47 
49  std::ostream& operator << (std::ostream& out) const;
50 
52  T Evaluate (T x) const;
54  Polynomial<T> Evaluate(const Polynomial<T>& x) const;
55 
57  T Derivative (T x) const;
59  T Derivative (T x,int n) const;
60 
63 
66 
69  Polynomial<T> Differentiate(int n) const;
70 
72  inline T operator () (T x) const { return Evaluate(x); }
74  inline Polynomial<T> operator () (const Polynomial<T>& x) const { return Evaluate(x); }
75 
77  void operator += (T val);
79  void operator -= (T val);
81  void operator *= (T b);
83  void operator /= (T b);
84 
86  void operator += (const Polynomial<T>& b);
88  void operator -= (const Polynomial<T>& b);
90  void operator *= (const Polynomial<T>& b);
91 };
92 
93 
94 //unary -
95 template <class T>
96 inline Polynomial<T> operator - (const Polynomial<T>& a)
97 {
98  Polynomial<T> res=a;
99  res *= -1.0;
100  return res;
101 }
102 
103 template <class T>
104 inline Polynomial<T> operator + (const Polynomial<T>& a, T b)
105 {
106  Polynomial<T> res=a;
107  res += b;
108  return res;
109 }
110 
111 template <class T>
112 inline Polynomial<T> operator - (const Polynomial<T>& a, T b)
113 {
114  Polynomial<T> res=a;
115  res -= b;
116  return res;
117 }
118 
119 template <class T>
120 inline Polynomial<T> operator * (const Polynomial<T>& a, T b)
121 {
122  Polynomial<T> res=a;
123  res *= b;
124  return res;
125 }
126 
127 template <class T>
128 inline Polynomial<T> operator / (const Polynomial<T>& a, T b)
129 {
130  Polynomial<T> res=a;
131  res /= b;
132  return res;
133 }
134 
135 
136 template <class T>
137 inline Polynomial<T> operator + (T a,const Polynomial<T>& b)
138 {
139  Polynomial<T> res=b;
140  res += a;
141  return res;
142 }
143 
144 template <class T>
145 inline Polynomial<T> operator - (T a,const Polynomial<T>& b)
146 {
147  Polynomial<T> res=a;
148  res -= b;
149  return res;
150 }
151 
152 template <class T>
153 inline Polynomial<T> operator * (T a,const Polynomial<T>& b)
154 {
155  Polynomial<T> res=b;
156  res *= a;
157  return res;
158 }
159 
160 //polynomial operations
161 template <class T>
162 inline Polynomial<T> operator + (const Polynomial<T>& a, const Polynomial<T>& b)
163 {
164  Polynomial<T> res=a;
165  res += b;
166  return res;
167 }
168 
169 template <class T>
170 inline Polynomial<T> operator - (const Polynomial<T>& a, const Polynomial<T>& b)
171 {
172  Polynomial<T> res=a;
173  res -= b;
174  return res;
175 }
176 
177 template <class T>
178 inline Polynomial<T> operator * (const Polynomial<T>& a, const Polynomial<T>& b)
179 {
180  Polynomial<T> res=a;
181  res *= b;
182  return res;
183 }
184 
185 
186 
187 
188 template <class T>
190 {
191  coef.resize(1);
192  coef[0] = c;
193 }
194 template <class T>
195 Polynomial<T>::Polynomial(const std::vector<T>& _coef)
196 :coef(_coef)
197 {}
198 
199 template <class T>
201 :coef(p.coef)
202 {}
203 
204 template <class T>
205 void Polynomial<T>::Resize(size_t s) { coef.resize(s,T(0)); }
206 
207 template <class T>
208 size_t Polynomial<T>::Size() const { return coef.size(); }
209 
210 template <class T>
212 {
213  for(size_t i=0;i<coef.size();i++)
214  if(coef[coef.size()-1-i]!=T(0))
215  return int(coef.size()-1-i);
216  return 0;
217 }
218 
219 template <class T>
220 void Polynomial<T>::SetCoef(size_t i,T value)
221 {
222  if(i >= coef.size())
223  Resize(i+1);
224  coef[i] = value;
225 }
226 
227 template <class T>
228 T Polynomial<T>::GetCoef(size_t i) const
229 {
230  if(i >= coef.size()) return T(0);
231  return coef[i];
232 }
233 
234 template <class T>
235 std::ostream& Polynomial<T>::operator << (std::ostream& out) const
236 {
237  for(size_t i=0;i<coef.size();i++) {
238  out << coef[coef.size()-1-i] << "x^" << coef.size()-1-i;
239  if(i+1 != coef.size())
240 out << " + ";
241  }
242  return out;
243 }
244 
245 template <class T>
247 {
248  //horner's rule
249  T s = coef[coef.size()-1];
250  for (size_t i=1;i<coef.size();i++)
251  s = coef[coef.size()-i-1] + ( x * s );
252  return s;
253 }
254 
255 template <class T>
257 {
258  Polynomial<T> s(coef[coef.size()-1]);
259  for (size_t i=1;i<coef.size();i++) {
260  s = Polynomial<T>(coef[coef.size()-i-1]) + ( x * s );
261  }
262  return s;
263 }
264 
265 template <class T>
267 {
268  T s = 0;
269  T xi = 1;
270  for (size_t i=1;i<coef.size();i++) {
271  s += T(i)*coef[i]*xi;
272  xi *= x;
273  }
274  return s;
275 }
276 
277 template <class T>
278 T Polynomial<T>::Derivative (T x,int n) const
279 {
280  assert(n >= 0);
281  if(n == 0) return Evaluate(x);
282  else if(n == 1) return Derivative(x);
283  return Differentiate(n).Evaluate(x);
284 }
285 
286 template <class T>
288 {
289  if(Size() <= 1) {
290  return Polynomial<T>(0);
291  }
292 
293  Polynomial<T> deriv;
294  deriv.coef.resize(coef.size()-1);
295  for(size_t i=0;i+1<coef.size();i++)
296  deriv.coef[i] = (T(i+1))*coef[i+1];
297  return deriv;
298 }
299 
300 template <class T>
302 {
303  if(Size() <= 1) {
304  return Polynomial<T>(0);
305  }
306 
307  Polynomial<T> anti;
308  anti.coef.resize(coef.size()+1);
309  for(size_t i=0;i<coef.size();i++)
310  anti.coef[i+1] = coef[i]/(T(i+1));
311  return anti;
312 }
313 
314 template <class T>
316 {
317  if(n < 0) {
318  if(n == -1) return AntiDifferentiate();
319  else return Differentiate(n+1).AntiDifferentiate();
320  }
321  else {
322  if(n >= (int)Size()) return Polynomial<T>(0);
323  if(n == 0) return *this;
324  if(n == 1) return Differentiate();
325  return Differentiate(n-1).Differentiate();
326  }
327 }
328 
329 template <class T>
331 {
332  if(coef.empty()) Resize(1);
333  for(size_t i=0;i<coef.size();i++) coef[i] += val;
334 }
335 
336 template <class T>
338 {
339  if(coef.empty()) Resize(1);
340  for(size_t i=0;i<coef.size();i++) coef[i] -= val;
341 }
342 
343 template <class T>
345 {
346  for (size_t i=0;i<coef.size();i++)
347 coef[i] *= b;
348 }
349 
350 template <class T>
352 {
353  for (size_t i=0;i<coef.size();i++)
354 coef[i] /= b;
355 }
356 
357 template <class T>
359 {
360  if(b.coef.size() > coef.size()) Resize(b.Size());
361  for(size_t i=0;i<b.coef.size();i++) coef[i] += b.coef[i];
362 }
363 
364 template <class T>
366 {
367  if(b.coef.size() > coef.size()) Resize(b.Size());
368  for(size_t i=0;i<b.coef.size();i++) coef[i] -= b.coef[i];
369 }
370 
371 template <class T>
373 {
374  std::vector<T> newCoef(Degree()+b.Degree()+1,T(0));
375  for (size_t i=0;i<coef.size();i++)
376  for (size_t j=0;j<b.coef.size();j++)
377 newCoef[i+j] += (coef[i] * b.coef[j]);
378  swap(coef,newCoef);
379 }
380 
381 
382 } //namespace Spline
383 
384 #endif
A simple polynomial class, p(x) = sum_{i=0}^n coef[i]*x^i.
Definition: Polynomial.h:14
void SetCoef(size_t i, T value)
Sets coefficient i. Automatically resizes the coefficient vector.
Definition: Polynomial.h:220
Polynomial()
Initializes to the 0 polynomial.
Definition: Polynomial.h:20
std::ostream & operator<<(std::ostream &out) const
Pretty-prints this.
Definition: Polynomial.h:235
void operator+=(T val)
Adds a constant offset.
Definition: Polynomial.h:330
T GetCoef(size_t i) const
Gets coefficient i. If i is out of bounds of the coefficient vector, returns 0.
Definition: Polynomial.h:228
Polynomial< T > Differentiate() const
Returns the derivative of this polynomial.
Definition: Polynomial.h:287
T operator()(T x) const
The operator (x) is equivalent to evaluation.
Definition: Polynomial.h:72
Polynomial< T > AntiDifferentiate() const
Returns the antiderivative of this polynomial.
Definition: Polynomial.h:301
Definition: BSpline.cpp:9
void operator*=(T b)
Scales by a constant.
Definition: Polynomial.h:344
void operator-=(T val)
Subtracts a constant offset.
Definition: Polynomial.h:337
size_t Size() const
Size is the size of the coefficient vector. Similar to Degree but disregarding leading 0 coefficients...
Definition: Polynomial.h:208
The logging system used in KrisLibrary.
T Derivative(T x) const
Evaluates the derivative at x.
Definition: Polynomial.h:266
T Evaluate(T x) const
Evaluates the polynomial at x.
Definition: Polynomial.h:246
Polynomial(const Polynomial< T2 > &p)
cast constructor
Definition: Polynomial.h:30
int Degree() const
The degree of the polynomial. Correctly handles leading 0 coefficients.
Definition: Polynomial.h:211
void operator/=(T b)
Divides by a constant (if b is 0, unexpected results will hold)
Definition: Polynomial.h:351