zz_px.h

数值算法库for Windows

#ifndef NTL_ZZ_pX__H
#define NTL_ZZ_pX__H

#include <NTL/vector.h>
#include <NTL/ZZ_p.h>
#include <NTL/vec_ZZ.h>
#include <NTL/vec_ZZ_p.h>
#include <NTL/FFT.h>

NTL_OPEN_NNS




// some cross-over points
// macros are used so as to be consistent with zz_pX 

#define NTL_ZZ_pX_FFT_CROSSOVER (20)  
#define NTL_ZZ_pX_NEWTON_CROSSOVER (45)
#define NTL_ZZ_pX_DIV_CROSSOVER (90)
#define NTL_ZZ_pX_HalfGCD_CROSSOVER (25)
#define NTL_ZZ_pX_GCD_CROSSOVER (180)
#define NTL_ZZ_pX_BERMASS_CROSSOVER (90)
#define NTL_ZZ_pX_TRACE_CROSSOVER (90)



/************************************************************

                         ZZ_pX

The class ZZ_pX implements polynomial arithmetic modulo p.
Polynomials are represented as vec_ZZ_p's.
If f is a ZZ_pX, then f.rep is a vec_ZZ_p.
The zero polynomial is represented as a zero length vector.
Otherwise. f.rep[0] is the constant-term, and f.rep[f.rep.length()-1]
is the leading coefficient, which is always non-zero.
The member f.rep is public, so the vector representation is fully
accessible.
Use the member function normalize() to strip leading zeros.

**************************************************************/


class ZZ_pX {

public:

typedef vec_ZZ_p VectorBaseType; 


vec_ZZ_p rep;


/***************************************************************

          Constructors, Destructors, and Assignment

****************************************************************/


ZZ_pX()
//  initial value 0

   { }


ZZ_pX(INIT_SIZE_TYPE, long n) { rep.SetMaxLength(n); }

ZZ_pX(const ZZ_pX& a) : rep(a.rep) { }
// initial value is a


ZZ_pX& operator=(const ZZ_pX& a) 
   { rep = a.rep; return *this; }

~ZZ_pX() { }

void normalize();
// strip leading zeros

void SetMaxLength(long n) 
// pre-allocate space for n coefficients.
// Value is unchanged

   { rep.SetMaxLength(n); }


void kill() 
// free space held by this polynomial.  Value becomes 0.

   { rep.kill(); }

static const ZZ_pX& zero();


ZZ_pX(ZZ_pX& x, INIT_TRANS_TYPE) : rep(x.rep, INIT_TRANS) { }

inline ZZ_pX(long i, const ZZ_p& c);
inline ZZ_pX(long i, long c);

ZZ_pX& operator=(long a);
ZZ_pX& operator=(const ZZ_p& a);


};




/********************************************************************

                           input and output

I/O format:

   [a_0 a_1 ... a_n],

represents the polynomial a_0 + a_1*X + ... + a_n*X^n.

On output, all coefficients will be integers between 0 and p-1,
amd a_n not zero (the zero polynomial is [ ]).
On input, the coefficients are arbitrary integers which are
then reduced modulo p, and leading zeros stripped.

*********************************************************************/


NTL_SNS istream& operator>>(NTL_SNS istream& s, ZZ_pX& x);
NTL_SNS ostream& operator<<(NTL_SNS ostream& s, const ZZ_pX& a);




/**********************************************************

                   Some utility routines

***********************************************************/


inline long deg(const ZZ_pX& a) { return a.rep.length() - 1; }
// degree of a polynomial.
// note that the zero polynomial has degree -1.

const ZZ_p& coeff(const ZZ_pX& a, long i);
// zero if i not in range

void GetCoeff(ZZ_p& x, const ZZ_pX& a, long i);
// x = a[i], or zero if i not in range

const ZZ_p& LeadCoeff(const ZZ_pX& a);
// zero if a == 0

const ZZ_p& ConstTerm(const ZZ_pX& a);
// zero if a == 0

void SetCoeff(ZZ_pX& x, long i, const ZZ_p& a);
// x[i] = a, error is raised if i < 0

void SetCoeff(ZZ_pX& x, long i, long a);

void SetCoeff(ZZ_pX& x, long i);
// x[i] = 1, error is raised if i < 0

inline ZZ_pX::ZZ_pX(long i, const ZZ_p& a)
   { SetCoeff(*this, i, a); } 

inline ZZ_pX::ZZ_pX(long i, long a)
   { SetCoeff(*this, i, a); } 

void SetX(ZZ_pX& x);
// x is set to the monomial X

long IsX(const ZZ_pX& a);
// test if x = X

inline void clear(ZZ_pX& x) 
// x = 0

   { x.rep.SetLength(0); }

inline void set(ZZ_pX& x)
// x = 1

   { x.rep.SetLength(1); set(x.rep[0]); }

inline void swap(ZZ_pX& x, ZZ_pX& y)
// swap x & y (only pointers are swapped)

   { swap(x.rep, y.rep); }

void random(ZZ_pX& x, long n);
inline ZZ_pX random_ZZ_pX(long n)
   { ZZ_pX x; random(x, n); NTL_OPT_RETURN(ZZ_pX, x); }
// generate a random polynomial of degree < n 

void trunc(ZZ_pX& x, const ZZ_pX& a, long m);
// x = a % X^m

inline ZZ_pX trunc(const ZZ_pX& a, long m)
   { ZZ_pX x; trunc(x, a, m); NTL_OPT_RETURN(ZZ_pX, x); }

void RightShift(ZZ_pX& x, const ZZ_pX& a, long n);
// x = a/X^n

inline ZZ_pX RightShift(const ZZ_pX& a, long n)
   { ZZ_pX x; RightShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }

void LeftShift(ZZ_pX& x, const ZZ_pX& a, long n);
// x = a*X^n

inline ZZ_pX LeftShift(const ZZ_pX& a, long n)
   { ZZ_pX x; LeftShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }

#ifndef NTL_TRANSITION

inline ZZ_pX operator>>(const ZZ_pX& a, long n)
   { ZZ_pX x; RightShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator<<(const ZZ_pX& a, long n)
   { ZZ_pX x; LeftShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX& operator<<=(ZZ_pX& x, long n)
   { LeftShift(x, x, n); return x; }

inline ZZ_pX& operator>>=(ZZ_pX& x, long n)
   { RightShift(x, x, n); return x; }

#endif



void diff(ZZ_pX& x, const ZZ_pX& a);
// x = derivative of a

inline ZZ_pX diff(const ZZ_pX& a)
   { ZZ_pX x; diff(x, a); NTL_OPT_RETURN(ZZ_pX, x); }


void MakeMonic(ZZ_pX& x);

void reverse(ZZ_pX& c, const ZZ_pX& a, long hi);

inline ZZ_pX reverse(const ZZ_pX& a, long hi)
   { ZZ_pX x; reverse(x, a, hi); NTL_OPT_RETURN(ZZ_pX, x); }

inline void reverse(ZZ_pX& c, const ZZ_pX& a)
{  reverse(c, a, deg(a)); }

inline ZZ_pX reverse(const ZZ_pX& a)
   { ZZ_pX x; reverse(x, a); NTL_OPT_RETURN(ZZ_pX, x); }

inline void VectorCopy(vec_ZZ_p& x, const ZZ_pX& a, long n)
   { VectorCopy(x, a.rep, n); }

inline vec_ZZ_p VectorCopy(const ZZ_pX& a, long n)
   { return VectorCopy(a.rep, n); }




/*******************************************************************

                        conversion routines

********************************************************************/



void conv(ZZ_pX& x, long a);
void conv(ZZ_pX& x, const ZZ& a);
void conv(ZZ_pX& x, const ZZ_p& a);
void conv(ZZ_pX& x, const vec_ZZ_p& a);

inline ZZ_pX to_ZZ_pX(long a)
   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX to_ZZ_pX(const ZZ& a)
   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX to_ZZ_pX(const ZZ_p& a)
   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX to_ZZ_pX(const vec_ZZ_p& a)
   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }



/*************************************************************

                        Comparison

**************************************************************/

long IsZero(const ZZ_pX& a); 

long IsOne(const ZZ_pX& a);

inline long operator==(const ZZ_pX& a, const ZZ_pX& b)
{
   return a.rep == b.rep;
}

inline long operator!=(const ZZ_pX& a, const ZZ_pX& b)
{
   return !(a == b);
}

long operator==(const ZZ_pX& a, long b);
long operator==(const ZZ_pX& a, const ZZ_p& b);

inline long operator==(long a, const ZZ_pX& b) { return b == a; }
inline long operator==(const ZZ_p& a, const ZZ_pX& b) { return b == a; }

inline long operator!=(const ZZ_pX& a, long b) { return !(a == b); }
inline long operator!=(const ZZ_pX& a, const ZZ_p& b) { return !(a == b); }

inline long operator!=(long a, const ZZ_pX& b) { return !(a == b); }
inline long operator!=(const ZZ_p& a, const ZZ_pX& b) { return !(a == b); }


/***************************************************************

                         Addition

****************************************************************/

void add(ZZ_pX& x, const ZZ_pX& a, const ZZ_pX& b);
// x = a + b

void sub(ZZ_pX& x, const ZZ_pX& a, const ZZ_pX& b);
// x = a - b

void negate(ZZ_pX& x, const ZZ_pX& a);
// x = -a

// scalar versions

void add(ZZ_pX& x, const ZZ_pX& a, const ZZ_p& b); // x = a + b
void add(ZZ_pX& x, const ZZ_pX& a, long b);

inline void add(ZZ_pX& x, const ZZ_p& a, const ZZ_pX& b) { add(x, b, a); }
inline void add(ZZ_pX& x, long a, const ZZ_pX& b) { add(x, b, a); }


void sub(ZZ_pX & x, const ZZ_pX& a, const ZZ_p& b); // x = a - b

void sub(ZZ_pX& x, const ZZ_pX& a, long b);
void sub(ZZ_pX& x, const ZZ_pX& a, const ZZ_p& b);

void sub(ZZ_pX& x, long a, const ZZ_pX& b);
void sub(ZZ_pX& x, const ZZ_p& a, const ZZ_pX& b);

inline ZZ_pX operator+(const ZZ_pX& a, const ZZ_pX& b)
   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator+(const ZZ_pX& a, const ZZ_p& b)
   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator+(const ZZ_pX& a, long b)
   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator+(const ZZ_p& a, const ZZ_pX& b)
   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator+(long a, const ZZ_pX& b)
   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }


inline ZZ_pX operator-(const ZZ_pX& a, const ZZ_pX& b)
   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator-(const ZZ_pX& a, const ZZ_p& b)
   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator-(const ZZ_pX& a, long b)
   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator-(const ZZ_p& a, const ZZ_pX& b)
   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX operator-(long a, const ZZ_pX& b)
   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }


inline ZZ_pX& operator+=(ZZ_pX& x, const ZZ_pX& b)
   { add(x, x, b); return x; }

inline ZZ_pX& operator+=(ZZ_pX& x, const ZZ_p& b)
   { add(x, x, b); return x; }

inline ZZ_pX& operator+=(ZZ_pX& x, long b)
   { add(x, x, b); return x; }

inline ZZ_pX& operator-=(ZZ_pX& x, const ZZ_pX& b)
   { sub(x, x, b); return x; }

inline ZZ_pX& operator-=(ZZ_pX& x, const ZZ_p& b)
   { sub(x, x, b); return x; }

inline ZZ_pX& operator-=(ZZ_pX& x, long b)
   { sub(x, x, b); return x; }


inline ZZ_pX operator-(const ZZ_pX& a) 
   { ZZ_pX x; negate(x, a); NTL_OPT_RETURN(ZZ_pX, x); }

inline ZZ_pX& operator++(ZZ_pX& x) { add(x, x, 1); return x; }
inline void operator++(ZZ_pX& x, int) { add(x, x, 1); }
inline ZZ_pX& operator--(ZZ_pX& x) { sub(x, x, 1); return x; }
inline void operator--(ZZ_pX& x, int) { sub(x, x, 1); }