1 /* === S Y N F I G ========================================================= */
2 /*! \file polynomial_root.h
3 ** \brief Polynomial Root Finder Header
8 ** Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
9 ** Copyright (c) 2007 Chris Moore
11 ** This package is free software; you can redistribute it and/or
12 ** modify it under the terms of the GNU General Public License as
13 ** published by the Free Software Foundation; either version 2 of
14 ** the License, or (at your option) any later version.
16 ** This package is distributed in the hope that it will be useful,
17 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
18 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 ** General Public License for more details.
22 /* ========================================================================= */
24 /* === S T A R T =========================================================== */
26 #ifndef __SYNFIG_POLYNOMIAL_ROOT_H
27 #define __SYNFIG_POLYNOMIAL_ROOT_H
29 /* === H E A D E R S ======================================================= */
34 /* === M A C R O S ========================================================= */
36 /* === T Y P E D E F S ===================================================== */
38 /* === C L A S S E S & S T R U C T S ======================================= */
39 template < typename T = float, typename F = float >
40 class Polynomial : public std::vector<T> //a0 + a1x + a2x^2 + ... + anx^n
44 //Will maintain all lower constants
45 void degree(unsigned int d, const T & def = (T)0) { resize(d+1,def); }
46 unsigned int degree()const { return this->size() - 1; }
48 const Polynomial & operator+=(const Polynomial &p)
50 if(p.size() > this->size())
51 resize(p.size(), (T)0);
53 for(int i = 0; i < p.size(); ++i)
60 const Polynomial & operator-=(const Polynomial &p)
62 if(p.size() > this->size())
63 resize(p.size(), (T)0);
65 for(int i = 0; i < p.size(); ++i)
72 const Polynomial & operator*=(const Polynomial &p)
81 std::vector<T> nc(*this);
83 //in place for constant stuff
84 for(i = 0; i < nc.size(); ++i)
89 if(p.size() < 2) return *this;
91 this->resize(this->size() + p.degree());
92 for(int i = 0; i < nc.size(); ++i)
94 for(int j = 1; j < p.size(); ++j)
96 nc[i+j] += nc[i]*p[j];
106 std::vector< std::complex<float> > workcoefs;
110 std::vector< std::complex<float> > coefs; //the number of coefficients determines the degree of polynomial
112 std::vector< std::complex<float> > roots;
114 void find_all_roots(bool polish);
119 /* === E N D =============================================================== */