17 lines
18 KiB
Plaintext
17 lines
18 KiB
Plaintext
|
<html>
|
||
|
|
<head></head>
|
||
|
|
<body>
|
||
|
|
/**************************************************************************\ MODULE: ZZX SUMMARY: The class ZZX implements polynomials in ZZ[X], i.e., univariate polynomials with integer coefficients. Polynomial multiplication is implemented using one of 4 different algorithms: 1) classical 2) Karatsuba 3) Schoenhage & Strassen --- performs an FFT by working modulo a "Fermat number" of appropriate size... good for polynomials with huge coefficients and moderate degree 4) CRT/FFT --- performs an FFT by working modulo several small primes...good for polynomials with moderate coefficients and huge degree. The choice of algorithm is somewhat heuristic, and may not always be perfect. Many thanks to Juergen Gerhard <jngerhar@plato.uni-paderborn.de>
|
||
|
|
for pointing out the deficiency in the NTL-1.0 ZZX arithmetic, and for contributing the Schoenhage/Strassen code. Extensive use is made of modular algorithms to enhance performance (e.g., the GCD algorithm and amny others). \**************************************************************************/ #include
|
||
|
|
<ntl vec_zz.h>
|
||
|
|
#include "zz_pX.h" #include
|
||
|
|
<ntl zz_px.h>
|
||
|
|
class ZZX { public: ZZX(); // initial value 0 ZZX(const ZZX& a); // copy explicit ZZX(const ZZ& a); // promotion explicit ZZX(long a); // promotion ~ZZX(); ZZX(ZZX&& a); // move constructor (C++11 only) // declared noexcept unless NTL_EXCEPTIONS flag is set ZZX& operator=(ZZX&& a); // move assignment (C++11 only) // declared noexcept unless NTL_EXCEPTIONS flag is set ZZX(INIT_MONO_TYPE, long i, const ZZ& c); ZZX(INIT_MONO_TYPE, long i, long c); // initial value c*X^i, invoke as ZZX(INIT_MONO, i, c) ZZX(INIT_MONO_TYPE, long i); // initial value X^i, invoke as ZZX(INIT_MONO, i) ZZX& operator=(const ZZX& a); // assignment ZZX& operator=(const ZZ& a); ZZX& operator=(long a); typedef ZZ coeff_type; // ... }; /**************************************************************************\ Accessing coefficients The degree of a polynomial f is obtained as deg(f), where the zero polynomial, by definition, has degree -1. A polynomial f is represented as a coefficient vector. Coefficients may be accesses in one of two ways. The safe, high-level method is to call the function coeff(f, i) to get the coefficient of X^i in the polynomial f, and to call the function SetCoeff(f, i, a) to set the coefficient of X^i in f to the scalar a. One can also access the coefficients more directly via a lower level interface. The coefficient of X^i in f may be accessed using subscript notation f[i]. In addition, one may write f.SetLength(n) to set the length of the underlying coefficient vector to n, and f.SetMaxLength(n) to allocate space for n coefficients, without changing the coefficient vector itself. After setting coefficients using this low-level interface, one must ensure that leading zeros in the coefficient vector are stripped afterwards by calling the function f.normalize(). NOTE: the coefficient vector of f may also be accessed directly as f.rep; however, this is not recommended. Also, for a properly normalized polynomial f, we have f.rep.length() == deg(f)+1, and deg(f) >= 0 => f.rep[deg(f)] != 0. \**************************************************************************/ long deg(const ZZX& a); // return deg(a); deg(0) == -1. const ZZ& coeff(const ZZX& a, long i); // returns the coefficient of X^i, or zero if i not in range const ZZ& LeadCoeff(const ZZX& a); // returns leading term of a, or zero if a == 0 const ZZ& ConstTerm(const ZZX& a); // returns constant term of a, or zero if a == 0 void SetCoeff(ZZX& x, long i, const ZZ& a); void SetCoeff(ZZX& x, long i, long a); // makes coefficient of X^i equal to a; error is raised if i < 0 void SetCoeff(ZZX& x, long i); // makes coefficient of X^i equal to 1; error is raised if i < 0 void SetX(ZZX& x); // x is set to the monomial X long IsX(const ZZX& a); // test if x = X ZZ& ZZX::operator[](long i); const ZZ& ZZX::operator[](long i) const; // indexing operators: f[i] is the coefficient of X^i --- // i should satsify i >= 0 and i <= deg(f). // No range checking (unless NTL_RANGE_CHECK is defined). void ZZX::SetLength(long n); // f.SetLength(n) sets the length of the inderlying coefficient // vector to n --- after this call, indexing f[i] for i = 0..n-1 // is valid. void ZZX::normalize(); // f.normalize() strips leading zeros from coefficient vector of f void ZZX::SetMaxLength(long n); // f.SetMaxLength(n) pre-allocate spaces for n coefficients. The // polynomial that f represents is unchanged. /**************************************************************************\ Comparison \**************************************************************************/ long operator==(const ZZX& a, const ZZX& b); long operator!=(const ZZX& a, const ZZX& b); long IsZero(const ZZX& a); // test for 0 long IsOne(const ZZX& a); // test for 1 // PROMOTIONS: operators ==, != promote {long, ZZ} to ZZX on (a, b). /**************************************************************************\ Addition \*************************************************************
|
||
|
|
<zzx>
|
||
|
|
vec_ZZX; // backward compatibility /**************************************************************************\ Miscellany \**************************************************************************/ void clear(ZZX& x); // x = 0 void set(ZZX& x); // x = 1 void ZZX::kill(); // f.kill() sets f to 0 and frees all memory held by f. Equivalent to // f.rep.kill(). ZZX::ZZX(INIT_SIZE_TYPE, long n); // ZZX(INIT_SIZE, n) initializes to zero, but space is pre-allocated // for n coefficients static const ZZX& zero(); // ZZX::zero() is a read-only reference to 0 void ZZX::swap(ZZX& x); void swap(ZZX& x, ZZX& y); // swap (by swapping pointers) ZZX::ZZX(long i, const ZZ& c); ZZX::ZZX(long i, long c); // initial value c*X^i, provided for backward compatibility
|
||
|
|
</zzx>
|
||
|
|
</ntl>
|
||
|
|
</ntl>
|
||
|
|
</jngerhar@plato.uni-paderborn.de>
|
||
|
|
</body>
|
||
|
|
</html>
|