All Classes Functions Friends
uzpolynomial.h
1 #ifndef _UZPOLYNOMIAL_H_
2 #define _UZPOLYNOMIAL_H_
3 
4 /**
5  * Data Structure for univariate integer polynomial
6  * stored in a dense case
7  **/
8 
9 #include "../polynomial.h"
10 #include "modpoly.h"
11 
13  private:
14  std::string name; // Variable name
15  int curd; // Current degree
16  int n; // Maximum size of the polynomial
17  mpz_class* coef; // Coefficients
18 
19  inline void zeros() {
20  for (int i = 0; i < n; ++i)
21  coef[i] = 0;
22  }
23 
24  bool isEqual(DenseUnivariateIntegerPolynomial& q);
25  void pomopo(mpz_class c, mpz_class t, DenseUnivariateIntegerPolynomial& b);
26  void resetDegree();
30 
31  public:
32  static int characteristic;
33  static bool isPrimeField;
34  static bool isComplexField;
35  /**
36  * Construct a polynomial
37  *
38  * @param d
39  **/
40  DenseUnivariateIntegerPolynomial () : curd(0), n(1), name("%") {
41  coef = new mpz_class[1];
42  coef[0] = 0;
43  }
44  /**
45  * Construct a polynomial with degree
46  *
47  * @param d: Size of the polynomial
48  **/
50  if (s < 1) { s = 1; }
51  n = s;
52  coef = new mpz_class[n];
53  curd = 0;
54  //coef[0] = 0;
55  zeros();
56  name = "%";
57  }
58 
59  /**
60  * Construct a polynomial with a coeffient
61  * @param e: The coefficient
62  **/
63  DenseUnivariateIntegerPolynomial (Integer e) : curd(0), n(1), name("%") {
64  coef = new mpz_class[1];
65  coef[0] = e.get_mpz();
66  }
67  DenseUnivariateIntegerPolynomial (RationalNumber e) : curd(0), n(1), name("%") {
68  if (e.get_den() == 1) {
69  coef = new mpz_class[1];
70  coef[0] = e.get_num();
71  }
72  else {
73  std::cout << "BPAS error, try to construct a rational number in DUZP." << std::endl;
74  exit(1);
75  }
76  }
77  /**
78  * Copy constructor
79  *
80  * @param b: A densed univariate rationl polynomial
81  **/
82  DenseUnivariateIntegerPolynomial(const DenseUnivariateIntegerPolynomial& b) : curd(b.curd), name(b.name) {
83  n = curd + 1;
84  coef = new mpz_class[n];
85  std::copy(b.coef, b.coef+n, coef);
86  }
87  /**
88  * Destroy the polynomial
89  *
90  * @param
91  **/
93  delete [] coef;
94  }
95 
96  /**
97  * Get degree of the polynomial
98  *
99  * @param
100  **/
101  inline int degree() {
102  return curd;
103  }
104 
105  /**
106  * Get the leading coefficient
107  *
108  * @param
109  **/
110  inline mpz_class leadingCoefficient() {
111  return coef[curd];
112  }
113  /**
114  * Get coefficients of the polynomial, given start offset
115  *
116  * @param k: Offset
117  **/
118  inline mpz_class* coefficients(int k=0) {
119 #ifdef BPASDEBUG
120  if (k < 0 || k >= n)
121  std::cout << "BPAS: warning, try to access a non-exist coefficient " << k << " from DUZP(" << n << ")." << std::endl;
122 #endif
123  return &coef[k];
124  }
125  /**
126  * Get a coefficient of the polynomial
127  *
128  * @param k: Offset
129  **/
130  inline mpz_class coefficient(int k) {
131  if (k < 0 || k >= n)
132  return mpz_class(0);
133  return coef[k];
134  }
135  /**
136  * Set a coefficient of the polynomial
137  *
138  * @param k: Offset
139  * @param val: Coefficient
140  **/
141  inline void setCoefficient(int k, mpz_class value) {
142  if (k >= n || k < 0) {
143  std::cout << "BPAS: error, DUZP(" << n << ") but trying to access " << k << "." << std::endl;
144  exit(1);
145  }
146  coef[k] = value;
147  if (k > curd && value != 0)
148  curd = k;
149  resetDegree();
150  }
151  inline void setCoefficient(int k, Integer value) {
152  setCoefficient(k, value.get_mpz());
153  }
154  inline void setCoefficient(int k, sfixn value) {
155  setCoefficient(k, mpz_class(value));
156  }
157 
158  /**
159  * Get variable's name
160  *
161  * @param
162  **/
163  inline std::string variable() {
164  return name;
165  }
166  /**
167  * Set variable's name
168  *
169  * @param x: Varable's name
170  **/
171  inline void setVariableName (std::string x) {
172  name = x;
173  }
174  /**
175  * Overload operator =
176  *
177  * @param b: A univariate integer polynoial
178  **/
180  if (this != &b) {
181  if (n) { delete [] coef; n = 0; }
182  name = b.name;
183  curd = b.curd;
184  n = curd + 1;
185  coef = new mpz_class[n];
186  std::copy(b.coef, b.coef+n, coef);
187  }
188  return *this;
189  }
190  /**
191  * Overload operator !=
192  *
193  * @param b: A univariate integer polynoial
194  **/
196  return !(isEqual(b));
197  }
198  /**
199  * Overload operator ==
200  *
201  * @param b: A univariate integer polynoial
202  **/
204  return isEqual(b);
205  }
206 
207  /**
208  * Is zero polynomial
209  *
210  * @param
211  **/
212  inline bool isZero () {
213  if (!curd)
214  return (coef[0] == 0);
215  return 0;
216  }
217  /**
218  * Zero polynomial
219  *
220  * @param
221  **/
222  inline void zero() {
223  curd = 0;
224  zeros();
225  }
226  /**
227  * Is polynomial a constatn 1
228  *
229  * @param
230  **/
231  inline bool isOne() {
232  if (!curd)
233  return (coef[0] == 1);
234  return 0;
235  }
236  /**
237  * Set polynomial to 1
238  *
239  * @param
240  **/
241  inline void one() {
242  curd = 0;
243  coef[0] = 1;
244  for (int i = 1; i < n; ++i)
245  coef[i] = 0;
246  }
247  /**
248  * Is polynomial a constatn -1
249  *
250  * @param
251  **/
252  inline bool isNegativeOne() {
253  if (!curd)
254  return (coef[0] == -1);
255  return 0;
256  }
257  /**
258  * Set polynomial to -1
259  *
260  * @param
261  **/
262  inline void negativeOne() {
263  curd = 0;
264  coef[0] = -1;
265  for (int i = 1; i < n; ++i)
266  coef[i] = 0;
267  }
268  /**
269  * Is a constant
270  *
271  * @param
272  **/
273  inline int isConstant() {
274  if (curd) { return 0; }
275  else if (coef[0] >= 0) { return 1; }
276  else { return -1; }
277  }
278  /**
279  * Content of the polynomial
280  *
281  * @param
282  **/
283  inline mpz_class content() {
284  mpz_class c = coef[0];
285  for (int i = 1; i <= curd; ++i) {
286  if (coef[i] != 0) {
287  mpz_gcd(c.get_mpz_t(), c.get_mpz_t(), coef[i].get_mpz_t());
288  if (c == 1)
289  break;
290  }
291  }
292  return c;
293  }
294  /**
295  * Is the least signficant coefficient zero
296  *
297  * @param
298  **/
299  inline bool isTrailingCoefficientZero () {
300  return (coef[0] == 0);
301  }
302  /**
303  * Overload operator ^
304  * replace xor operation by exponentiation
305  *
306  * @param e: The exponentiation, e > 0
307  **/
309  /**
310  * Overload operator ^=
311  * replace xor operation by exponentiation
312  *
313  * @param e: The exponentiation, e > 0
314  **/
316  *this = *this ^ e;
317  return *this;
318  }
319  /**
320  * Overload operator <<
321  * replace by muplitying x^k
322  *
323  * @param k: The exponent of variable, k > 0
324  **/
326  /**
327  * Overload operator <<
328  * replace by muplitying x^k
329  *
330  * @param k: The exponent of variable, k > 0
331  **/
333  *this = *this << k;
334  return *this;
335  }
336  /**
337  * Overload operator >>
338  * replace by dividing x^k, and
339  * return the quotient
340  *
341  * @param k: The exponent of variable, k > 0
342  **/
344  inline DenseUnivariateIntegerPolynomial& operator>>= (int k) {
345  *this = *this >> k;
346  return *this;
347  }
348  /**
349  * Overload operator >>=
350  * replace by dividing x^k, and
351  * return the quotient
352  *
353  * @param k: The exponent of variable, k > 0
354  **/
355  /**
356  * Overload operator +
357  *
358  * @param b: A univariate integer polynomial
359  **/
361  /**
362  * Overload Operator +=
363  *
364  * @param b: A univariate integer polynomial
365  **/
367  if (curd >= b.curd)
368  add(b);
369  else
370  *this = *this + b;
371  return *this;
372  }
373  /**
374  * Add another polynomial to itself
375  *
376  * @param b: A univariate integer polynomial
377  **/
379  /**
380  * Overload Operator +
381  *
382  * @param c: An integer
383  **/
386  return (r += c);
387  }
388  inline DenseUnivariateIntegerPolynomial operator+ (mpz_class c) {
390  return (r += c);
391  }
394  return (r += c);
395  }
396  /**
397  * Overload Operator +=
398  *
399  * @param c: An integer
400  **/
402  coef[0] += mpz_class(c.get_mpz_t());
403  return *this;
404  }
405  inline DenseUnivariateIntegerPolynomial& operator+= (mpz_class c) {
406  coef[0] += c;
407  return *this;
408  }
410  coef[0] += c;
411  return *this;
412  }
413 
415  return (p + c);
416  }
418  return (p + c);
419  }
420  /**
421  * Subtract another polynomial
422  *
423  * @param b: A univariate integer polynomial
424  */
426  /**
427  * Overload operator -=
428  *
429  * @param b: A univariate integer polynomial
430  **/
432  if (curd >= b.curd)
433  subtract(b);
434  else
435  *this = *this - b;
436  return *this;
437  }
438  /**
439  * Overload operator -, negate
440  *
441  * @param
442  **/
444  /**
445  * Compute -f(x)
446  *
447  * @param
448  **/
449  inline void negate() {
450  for (int i = 0; i <= curd; ++i)
451  coef[i] = -coef[i];
452  }
453  /**
454  * Subtract another polynomial from itself
455  *
456  * @param b: A univariate integer polynomial
457  **/
459  /**
460  * Overload operator -
461  *
462  * @param c: An integer
463  **/
466  return (r -= c);
467  }
468  inline DenseUnivariateIntegerPolynomial operator- (mpz_class c) {
470  return (r -= c);
471  }
474  return (r -= c);
475  }
476 
477  /**
478  * Overload operator -=
479  *
480  * @param c: An integer
481  **/
483  coef[0] -= mpz_class(c.get_mpz_t());
484  return *this;
485  }
486  inline DenseUnivariateIntegerPolynomial& operator-= (mpz_class c) {
487  coef[0] -= c;
488  return *this;
489  }
491  coef[0] -= c;
492  return *this;
493  }
494 
496  return (-p + c);
497  }
499  return (-p + c);
500  }
501  /**
502  * Multiply to another polynomial
503  *
504  * @param b: A univariate integer polynomial
505  **/
507  /**
508  * Overload operator *=
509  *
510  * @param b: A univariate integer polynomial
511  **/
513  *this = *this * b;
514  return *this;
515  }
516  /**
517  * Overload operator *
518  *
519  * @param e: An integer
520  **/
523  return (r *= e);
524  }
525  inline DenseUnivariateIntegerPolynomial operator* (mpz_class e) {
527  return (r *= e);
528  }
531  return (r *= e);
532  }
533  /**
534  * Overload operator *=
535  *
536  * @param e: An integer
537  **/
539  mpz_class c (e.get_mpz_t());
540  *this *= c;
541  return *this;
542  }
543  inline DenseUnivariateIntegerPolynomial& operator*= (mpz_class e) {
544  if (e != 0 && e != 1) {
545  for (int i = 0; i <= curd; ++i)
546  coef[i] *= e;
547  }
548  else if (e == 0) { zero(); }
549  return *this;
550  }
551  /**
552  * Overload operator *=
553  *
554  * @param e: A constant
555  **/
557  if (e != 0 && e != 1) {
558  for (int i = 0; i <= curd; ++i)
559  coef[i] *= e;
560  }
561  else if (e == 0) { zero(); }
562  return *this;
563  }
564 
566  return (p * e);
567  }
569  return (p * e);
570  }
571  /**
572  * Overload operator /
573  * ExactDivision
574  *
575  * @param b: A univariate integer polynomial
576  **/
579  return (rem /= b);
580  }
581  /**
582  * Overload operator /=
583  * ExactDivision
584  *
585  * @param b: A univariate integer polynomial
586  **/
588  /**
589  * Overload operator /
590  *
591  * @param e: An integer
592  **/
595  return (r /= e);
596  }
597  inline DenseUnivariateIntegerPolynomial operator/ (mpz_class e) {
599  return (r /= e);
600  }
603  return (r /= e);
604  }
605  /**
606  * Overload operator /=
607  *
608  * @param e: An integer
609  **/
611  mpz_class c (e.get_mpz_t());
612  return (*this /= c);
613  }
616  return (*this /= mpz_class(e));
617  }
618 
620  /**
621  * Monic division
622  * Return quotient and itself become the remainder
623  *
624  * @param b: The dividend polynomial
625  **/
627  /**
628  * Monic division
629  * Return quotient
630  *
631  * @param b: The dividend polynomial
632  * @param rem: The remainder polynomial
633  **/
635  *rem = *this;
636  return rem->monicDivide(b);
637  }
638  /**
639  * Lazy pseudo dividsion
640  * Return the quotient and itself becomes remainder
641  * e is the exact number of division steps
642  *
643  * @param b: The dividend polynomial
644  * @param c: The leading coefficient of b to the power e
645  * @param d: That to the power deg(a) - deg(b) + 1 - e
646  **/
648  /**
649  * Lazy pseudo dividsion
650  * Return the quotient
651  * e is the exact number of division steps
652  *
653  * @param b: The divident polynomial
654  * @param rem: The remainder polynomial
655  * @param c: The leading coefficient of b to the power e
656  * @param d: That to the power deg(a) - deg(b) + 1 - e
657  **/
659  *rem = *this;
660  return rem->lazyPseudoDivide(b, c, d);
661  }
662  /**
663  * Pseudo dividsion
664  * Return the quotient and itself becomes remainder
665  *
666  * @param b: The divident polynomial
667  * @param d: The leading coefficient of b
668  * to the power deg(a) - deg(b) + 1
669  **/
671  /**
672  * Pseudo dividsion
673  * Return the quotient
674  *
675  * @param b: The divident polynomial
676  * @param rem: The remainder polynomial
677  * @param d: The leading coefficient of b
678  * to the power deg(a) - deg(b) + 1
679  **/
681  /**
682  * GCD(p, q)
683  *
684  * @param q: The other polynomial
685  **/
687  /**
688  * Compute k-th differentiate
689  *
690  * @param k: k-th differentiate, k > 0
691  **/
692  void differentiate(int k);
693  /**
694  * Evaluate f(x)
695  *
696  * @param x: Evaluation point
697  **/
698  mpz_class evaluate(mpz_class x);
699  /**
700  * Square free
701  *
702  * @param
703  **/
704  std::vector<DenseUnivariateIntegerPolynomial> squareFree();
705  /**
706  * Overload stream operator <<
707  *
708  * @param out: Stream object
709  * @param b: A univariate integer polynoial
710  **/
711  friend std::ostream& operator<< (std::ostream &out, DenseUnivariateIntegerPolynomial b);
712 };
713 
714 #endif
715 /* This file is part of the BPAS library http://www.bpaslib.org
716 
717  BPAS is free software: you can redistribute it and/or modify
718  it under the terms of the GNU General Public License as published by
719  the Free Software Foundation, either version 3 of the License, or
720  (at your option) any later version.
721 
722  BPAS is distributed in the hope that it will be useful,
723  but WITHOUT ANY WARRANTY; without even the implied warranty of
724  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
725  GNU General Public License for more details.
726 
727  You should have received a copy of the GNU General Public License
728  along with BPAS. If not, see <http://www.gnu.org/licenses/>.
729 
730  Copyright: Changbo Chen <changbo.chen@hotmail.com>
731  Farnam Mansouri <mansouri.farnam@gmail.com>
732  Marc Moreno Maza <moreno@csd.uwo.ca>
733  Ning Xie <nxie6@csd.uwo.ca>
734  Yuzhen Xie <yuzhenxie@yahoo.ca>
735 
736 */
737 
738 
DenseUnivariateIntegerPolynomial(Integer e)
Definition: uzpolynomial.h:63
int isConstant()
Definition: uzpolynomial.h:273
bool operator!=(DenseUnivariateIntegerPolynomial &b)
Definition: uzpolynomial.h:195
void setCoefficient(int k, mpz_class value)
Definition: uzpolynomial.h:141
DenseUnivariateIntegerPolynomial operator^(int e)
bool isNegativeOne()
Definition: uzpolynomial.h:252
DenseUnivariateIntegerPolynomial & operator*=(DenseUnivariateIntegerPolynomial b)
Definition: uzpolynomial.h:512
mpz_class content()
Definition: uzpolynomial.h:283
DenseUnivariateIntegerPolynomial & operator+=(DenseUnivariateIntegerPolynomial b)
Definition: uzpolynomial.h:366
mpz_class * coefficients(int k=0)
Definition: uzpolynomial.h:118
DenseUnivariateIntegerPolynomial & operator/=(DenseUnivariateIntegerPolynomial b)
DenseUnivariateIntegerPolynomial()
Definition: uzpolynomial.h:40
void add(DenseUnivariateIntegerPolynomial b)
DenseUnivariateIntegerPolynomial monicDivide(DenseUnivariateIntegerPolynomial &b, DenseUnivariateIntegerPolynomial *rem)
Definition: uzpolynomial.h:634
DenseUnivariateIntegerPolynomial(int s)
Definition: uzpolynomial.h:49
Definition: uzpolynomial.h:12
DenseUnivariateIntegerPolynomial operator>>(int k)
DenseUnivariateIntegerPolynomial & operator^=(int e)
Definition: uzpolynomial.h:315
DenseUnivariateIntegerPolynomial operator*(DenseUnivariateIntegerPolynomial b)
void one()
Definition: uzpolynomial.h:241
std::string variable()
Definition: uzpolynomial.h:163
mpz_class coefficient(int k)
Definition: uzpolynomial.h:130
void zero()
Definition: uzpolynomial.h:222
DenseUnivariateIntegerPolynomial lazyPseudoDivide(DenseUnivariateIntegerPolynomial &b, mpz_class *c, mpz_class *d=NULL)
DenseUnivariateIntegerPolynomial & operator<<=(int k)
Definition: uzpolynomial.h:332
bool isZero()
Definition: uzpolynomial.h:212
bool operator==(DenseUnivariateIntegerPolynomial &b)
Definition: uzpolynomial.h:203
void negate()
Definition: uzpolynomial.h:449
DenseUnivariateIntegerPolynomial(const DenseUnivariateIntegerPolynomial &b)
Definition: uzpolynomial.h:82
Definition: ring.h:48
Definition: polynomial.h:30
DenseUnivariateIntegerPolynomial & operator=(DenseUnivariateIntegerPolynomial b)
Definition: uzpolynomial.h:179
DenseUnivariateIntegerPolynomial operator+(DenseUnivariateIntegerPolynomial b)
bool isTrailingCoefficientZero()
Definition: uzpolynomial.h:299
DenseUnivariateIntegerPolynomial lazyPseudoDivide(DenseUnivariateIntegerPolynomial &b, DenseUnivariateIntegerPolynomial *rem, mpz_class *c, mpz_class *d)
Definition: uzpolynomial.h:658
DenseUnivariateIntegerPolynomial pseudoDivide(DenseUnivariateIntegerPolynomial &b, mpz_class *d=NULL)
Definition: ring.h:166
void subtract(DenseUnivariateIntegerPolynomial b)
DenseUnivariateIntegerPolynomial & operator-=(DenseUnivariateIntegerPolynomial b)
Definition: uzpolynomial.h:431
DenseUnivariateIntegerPolynomial monicDivide(DenseUnivariateIntegerPolynomial &b)
DenseUnivariateIntegerPolynomial operator-()
DenseUnivariateIntegerPolynomial operator/(DenseUnivariateIntegerPolynomial b)
Definition: uzpolynomial.h:577
bool isOne()
Definition: uzpolynomial.h:231
int degree()
Definition: uzpolynomial.h:101
DenseUnivariateIntegerPolynomial gcd(DenseUnivariateIntegerPolynomial q, int type=0)
std::vector< DenseUnivariateIntegerPolynomial > squareFree()
mpz_class evaluate(mpz_class x)
void negativeOne()
Definition: uzpolynomial.h:262
DenseUnivariateIntegerPolynomial operator<<(int k)
mpz_class leadingCoefficient()
Definition: uzpolynomial.h:110
~DenseUnivariateIntegerPolynomial()
Definition: uzpolynomial.h:92
void setVariableName(std::string x)
Definition: uzpolynomial.h:171