| Dense univariate polynomials |
A dense univariate polynomial f = f0 + f1 x+ ··· + fd
xd is represented by an array of coefficients [f0,..., fd].
All its coefficients are stored. It is assumed here that the coefficient ring
has the basic arithmetic operations defined in section X.
1 Implementation
template< class R>
struct UPolyDense
Univariate polynomials, with a dense representation given by the container
R. Forward and backward iterators are provided, as well as the arithmetic
operations +,-,+=,-=,*,*=,/, /=, % ,% =. The operators % and /
correspond respectively to the quotient and remainder computation in the
Euclidean division.
The operator()(const C &) correspond the evaluation of the polynomial.
The function UPOLYNOMIAL::checkdegree is called at the end of an
arithmetic operation, to reajust the variable degree_, if it exists
in the container R.
UPolyDense
{
typedef typename R::value_type value_type;
typedef typename R::size_type size_type;
typedef R rep_type;
typedef typename R::iterator iterator;
typedef typename R::reverse_iterator reverse_iterator;
typedef UPolyDense self_t;
R rep;
UPolyDense() : rep() {}
UPolyDense(const R & r) : rep(r) {}
UPolyDense(const int n);
UPolyDense(size_type n, Alloc A) {VECTOR::reserve(this->rep,n);}
UPolyDense(value_type c, size_type n);
UPolyDense(size_type n, value_type * t): rep(n,t) {}
UPolyDense(iterator b, iterator e): rep(b,e) {}
UPolyDense(char *);
UPolyDense(const self_t & P) : rep(P.rep) {TRACE(P);}
template
UPolyDense(const VAL & P) {assign(*this,P.rep);}
iterator begin() {return rep.begin();}
iterator begin() const {return rep.begin();}
iterator end() {return rep.end();}
iterator end() const {return rep.end();}
reverse_iterator rbegin() {return rep.rbegin();}
reverse_iterator rbegin() const {return rep.rbegin();}
reverse_iterator rend() {return rep.rend();}
reverse_iterator rend() const {return rep.rend();}
self_t & operator=(const self_t & P)
{TRACE(P);rep=P.rep; return *this;}
template
self_t & operator =(const VAL & M)
{assign(*this,M.rep);return *this;}
bool operator==(int n) const;
bool operator!=(int n) const {return !(*this==n);}
self_t & operator+= (const self_t & P);
self_t & operator-= (const self_t & P);
self_t & operator*= (const self_t & P);
self_t & operator*= (const value_type & c);
self_t & operator/= (const self_t & Q);
self_t & operator/= (const value_type & c);
self_t & operator%= (const self_t & Q);
int degree() { return (Degree(rep));}
int degree() const { return (Degree(rep));}
size_type size() const { return (rep.size());}
inline value_type & operator[] (size_type i)
{
if(i< max((size_type)(degree()+1),(size_type)0))
return rep[i]; else return *new value_type(0);return rep[i];
}
inline value_type operator[] (size_type i) const
{
if(i< max((size_type)(degree()+1),(size_type)0))
return rep[i]; else return 0;
}
template T operator()(const T & c);
};
template < class R>
int Degree(const UPolyDense< R> & p)
Output the degree, that is the index of the last non-zero
coefficient.
template < class R>
inline VAL< OP< '+',UPolyDense< R> ,UPolyDense< R> > >
operator+(const UPolyDense< R> & a, const UPolyDense< R> & b)
Addition of polynomials.
template < class R>
inline VAL< OP< '-',UPolyDense< R> ,UPolyDense< R> > >
operator-(const UPolyDense< R> & a, const UPolyDense< R> & b)
Substraction of polynomials.
template < class R> inline
VAL< OP< '*',UPolyDense< R> ,UPolyDense< R> > >
operator*(const UPolyDense< R> & a, const UPolyDense< R> & b)
Product of polynomials.
template < class R> inline
VAL< OP< '.',UPolyDense< R> ,typename UPolyDense< R> ::value_type> >
operator*(const UPolyDense< R> & a, const typename UPolyDense< R> ::value_type & c)
Scalar multiplication.
template < class R> inline
VAL< OP< '/',UPolyDense< R> ,UPolyDense< R> > >
operator/(const UPolyDense< R> & a, const UPolyDense< R> & b)
Quotient of polynomials.
template < class R> inline
VAL< OP< '% ',UPolyDense< R> ,UPolyDense< R> > >
operator% (const UPolyDense< R> & a, const UPolyDense< R> & b)
Remainder of polynomials.
template < class R> inline
VAL< OP< '^',UPolyDense< R> ,unsigned int> >
operator^(const UPolyDense< R> & a, const unsigned int & n)
Power of a polynomial.
template < class R> inline
ostream & operator< < (ostream & os, const UPolyDense< R> & p)
Output operator.
template < class R> inline
istream & operator> > (istream & is, UPolyDense< R> & P)
Input operator. The variable is x or x0. Ended by a ;.
template < class R>
UPolyDense< R> ::UPolyDense(char * s)
Constructor of a univariate polynomial from a string, ending by ;.
Example: UPolyDense< R> ("x^2+x^3-1;").
template< class R> inline
bool UPolyDense< R> ::operator==(int n) const
Equality test to 0,1,...
template< class R> inline
UPolyDense< R> & UPolyDense< R> ::operator/= (const typename UPolyDense< R> ::value_type & c)
Inplace division by a scalar.
template < class R> inline
UPolyDense< R> & UPolyDense< R> ::operator /= (const UPolyDense< R> & Q)
Inplace quotient in the Euclidian division.
template < class R> inline
UPolyDense< R> & UPolyDense< R> ::operator % = (const UPolyDense< R> & Q)
Inplace remainder in the Euclidian division.
template < class R> template< class T> inline
T UPolyDense< R> ::operator()(const T & c)
Evaluation of a polynomial, using Horner scheme. The output value is
specified by the type of c.
2 Containers for univariate polynomials
The container R should provide the following signatures:
typename R::value_type coeff_t;
typedef typename R::size_type;
typedef typename R::iterator;
R(size_type s, Alloc);
R(size_type s, C *t);
R(iterator b, iterator e);
void R::reserve(size_type n);
iterator R::begin() ;
iterator R::begin() const ;
iterator R::end() ;
iterator R::end() const ;
iterator R::rbegin() ;
iterator R::rbegin() const;
iterator R::rend() ;
iterator R::rend() const;
size_type R::size();
int Degree(const R &);
The container upar (X) and vector of the
stl can be used here.
3 Example of container
template < class C>
struct upar : public array1d< C>
upar< C> , univariate polynomials representation, as a subclass of
array1d< C> .
{
typedef C* iterator;
typedef reverse_iterator const_reverse_iterator;
typedef reverse_iterator reverse_iterator;
int degree_;
upar(): array1d(), degree_(-1) {}
upar(size_type s, Alloc): array1d(s), degree_(s-1) {}
upar(size_type s, C *t): array1d(s,t), degree_(s-1)
{UPOLYNOMIAL::checkdegree(*this);}
upar(C* b, C *e): array1d(b,e)
{degree_=size_-1;UPOLYNOMIAL::checkdegree(*this);}
upar(const upar & p): array1d(p), degree_(p.degree_) {}
void reserve(size_type n)
{this->array1d::reserve(n);degree_=n-1;}
iterator begin() { return iterator(tab_); }
iterator begin() const { return iterator(tab_); }
iterator end() { return iterator(tab_+degree_+1); }
iterator end() const { return iterator(tab_+degree_+1); }
reverse_iterator rbegin() { return reverse_iterator(tab_+degree_+1); }
reverse_iterator rbegin() const{ return reverse_iterator(tab_+degree_+1); }
reverse_iterator rend() { return reverse_iterator(tab_); }
reverse_iterator rend() const{ return reverse_iterator(tab_); }
upar & operator=(const upar & v)
{this->array1d::operator=(v); degree_=v.degree_; return *this;}
upar & operator=(upar * r)
{this->array1d::operator=(r); degree_ = r.degree_;return *this;}
};
4 Example
cout<<"p0 ="<<p0<<", p1 ="<<p1<<endl;
p0 =(1)*x2+(1)*x+(1), p1 =(1)*x3+(-1)*x2+(2)
cout<<"p0((0,1)) ="<<p0(complex<double>(0,1))<<endl;
p0((0,1)) =-1
cout<<"p1(1) ="<<UPOLYNOMIAL::eval(p1.rep,1.)<<endl;
p1(1) =2
Pol p2(p0+p1); cout<<p2<<endl;
(1)*x3+(1)*x+(3)
p2 =p0-p1; cout<<p2<<endl;
(-1)*x3+(2)*x2+(1)*x+(-1)
p2=p0*p1; cout<<p2<<endl;
(1)*x5+(1)*x2+(2)*x+(2)
p2+=p1-p0; cout<<p2<<endl;
(1)*x5+(1)*x3+(-1)*x2+(1)*x+(3)
p2=p1; p2*=p0; cout<<p2<<endl;
(1)*x5+(1)*x2+(2)*x+(2)
p2+=(p1-p0)*(p1-p0*2);cout<<p2<<endl;
(1)*x6+(-4)*x5+(3)*x4+(8)*x3
+(2)
p2=p0-(p0+p1); cout<<p2<<endl;
(-1)*x3+(1)*x2+(-2)
p2=p0 +p1*2; cout<<p2<<endl;
(2)*x3+(-1)*x2+(1)*x+(5)
p2=(p1+p0)*(p1-p0*2); cout<<p2<<endl;
(1)*x6+(-3)*x5+(-1)*x4+(-11)*x2+(-6)*x
//Quotient in the Euclidean division
p2=p1/p0; cout<<p2<<endl;
(1)*x+(-2)
//Remainder in the Euclidean division
p2=p1%p0; cout<<p2<<endl;
(1)*x+(4)
p1%=p0; cout<<p1<<endl;
(1)*x+(4)
}