Quotient of univariate polynomials


This class represents dense univariate polynomial modulo a fixed polynomial p, that is elements in A= K[x]/(p). If d is the degree of p, an element is represented by a vector of size d, corresponding to its coefficients in the Horner basis:
f = f0   H0(x) + f1   H1(x) + ··· + fd-1  Hd-1(x).
where
Hi(x)= p+(x-d+i  p)
is the ith Horner polynomial of degree i. In this basis, the square of a polynomial can be performed with two convolutions (eg. based on FFT (X)). See [Card95] for more details.



1  Implementation

upoly/UPolyQuot.H

template< class R>  struct UPolyQuot : public UPolyDense< R> 
Class of polynomials modulo a polynomial UPolyQuot< R> ::poly. Elements are represented in the Horner basis. All the arithmetic operations are performed in this basis. Only the display of a polynomial needs a change to the monomial basis. 
{

  static R poly;

  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 iterator_r;
  typedef UPolyQuot                 self_t;

  UPolyQuot() {}
  UPolyQuot(const R & r): UPolyDense(r) {}
  UPolyQuot(int n): UPolyDense(n){}
  UPolyQuot(size_type n, Alloc A): UPolyDense(n,A){}
  UPolyQuot(size_type n, value_type * t, bool mbs = false):  
    UPolyDense(n,t) {} //{UPOLYNOMIAL::montohorn(*this,*this,mbs);}
  UPolyQuot(iterator b, iterator e, bool mbs =true): 
    UPolyDense(b,e) {}

  //  UPolyQuot(const char * str): UPolyDense(str) {} 
  UPolyQuot(const UPolyQuot & P):  UPolyDense(P.rep) {}
  template 
  UPolyQuot(const VAL & P) {assign(*this,P.rep);}
  
  // Returns the quotient dimension 
  static size_type dim() {return Degree(poly);}

  UPolyQuot & operator=(const UPolyQuot & P) 
    {rep=P.rep; return *this;} 

  template 
  UPolyQuot & operator=(const VAL & P)
    {assign(*this,P.rep); return *this;}
};


template < class R>  inline VAL< OP< '+',UPolyQuot< R> ,UPolyQuot< R>  >  >  operator+(const UPolyQuot< R>  & a, const UPolyQuot< R>  & b)
Addition operator.

template < class R>  inline VAL< OP< '-',UPolyQuot< R> ,UPolyQuot< R>  >  >  operator-(const UPolyQuot< R>  & a, const UPolyQuot< R>  & b)
Substraction operator.

template < class R>  inline VAL< OP< '-',UPolyQuot< R> ,UPolyQuot< R>  >  >  operator-(const UPolyQuot< R>  & a)
Unary susbtraction operator.

template < class R>  inline VAL< OP< '*',UPolyQuot< R> ,UPolyQuot< R>  >  >  operator*(const UPolyQuot< R>  & a, const UPolyQuot< R>  & b)
Product of polynomials.

template < class R>  inline VAL< OP< '.',UPolyQuot< R> ,typename UPolyQuot< R> ::value_type>  >  operator*(const UPolyQuot< R>  & a, const typename UPolyQuot< R> ::value_type & c)
Scalar multiplication.

template < class R>  inline VAL< OP< '/',UPolyQuot< R> ,UPolyQuot< R>  >  >  operator/(const UPolyQuot< R>  & a, const UPolyQuot< R>  & b)
Quotient of polynomials.

template < class R>  inline ostream & operator< < (ostream & os, const UPolyQuot< R>  & p)
Output operator.

template < class R>  inline istream & operator> > (istream & is, UPolyQuot< R>  & P)
Input operator. The variable is x or x0. Ended by ;.

upoly/UPolyQuot.C

template < class R>  void UPOLYNOMIAL::quo_square(R & x,const R & f)
Square f in A and put it x.

template < class R>  void UPOLYNOMIAL::quo_mult(R & x, const R & a, const R& b)
Multiply a by b in A and put it x.

template < class R>  void UPOLYNOMIAL::montohorn(R &x, const R & y, bool MtoH)
Express the polynomial x from a basis (Monomial or Horner) in the other basis. From the Horner basis to the monomial basis (MtoH=false), the Bezoutian matrix B1,p is used. For the other case (MtoH=true), the matrix Htp is used.



2  Containers for quotiented polynomials

The container R should provide the same signatures as for dense univariate polynomials. It can be upar (X) for instance. The container vector of the stl can also be used.



3  Example

#include "upoly.H"

typedef double C;
typedef UPolyQuot<upar<C> > Pol;

int main (int argc, char **argv)
{

  // We define the quotient by the following polynomial
  C u[]={-3,-2,-1,1};
  Pol::poly= upar<C>(4,u);
  cout<<UPolyDense<upar<C> >(Pol::poly)<<endl;
(1)*x3+(-1)*x2+(-2)*x+(-3)

  // Here are the polynomials
  C u1[]={0,0,1,0,0};
  Pol p0(u1,u1+3), p1(u1+1,u1+4), p2;

  cout<<"p0 ="<<p0<<endl;
p0 =(1)*x2+(-1)*x+(-2)
 
  cout<<"p1 ="<<p1<<endl;
p1 =(1)*x+(-1)
 

  p2 = p0+p1; cout<<p2<<endl;
(1)*x2+(-3)
  p2 = p0*p0; cout<<p2<<endl;
(-2)*x2+(5)*x+(1)
  p2 = p0*p1; cout<<p2<<endl;
(-1)*x2+(1)*x+(5)

}