1 /* === S Y N F I G ========================================================= */
2 /*! \file polynomial_root.h
3 ** \brief Polynomial Root Finder Header
5 ** $Id: polynomial_root.h,v 1.1.1.1 2005/01/04 01:23:14 darco Exp $
8 ** Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
10 ** This package is free software; you can redistribute it and/or
11 ** modify it under the terms of the GNU General Public License as
12 ** published by the Free Software Foundation; either version 2 of
13 ** the License, or (at your option) any later version.
15 ** This package 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 GNU
18 ** General Public License for more details.
21 /* ========================================================================= */
23 /* === S T A R T =========================================================== */
25 #ifndef __SYNFIG_POLYNOMIAL_ROOT_H
26 #define __SYNFIG_POLYNOMIAL_ROOT_H
28 /* === H E A D E R S ======================================================= */
33 /* === M A C R O S ========================================================= */
35 /* === T Y P E D E F S ===================================================== */
37 /* === C L A S S E S & S T R U C T S ======================================= */
38 template < typename T = float, typename F = float >
39 class Polynomial : public std::vector<T> //a0 + a1x + a2x^2 + ... + anx^n
43 //Will maintain all lower constants
44 void degree(unsigned int d, const T & def = (T)0) { resize(d+1,def); }
45 unsigned int degree()const { return size() - 1; }
47 const Polynomial & operator+=(const Polynomial &p)
50 resize(p.size(), (T)0);
52 for(int i = 0; i < p.size(); ++i)
59 const Polynomial & operator-=(const Polynomial &p)
62 resize(p.size(), (T)0);
64 for(int i = 0; i < p.size(); ++i)
71 const Polynomial & operator*=(const Polynomial &p)
80 std::vector<T> nc(*this);
82 //in place for constant stuff
83 for(i = 0; i < nc.size(); ++i)
88 if(p.size() < 2) return *this;
90 resize(size() + p.degree());
91 for(int i = 0; i < nc.size(); ++i)
93 for(int j = 1; j < p.size(); ++j)
95 nc[i+j] += nc[i]*p[j];
105 std::vector< std::complex<float> > workcoefs;
109 std::vector< std::complex<float> > coefs; //the number of coefficients determines the degree of polynomial
111 std::vector< std::complex<float> > roots;
113 void find_all_roots(bool polish);
118 /* === E N D =============================================================== */