1[section:polynomials Polynomials] 2 3[h4 Synopsis] 4 5`` 6#include <boost/math/tools/polynomial.hpp> 7`` 8 9 namespace boost { namespace math { 10 namespace tools { 11 12 template <class T> 13 class polynomial 14 { 15 public: 16 // typedefs: 17 typedef typename std::vector<T>::value_type value_type; 18 typedef typename std::vector<T>::size_type size_type; 19 20 // construct: 21 polynomial(){} 22 template <class U> 23 polynomial(const U* data, unsigned order); 24 template <class I> 25 polynomial(I first, I last); 26 template <class U> 27 explicit polynomial(const U& point, 28 typename boost::enable_if<boost::is_convertible<U, T> >::type* = 0); 29 template <class Range> 30 explicit polynomial(const Range& r, 31 typename boost::enable_if<boost::math::tools::detail::is_const_iterable<Range> >::type* = 0); // C++14 32 polynomial(std::initializer_list<T> l); // C++11 33 34 polynomial(std::vector<T>&& p); 35 36 // access: 37 size_type size()const; 38 size_type degree()const; 39 value_type& operator[](size_type i); 40 const value_type& operator[](size_type i)const; 41 std::vector<T> const& data() const; 42 std::vector<T>& data(); 43 explicit operator bool() const; 44 45 polynomial<T> prime() const; 46 47 polynomial<T> integrate() const; 48 49 T operator()(T z) const; 50 51 52 53 // modify: 54 void set_zero(); 55 56 // operators: 57 template <class U> 58 polynomial& operator +=(const U& value); 59 template <class U> 60 polynomial& operator -=(const U& value); 61 template <class U> 62 polynomial& operator *=(const U& value); 63 template <class U> 64 polynomial& operator /=(const U& value); 65 template <class U> 66 polynomial& operator %=(const U& value); 67 template <class U> 68 polynomial& operator +=(const polynomial<U>& value); 69 template <class U> 70 polynomial& operator -=(const polynomial<U>& value); 71 template <class U> 72 polynomial& operator *=(const polynomial<U>& value); 73 template <class U> 74 polynomial& operator /=(const polynomial<U>& value); 75 template <class U> 76 polynomial& operator %=(const polynomial<U>& value); 77 }; 78 79 template <class T> 80 polynomial<T> operator + (const polynomial<T>& a, const polynomial<T>& b); 81 template <class T> 82 polynomial<T> operator - (const polynomial<T>& a, const polynomial<T>& b); 83 template <class T> 84 polynomial<T> operator * (const polynomial<T>& a, const polynomial<T>& b); 85 template <class T> 86 polynomial<T> operator / (const polynomial<T>& a, const polynomial<T>& b); 87 template <class T> 88 polynomial<T> operator % (const polynomial<T>& a, const polynomial<T>& b); 89 90 template <class T, class U> 91 polynomial<T> operator + (const polynomial<T>& a, const U& b); 92 template <class T, class U> 93 polynomial<T> operator - (const polynomial<T>& a, const U& b); 94 template <class T, class U> 95 polynomial<T> operator * (const polynomial<T>& a, const U& b); 96 template <class T, class U> 97 polynomial<T> operator / (const polynomial<T>& a, const U& b); 98 template <class T, class U> 99 polynomial<T> operator % (const polynomial<T>& a, const U& b); 100 101 template <class U, class T> 102 polynomial<T> operator + (const U& a, const polynomial<T>& b); 103 template <class U, class T> 104 polynomial<T> operator - (const U& a, const polynomial<T>& b); 105 template <class U, class T> 106 polynomial<T> operator * (const U& a, const polynomial<T>& b); 107 108 template <class T> 109 polynomial<T> operator - (const polynomial<T>& a); 110 111 template <class T> 112 polynomial<T> operator >>= (const U& a); 113 template <class T> 114 polynomial<T> operator >> (polynomial<T> const &a, const U& b); 115 template <class T> 116 polynomial<T> operator <<= (const U& a); 117 template <class T> 118 polynomial<T> operator << (polynomial<T> const &a, const U& b); 119 120 template <class T> 121 bool operator == (const polynomial<T> &a, const polynomial<T> &b); 122 template <class T> 123 bool operator != (const polynomial<T> &a, const polynomial<T> &b); 124 125 template <class T> 126 polynomial<T> pow(polynomial<T> base, int exp); 127 128 template <class charT, class traits, class T> 129 std::basic_ostream<charT, traits>& operator << 130 (std::basic_ostream<charT, traits>& os, const polynomial<T>& poly); 131 132 template <typename T> 133 std::pair< polynomial<T>, polynomial<T> > 134 quotient_remainder(const polynomial<T>& a, const polynomial<T>& b); 135 136 } // namespace tools 137 }} // namespace boost { namespace math 138 139[h4 Description] 140 141This is a somewhat trivial class for polynomial manipulation. 142 143See 144 145* [@https://en.wikipedia.org/wiki/Polynomial Polynomial] and 146* Donald E. Knuth, The Art of Computer Programming: Volume 2, Third edition, (1998) 147Chapter 4.6.1, Algorithm D: Division of polynomials over a field. 148 149Implementation is currently of the "naive" variety, with [bigo](N[super 2]) 150multiplication, for example. This class should not be used in 151high-performance computing environments: it is intended for the 152simple manipulation of small polynomials, typically generated 153for special function approximation. 154 155It does has division for polynomials over a [@https://en.wikipedia.org/wiki/Field_%28mathematics%29 field] 156(here floating point, complex, etc) 157and over a unique factorization domain (integers). 158Division of polynomials over a field is compatible with 159[@https://en.wikipedia.org/wiki/Euclidean_algorithm Euclidean GCD]. 160 161Division of polynomials over a UFD is compatible with the subresultant algorithm for GCD (implemented as subresultant_gcd), but a serious word of warning is required: the intermediate value swell of that algorithm will cause single-precision integral types to overflow very easily. So although the algorithm will work on single-precision integral types, an overload of the gcd function is only provided for polynomials with multi-precision integral types, to prevent nasty surprises. This is done somewhat crudely by disabling the overload for non-POD integral types. 162 163Advanced manipulations: the FFT, factorisation etc are 164not currently provided. Submissions for these are of course welcome :-) 165 166[h4:polynomial_examples Polynomial Arithmetic Examples] 167 168[import ../../example/polynomial_arithmetic.cpp] 169 170[polynomial_arithmetic_0] 171[polynomial_arithmetic_1] 172 173[polynomial_arithmetic_2] 174for output: 175[polynomial_output_1] 176 177[polynomial_arithmetic_3] 178for output 179[polynomial_output_2] 180 181[h5 Division, Quotient and Remainder] 182[polynomial_arithmetic_4] 183 184The source code is at [@../../example/polynomial_arithmetic.cpp polynomial_arithmetic.cpp] 185 186[endsect] [/section:polynomials Polynomials] 187 188[/ 189 Copyright 2006 John Maddock and Paul A. Bristow. 190 Copyright 2015 Jeremy William Murphy. 191 192 Distributed under the Boost Software License, Version 1.0. 193 (See accompanying file LICENSE_1_0.txt or copy at 194 http://www.boost.org/LICENSE_1_0.txt). 195] 196