All Classes Functions Friends
upolynomial.h
1 #ifndef _UPOLYNOMIAL_H_
2 #define _UPOLYNOMIAL_H_
3 
4 //#include <type_traits>
5 #include "../polynomial.h"
6 #include "../IntegerPolynomial/uzpolynomial.h"
7 #include "../RationalNumberPolynomial/URPolynomial/urpolynomial.h"
8 
9 template <class Ring>
11  private:
12  std::string name;
13  std::vector< UnivariateTerm<Ring> > terms;
14 
15  inline bool isEqual(SparseUnivariatePolynomial<Ring>& b) {
16  if (degree() && b.degree() && (name != b.name))
17  return 0;
18  int n = terms.size();
19  int m = b.terms.size();
20  if (n != m)
21  return 0;
22  for (int i = 0; i < n; ++i) {
23  UnivariateTerm<Ring> t = b.terms[i];
24  if (terms[i].coef != t.coef || terms[i].exp != t.exp)
25  return 0;
26  }
27  return 1;
28  }
29  inline bool isEqual(DenseUnivariateRationalPolynomial& b) {
30  if (name != b.variable())
31  return 0;
32  int n = degree(), m = b.degree();
33  if (n != m)
34  return 0;
35  n = terms.size(), m++;
36  int k = 0;
37  for (int i = 0; i < m; ++i) {
38  if (k < n && terms[k].exp == i) {
39  if (terms[k].coef != b.coefficient(i))
40  return 0;
41  k++;
42  }
43  else if (b.coefficient(i) != 0)
44  return 0;
45  }
46  return 1;
47  }
48  inline bool isEqual(DenseUnivariateIntegerPolynomial& b) {
49  if (name != b.variable())
50  return 0;
51  int n = degree(), m = b.degree();
52  if (n != m)
53  return 0;
54  n = terms.size(), m++;
55  int k = 0;
56  for (int i = 0; i < m; ++i) {
57  if (k < n && terms[k].exp == i) {
58  if (terms[k].coef != b.coefficient(i))
59  return 0;
60  k++;
61  }
62  else if (b.coefficient(i) != 0)
63  return 0;
64  }
65  return 1;
66  }
67 
68  /* this += t * b */
69  inline void pomopo(UnivariateTerm<Ring> t, SparseUnivariatePolynomial<Ring>& b) {
70  int ai = 0, m = b.terms.size();
71 
72  for (int i = 0; i < m; ++i) {
73  UnivariateTerm<Ring> product;
74  product.coef = t.coef * b.terms[i].coef;
75  product.exp = t.exp + b.terms[i].exp;
76 
77  if (ai >= terms.size()) {
78  terms.push_back(product);
79  ai++;
80  }
81  else {
82  int e1 = terms[ai].exp, e2 = product.exp;
83  while (e1 < e2) {
84  ai++;
85  if (ai < terms.size())
86  e1 = terms[ai].exp;
87  else {
88  terms.push_back(product);
89  ai++;
90  break;
91  }
92  }
93  if (e1 == e2) {
94  terms[ai].coef += product.coef;
95  if (terms[ai].coef.isZero())
96  terms.erase(terms.begin()+ai);
97  else { ai++; }
98  }
99  else if (e1 > e2) {
100  terms.insert(terms.begin()+ai, product);
101  ai++;
102  }
103  }
104  }
105  }
106 
107  inline void pomopo(Ring c, UnivariateTerm<Ring> t, SparseUnivariatePolynomial<Ring>& b) {
108  int ai = 0, m = b.terms.size();
109 
110  for (int i = 0; i < m; ++i) {
111  UnivariateTerm<Ring> product;
112  product.coef = t.coef * b.terms[i].coef;
113  product.exp = t.exp + b.terms[i].exp;
114 
115  if (ai >= terms.size()) {
116  terms.push_back(product);
117  ai++;
118  }
119  else {
120  int e1 = terms[ai].exp, e2 = product.exp;
121  while (e1 < e2) {
122  terms[ai].coef *= c;
123  ai++;
124  if (ai < terms.size())
125  e1 = terms[ai].exp;
126  else {
127  terms.push_back(product);
128  ai++;
129  break;
130  }
131  }
132  if (e1 == e2) {
133  terms[ai].coef *= c;
134  terms[ai].coef += product.coef;
135  if (terms[ai].coef.isZero())
136  terms.erase(terms.begin()+ai);
137  else { ai++; }
138  }
139  else if (e1 > e2) {
140  terms.insert(terms.begin()+ai, product);
141  ai++;
142  }
143  }
144  }
145  for (int i = ai; i < terms.size(); ++i)
146  terms[i].coef *= c;
147  }
148 
149  // For subresultant
151  int n = sd.degree() - sdm.degree() - 1;
152  if (!n) { return sdm; }
153  Ring x = sdm.leadingCoefficient();
154  Ring y = sd.leadingCoefficient();
155  int a = (int) pow(2, floor(log2(n)));
156  Ring c = x;
157  n -= a;
158  while (a != 1) {
159  a >>= 1;
160  c *= c;
161  c /= y;
162  if (n >= a) {
163  c *= x;
164  c /= y;
165  n -= a;
166  }
167  }
168  c /= y;
169 
171  se *= c;
172  return se;
173  }
175  int d = a.degree(), e = sdm.degree();
177  res.name = name;
178  Ring ec = se.leadingCoefficient();
179  if (d == e){
180  // Streamlined resultant computation for regular case
181  Ring dc = a.leadingCoefficient();
182  Ring rTemp;
184  supTemp.name = name;
185  // compute first of two main terms
186  res = a;
187  res *= ec;
188  rTemp = a.coefficient(e);
189  supTemp = se;
190  supTemp *= rTemp;
191  res -= supTemp;
192  res /= dc;
193  res *= ec;
194  // compute second of two main terms
195  rTemp = se.coefficient(e-1);
196  supTemp.zero();
197  supTemp.setCoefficient(0,rTemp);
198  rTemp = -ec;
199  supTemp.setCoefficient(1,rTemp);
200  supTemp *= se;
201  res += supTemp;
202  // divide out dc to obtain resultant
203  res /= dc;
204  return res;
205  }
206  else {
207  // Ducos algorithm for defective case
208  Ring mc = sdm.leadingCoefficient();
210  for (int i = 0; i < e; ++i) {
211  P[i].setVariableName(name);
212  P[i].setCoefficient(i, ec);
213  }
214  P[e].setVariableName(name);
215  P[e].setCoefficient(e, ec);
216  P[e] -= se;
217  ec.one();
218  res.setCoefficient(1, ec);
219  UnivariateTerm<Ring> t (ec, 1);
220  for(int i = e+1; i < d; ++i) {
221  ec = -P[i-1].coefficient(e-1);
222  ec /= mc;
223  P[i] = sdm;
224  P[i] *= ec;
225  //P[i] += res * P[i-1];
226  P[i].pomopo(t, P[i-1]);
227  }
228  res *= P[d-1];
229 
231  for (int i = 0; i < d; ++i) {
232  P[i] *= a.coefficient(i);
233  D += P[i];
234  }
235  D /= a.leadingCoefficient();
236  delete [] P;
237 
238  ec = -res.coefficient(e);
239  //res += D;
240  //res *= mc;
241  t.coef = mc;
242  t.exp = 0;
243  res.pomopo(mc, t, D);
244  sdm *= ec;
245  res += sdm;
246  res /= sd;
247 
248  if ((d - e + 1) % 2 == 1)
249  return -res;
250  return res;
251  }
252  }
253  inline UnivariateTerm<Ring> leadingTerm() {
254  int n = terms.size();
255  if (n) { return terms[n-1]; }
256  else { return UnivariateTerm<Ring>(); }
257  }
258 
259  public:
260  int characteristic;
261  static bool isPrimeField;
262  static bool isComplexField;
263  /**
264  * Construct a polynomial
265  *
266  * @param
267  **/
268  SparseUnivariatePolynomial<Ring> () : name("%"), terms() {
269  Ring e;
270  characteristic = e.characteristic;
271  }
272  /**
273  * Copy constructor
274  *
275  * @param b: A sparse univariate polynomial
276  **/
277  SparseUnivariatePolynomial<Ring> (const SparseUnivariatePolynomial<Ring>& b) : name(b.name), terms(b.terms) {
278  Ring e;
279  characteristic = e.characteristic;
280  }
281 
283  UnivariateTerm<Ring> t;
284  t.coef = Ring(c);
285  terms.push_back(t);
286  }
287 
289  UnivariateTerm<Ring> t;
290  t.coef = Ring(c);
291  t.exp = 0;
292  terms.push_back(t);
293  }
294 
296  UnivariateTerm<Ring> t;
297  t.coef = Ring(c);
298  terms.push_back(t);
299  }
300 
302  name = b.variable();
303  for (int i = 0; i <= b.degree(); ++i) {
304  Ring e (Integer(b.coefficient(i)));
305  if (!e.isZero()) {
306  UnivariateTerm<Ring> t;
307  t.coef = e;
308  t.exp = i;
309  terms.push_back(t);
310  }
311  }
312  }
313 
315  name = b.variable();
316  for (int i = 0; i <= b.degree(); ++i) {
317  Ring e (RationalNumber(b.coefficient(i)));
318  if (!e.isZero()) {
319  UnivariateTerm<Ring> t;
320  t.coef = e;
321  t.exp = i;
322  terms.push_back(t);
323  }
324  }
325  }
326  /**
327  * Destroy the polynomial
328  *
329  * @param
330  **/
332  terms.clear();
333  }
334  /**
335  * Get the number of terms
336  *
337  * @param
338  **/
339  inline int numberOfTerms() {
340  return terms.size();
341  }
342  /**
343  * Get the degree of the polynomial
344  *
345  * @param
346  **/
347  inline int degree() {
348  int n = terms.size();
349  if (n) { return terms[n-1].exp; }
350  else { return 0; }
351  }
352  /**
353  * Get the leading coefficient
354  *
355  * @param
356  **/
357  inline Ring leadingCoefficient() {
358  int n = terms.size();
359  if (n) { return terms[n-1].coef; }
360  else { return Ring(); }
361  }
362  /**
363  * Get a coefficient
364  *
365  * @param k: The exponent
366  **/
367  inline Ring coefficient(int k) {
368  int n = terms.size();
369  for (int i = 0; i < n; ++i) {
370  if (k == terms[i].exp)
371  return terms[i].coef;
372  else if (k < terms[i].exp)
373  break;
374  }
375  return Ring();
376  }
377  /**
378  * Set a coeffcient with its exponent
379  *
380  * @param e: The exponent
381  * @param c: The coefficient
382  **/
383  inline void setCoefficient(int e, Ring c) {
384  UnivariateTerm<Ring> b;
385  b.coef = c;
386  b.exp = e;
387 
388 
389  int k = terms.size() - 1;
390  if ((k < 0 || b.exp > terms[k].exp) && !c.isZero())
391  terms.push_back(b);
392  else {
393  for (int i = 0; i <= k; ++i) {
394  int e1 = terms[i].exp, e2 = b.exp;
395  if (e1 == e2) {
396  terms[i].coef = b.coef;
397  if (terms[i].coef.isZero())
398  terms.erase(terms.begin()+i);
399  break;
400  }
401  else if (e1 > e2) {
402  if (!c.isZero())
403  terms.insert(terms.begin()+i, b);
404  break;
405  }
406  }
407  }
408  }
409  /**
410  * Get the variable name
411  *
412  * @param
413  **/
414  inline std::string variable() {
415  return name;
416  }
417  /**
418  * Set the variable name
419  *
420  * @param c: Variable's name
421  **/
422  inline void setVariableName (std::string c) {
423  name = c;
424  }
425 
426  /**
427  * Overload operator =
428  *
429  * @param b: A sparse univariate polynomial
430  **/
432  if (this != &b) {
433  terms.clear();
434  name = b.name;
435  terms = b.terms;
436  Ring e;
437  characteristic = e.characteristic;
438  }
439  return *this;
440  }
441  /**
442  * Overload operator !=
443  *
444  * @param b: A sparse univariate polynomial
445  **/
447  return !(isEqual(b));
448  }
449  /**
450  * Overload operator ==
451  *
452  * @param b: A sparse univariate polynomial
453  **/
455  return isEqual(b);
456  }
458  return isEqual(b);
459  }
461  return isEqual(b);
462  }
463 
464  /**
465  * Is zero polynomial
466  *
467  * @param
468  **/
469  inline bool isZero() {
470  return !(terms.size());
471  }
472  /**
473  * Zero polynomial
474  *
475  * @param
476  **/
477  inline void zero() {
478  terms.clear();
479  }
480  /**
481  * Is polynomial a constant 1
482  *
483  * @param
484  **/
485  inline bool isOne() {
486  if (terms.size() == 1 && !terms[0].exp)
487  return terms[0].coef.isOne();
488  return 0;
489  }
490  /**
491  * Set polynomial to 1
492  *
493  * @param
494  **/
495  inline void one() {
496  terms.clear();
497  UnivariateTerm<Ring> t;
498  t.coef.one();
499  t.exp = 0;
500  terms.push_back(t);
501  }
502  /**
503  * Is polynomial a constant -1
504  *
505  * @param
506  **/
507  inline bool isNegativeOne() {
508  if (terms.size() == 1 && !terms[0].exp)
509  return terms[0].coef.isNegativeOne();
510  return 0;
511  }
512  /**
513  * Set polynomial to -1
514  *
515  * @param
516  **/
517  inline void negativeOne() {
518  terms.clear();
519  UnivariateTerm<Ring> t;
520  t.coef.negativeOne();
521  t.exp = 0;
522  terms.push_back(t);
523  }
524  /**
525  * Is a constant
526  *
527  * @param
528  **/
529  inline int isConstant() {
530  if (terms.size() == 1 && !terms[0].exp)
531  return terms[0].coef.isConstant();
532  return 0;
533  }
534  /**
535  * Convert to a constant
536  *
537  * @param
538  **/
539  inline Ring convertToConstant() {
540  if (terms.size() && !terms[0].exp)
541  return terms[0].coef;
542  else {
543  Ring e;
544  e.zero();
545  return e;
546  }
547  }
548  /**
549  * Content of the polynomial
550  *
551  * @param
552  **/
553  inline Ring content() {
554  Ring c;
555  int n = terms.size();
556  if (n) {
557  c = terms[0].coef;
558  for (int i = 1; i < n; ++i) {
559  c = c.gcd(terms[i].coef);
560  if (c.isOne())
561  break;
562  }
563  }
564  //else { c.zero(); }
565  return c;
566  }
567  /**
568  * Overload operator ^
569  * replace xor operation by exponentiation
570  *
571  * @param e: The exponentiation, e > 0
572  **/
575  res.name = name;
576  //res.one();
577  //unsigned long int q = e / 2, r = e % 2;
578  //SparseUnivariatePolynomial<Ring> power2 = *this * *this;
579  //for (int i = 0; i < q; ++i)
580  // res *= power2;
581  //if (r) { res *= *this; }
582  if (isZero() || isOne() || e == 1)
583  res = *this;
584  else if (e == 2)
585  res = *this * *this;
586  else if (e > 2) {
588  res.one();
589 
590  while (e) {
591  if (e % 2) { res *= x; }
592  x = x * x;
593  e >>= 1;
594  }
595  }
596  else if (!e)
597  res.one();
598  else {
599  res = *this;
600  }
601  return res;
602  }
603  /**
604  * Overload operator ^=
605  * replace xor operation by exponentiation
606  *
607  * @param e: The exponentiation, e > 0
608  **/
610  *this = *this ^ e;
611  return *this;
612  }
613  /**
614  * Overload operator <<
615  * replace by muplitying x^k
616  *
617  * @param k: The exponent of variable, k > 0
618  **/
621  return (r <<= k);
622  }
623  /**
624  * Overload operator <<=
625  * replace by muplitying x^k
626  *
627  * @param k: The exponent of variable, k > 0
628  **/
630  for (int i = 0; i < terms.size(); ++i)
631  terms[i].exp += (unsigned long int) k;
632  return *this;
633  }
634  /**
635  * Overload operator >>
636  * replace by dividing x^k, and
637  * return the quotient
638  *
639  * @param k: The exponent of variable, k > 0
640  **/
643  return (r >>= k);
644  }
645  /**
646  * Overload operator >>=
647  * replace by dividing x^k, and
648  * return the quotient
649  *
650  * @param k: The exponent of variable, k > 0
651  **/
653  int i = 0;
654  unsigned long int e = (unsigned long int) k;
655  while (i < terms.size()) {
656  if (terms[i].exp >= e) {
657  terms[i].exp -= e;
658  i++;
659  }
660  else { terms.erase(terms.begin()); }
661  }
662  return *this;
663  }
664  /**
665  * Overload operator +
666  *
667  * @param b: A univariate polynomial
668  **/
671  return (res += b);
672  }
673  /**
674  * Overload operator+=
675  *
676  * @param b: A univariate polynomial
677  **/
679  if (!terms.size()) { return (*this = b); }
680  if (!b.terms.size()) { return *this; }
681  if (isConstant()) { return (*this = b + terms[0].coef); }
682  if (b.isConstant()) { return (*this += b.terms[0].coef); }
683  if (name != b.name) {
684  std::cout << "BPAS: error, trying to add between Ring[" << name << "] and Ring[" << b.name << "]." << std::endl;
685  exit(1);
686  }
687 
688  int ai = 0;
689  for (int i = 0; i < b.terms.size(); ++i) {
690  UnivariateTerm<Ring> bt = b.terms[i];
691  if (ai >= terms.size()) {
692  terms.push_back(bt);
693  ai++;
694  }
695  else {
696  int e1 = terms[ai].exp, e2 = bt.exp;
697  while (e1 < e2) {
698  ai++;
699  if (ai < terms.size())
700  e1 = terms[ai].exp;
701  else {
702  terms.push_back(bt);
703  ai++;
704  break;
705  }
706  }
707  if (e1 == e2) {
708  terms[ai].coef += bt.coef;
709  if (terms[ai].coef.isZero())
710  terms.erase(terms.begin()+ai);
711  else { ai++; }
712  }
713  else if (e1 > e2)
714  terms.insert(terms.begin()+ai, bt);
715  }
716  }
717  return *this;
718  }
719  /**
720  * Overload operator +
721  *
722  * @param e: A coefficient constant
723  **/
726  return (r += e);
727  }
728  /**
729  * Overload operator +=
730  *
731  * @param e: A coefficient constant
732  **/
734  if (!e.isZero()) {
735  if (terms.size()) {
736  UnivariateTerm<Ring> a = terms[0];
737  if (a.exp) {
738  a.coef = e;
739  a.exp = 0;
740  terms.insert(terms.begin(), a);
741  }
742  else {
743  terms[0].coef += e;
744  if (terms[0].coef.isZero())
745  terms.erase(terms.begin());
746  }
747  }
748  else {
749  UnivariateTerm<Ring> a;
750  a.coef = e;
751  a.exp = 0;
752  terms.push_back(a);
753  }
754  }
755  return *this;
756  }
757 
759  return (p + c);
760  }
761  /**
762  * Overload operator -, negate
763  *
764  * @param
765  **/
768  res.name = name;
769  for (int i = 0; i < terms.size(); ++i) {
770  UnivariateTerm<Ring> t;
771  t.coef = -terms[i].coef;
772  t.exp = terms[i].exp;
773  res.terms.push_back(t);
774  }
775  return res;
776  }
777  /**
778  * Subtract another polynomial
779  *
780  * @param b: A univariate polynomial
781  **/
784  return (res -= b);
785  }
786  /**
787  * Overload operator -=
788  *
789  * @param b: A univariate polynomial
790  **/
792  if (!terms.size()) { return (*this = -b); }
793  if (!b.terms.size()) { return *this; }
794  if (isConstant()) { return (*this = -b + terms[0].coef); }
795  if (b.isConstant()) { return (*this -= b.terms[0].coef); }
796  if (name != b.name) {
797  std::cout << "BPAS: error, trying to subtract between Ring[" << name << "] and Ring[" << b.name << "]." << std::endl;
798  exit(1);
799  }
800 
801  int ai = 0;
802  for (int i = 0; i < b.terms.size(); ++i) {
803  UnivariateTerm<Ring> t = b.terms[i];
804  t.coef = -t.coef;
805 
806  if (ai >= terms.size()) {
807  terms.push_back(t);
808  ai++;
809  }
810  else {
811  int e1 = terms[ai].exp, e2 = t.exp;
812  while (e1 < e2) {
813  ai++;
814  if (ai < terms.size())
815  e1 = terms[ai].exp;
816  else {
817  terms.push_back(t);
818  ai++;
819  break;
820  }
821  }
822  if (e1 == e2) {
823  terms[ai].coef += t.coef;
824  if (terms[ai].coef.isZero())
825  terms.erase(terms.begin()+ai);
826  else { ai++; }
827  }
828  else if (e1 > e2)
829  terms.insert(terms.begin()+ai, t);
830  }
831  }
832  return *this;
833  }
834  /**
835  * Overload operator -
836  *
837  * @param e: A coefficient constant
838  **/
841  return (r -= e);
842  }
843  /**
844  * Overload operator -=
845  *
846  * @param e: A coefficient constant
847  **/
849  if (!e.isZero()) {
850  if (terms.size()) {
851  UnivariateTerm<Ring> t = terms[0];
852  if (t.exp) {
853  t.coef = -e;
854  t.exp = 0;
855  terms.insert(terms.begin(), t);
856  }
857  else {
858  terms[0].coef -= e;
859  if (terms[0].coef.isZero())
860  terms.erase(terms.begin());
861  }
862  }
863  else {
864  UnivariateTerm<Ring> t;
865  t.coef = -e;
866  t.exp = 0;
867  terms.push_back(t);
868  }
869  }
870  return *this;
871  }
873  return (-p + c);
874  }
875  /**
876  * Multiply another polynomial
877  *
878  * @param b: A univariate polynomial
879  **/
881  int n = terms.size(), m = b.terms.size();
882  if (!n)
883  return *this;
884  if (!m)
885  return b;
886 
888  if (!degree()) {
889  for (int i = 0; i < m; ++i) {
890  UnivariateTerm<Ring> bt = b.terms[i];
891  UnivariateTerm<Ring> t;
892  t.coef = terms[0].coef * bt.coef;
893  t.exp = bt.exp;
894  res.terms.push_back(t);
895  }
896  res.name = b.name;
897  return res;
898  }
899  res.name = name;
900  if (!b.degree()) {
901  UnivariateTerm<Ring> bt = b.terms[0];
902  for (int i = 0; i < n; ++i) {
903  UnivariateTerm<Ring> t;
904  t.coef = terms[i].coef * bt.coef;
905  t.exp = terms[i].exp;
906  res.terms.push_back(t);
907  }
908  return res;
909  }
910 
911  if (name != b.name) {
912  std::cout << "BPAS: error, trying to multiply between Ring[" << name << "] and Ring[" << b.name << "]." << std::endl;
913  exit(1);
914  }
915 
916  if (n + m < 64) {
917  if (n <= m) {
918  for (int i = 0; i < n; ++i)
919  res.pomopo(terms[i], b);
920  }
921  else {
922  for (int i = 0; i < m; ++i)
923  res.pomopo(b.terms[i], *this);
924  }
925  }
926  else {
927  int s = (m > n) ? m : n;
928  s >>= 1;
930  f0.name = f1.name = name;
931  for (int i = 0; i < n; ++i) {
932  if (terms[i].exp < s)
933  f0.terms.push_back(terms[i]);
934  else {
935  UnivariateTerm<Ring> t (terms[i].coef, terms[i].exp-s);
936  f1.terms.push_back(t);
937  }
938  }
940  g0.name = g1.name = name;
941  for (int i = 0; i < m; ++i) {
942  if (b.terms[i].exp < s)
943  g0.terms.push_back(b.terms[i]);
944  else {
945  UnivariateTerm<Ring> t (b.terms[i].coef, b.terms[i].exp-s);
946  g1.terms.push_back(t);
947  }
948  }
950  t0.name = t1.name = name;
951  n = f0.terms.size(), m = g0.terms.size();
952  if (n <= m) {
953  for (int i = 0; i < n; ++i)
954  res.pomopo(f0.terms[i], g0);
955  }
956  else {
957  for (int i = 0; i < m; ++i)
958  res.pomopo(g0.terms[i], f0);
959  }
960  n = f1.terms.size(), m = g1.terms.size();
961  if (n <= m) {
962  for (int i = 0; i < n; ++i)
963  t0.pomopo(f1.terms[i], g1);
964  }
965  else {
966  for (int i = 0; i < m; ++i)
967  t0.pomopo(g1.terms[i], f1);
968  }
969  f0 += f1, g0 += g1;
970  n = f0.terms.size(), m = g0.terms.size();
971  if (n <= m) {
972  for (int i = 0; i < n; ++i)
973  t1.pomopo(f0.terms[i], g0);
974  }
975  else {
976  for (int i = 0; i < m; ++i)
977  t1.pomopo(g0.terms[i], f0);
978  }
979  t1 -= res + t0;
980  for (int i = 0; i < t1.terms.size(); ++i)
981  t1.terms[i].exp += s;
982  s <<= 1;
983  for (int i = 0; i < t0.terms.size(); ++i)
984  t0.terms[i].exp += s;
985  res += t0 + t1;
986  }
987  return res;
988  }
989  /**
990  * Overload operator *=
991  *
992  * @param b: A univariate polynomial
993  **/
995  *this = *this * b;
996  return *this;
997  }
998  /**
999  * Overload operator *
1000  *
1001  * @param c: A coefficient
1002  **/
1005  return (r *= c);
1006  }
1009  return (r *= e);
1010  }
1011  /**
1012  * Overload operator *=
1013  *
1014  * @param c: A coefficient
1015  **/
1017  if (!isZero()) {
1018  if (!c.isZero() && !c.isOne()) {
1019  for (int i = 0; i < terms.size(); ++i)
1020  terms[i].coef *= c;
1021  }
1022  else if (c.isZero())
1023  terms.clear();
1024  }
1025  return *this;
1026  }
1028  if (e != 0 && e != 1) {
1029  for (int i = 0; i < terms.size(); ++i)
1030  terms[i].coef *= e;
1031  }
1032  else if (e == 0) { zero(); }
1033  return *this;
1034  }
1036  return (p * e);
1037  }
1039  return (p * e);
1040  }
1041  /**
1042  * Overload operator /
1043  * EdeDivision
1044  *
1045  * @param b: A univariate polynomial
1046  **/
1049  return (rem /= b);
1050  }
1051 
1052  /**
1053  * Overload operator /=
1054  * ExactDivision
1055  *
1056  * @param b: A univariate polynomial
1057  **/
1059  if (b.isZero()) {
1060  std::cout << "BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1061  exit(1);
1062  }
1063  if (b.isConstant()) { return (*this /= b.terms[0].coef); }
1064  if (isConstant()) {
1065  zero();
1066  return *this;
1067  }
1068  if (name != b.name) {
1069  std::cout << "BPAS: error, trying to exact divide between Ring[" << name << "] and Ring[" << b.name << "]." << std::endl;
1070  exit(1);
1071  }
1072 
1074  q.name = name;
1075 
1076  int db = b.degree();
1077  UnivariateTerm<Ring> bt = b.leadingTerm();
1078 
1079  if (db == 1 && bt.coef.isOne()) {
1080  if (b.terms.size() > 1) {
1081  int k = 0;
1082  Ring e, prev;
1083  UnivariateTerm<Ring> t, at = leadingTerm();
1084  if (!terms[0].exp) {
1085  prev = t.coef = terms[0].coef / b.terms[0].coef;
1086  t.exp = 0;
1087  q.terms.push_back(t);
1088  k++;
1089  }
1090  else { prev.zero(); }
1091  for (int i = 1; i < at.exp; ++i) {
1092  if (k < terms.size() && terms[k].exp == i) {
1093  e = terms[k].coef;
1094  k++;
1095  }
1096  else { e.zero(); }
1097  t.coef = (e - prev) / b.terms[0].coef;
1098  if (!t.coef.isZero()) {
1099  t.exp = i;
1100  q.terms.push_back(t);
1101  }
1102  prev = t.coef;
1103  }
1104  if (prev == at.coef)
1105  return (*this = q);
1106  else {
1107  std::cout << "BPAS: error, not exact division in SparseUnivariatePolynomial<Ring>." << std::endl;
1108  exit(1);
1109  }
1110  }
1111  else {
1112  if (!terms[0].exp) {
1113  std::cout << "BPAS: error, not exact division in SparseUnivariatePolynomial<Ring>." << std::endl;
1114  exit(1);
1115  }
1116  else {
1117  for (int i = 0; i < terms.size(); ++i)
1118  terms[i].exp--;
1119  return *this;
1120  }
1121  }
1122  }
1123 
1124  while (!isZero() && degree() >= db) {
1125  UnivariateTerm<Ring> at = leadingTerm();
1126  UnivariateTerm<Ring> lc, nlc;
1127  lc.coef = at.coef / bt.coef;
1128  lc.exp = at.exp - bt.exp;
1129  nlc.coef = -lc.coef;
1130  nlc.exp = lc.exp;
1131  pomopo(nlc, b);
1132  q.terms.insert(q.terms.begin(), lc);
1133  }
1134  if (!isZero()) {
1135  std::cout << "BPAS: error, not exact division in SparseUnivariatePolynomial<Ring>." << std::endl;
1136  exit(1);
1137  }
1138  return (*this = q);
1139  }
1140  /**
1141  * Overload operator /
1142  *
1143  * @param e: A coefficient constant
1144  **/
1147  return (r /= e);
1148  }
1149  /**
1150  * Overload operator /=
1151  *
1152  * @param e: A coefficient constant
1153  **/
1155  if (e.isZero()) {
1156  std::cout << "BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1157  exit(1);
1158  }
1159  else if (!e.isOne()) {
1160  int i = 0;
1161  while (i < terms.size()) {
1162  terms[i].coef /= e;
1163  if (terms[i].coef.isZero())
1164  terms.erase(terms.begin()+i);
1165  else { ++i; }
1166  }
1167  }
1168  return *this;
1169  }
1171  if (p.isZero()) {
1172  std::cout << "BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1173  exit(1);
1174  }
1176  q.name = p.name;
1177 
1178  if (p.isConstant()) {
1179  q += e;
1180  return (q /= p.terms[0].coef);
1181  }
1182  else { return q; }
1183  }
1184  /**
1185  * Negate the polynomial
1186  *
1187  * @param
1188  **/
1189  inline void negate() {
1190  for (int i = 0; i < terms.size(); ++i)
1191  terms[i].coef = -terms[i].coef;
1192  }
1193  /**
1194  * Monic division
1195  * Assuming the leading coefficient of dividend is 1
1196  * Return quotient and itself becomes remainder
1197  *
1198  * @param b: The dividend polynomial
1199  **/
1201  if (b.isZero()) {
1202  std::cout << "BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1203  exit(1);
1204  }
1205  else if (!b.leadingCoefficient().isOne()) {
1206  std::cout << "BPAS: error, leading coefficient is not one in monicDivide() from SparseUnivariatePolynomial<Ring>." << std::endl;
1207  exit(1);
1208  }
1209 
1210  if (b.isConstant()) {
1212  zero();
1213  return r;
1214  }
1215  if (isConstant()) {
1217  r.zero();
1218  return r;
1219  }
1220  if (name != b.name) {
1221  std::cout << "BPAS: error, trying to monic divide between Ring[" << name << "] and Ring[" << b.name << "]." << std::endl;
1222  exit(1);
1223  }
1224 
1226  quo.name = name;
1227  UnivariateTerm<Ring> bt = b.leadingTerm();
1228  while (degree() >= b.degree()) {
1229  UnivariateTerm<Ring> at = leadingTerm();
1230  UnivariateTerm<Ring> nlc;
1231  nlc.coef = -at.coef;
1232  nlc.exp = at.exp - bt.exp;
1233  pomopo(nlc, b);
1234  at.exp = nlc.exp;
1235  quo.terms.insert(quo.terms.begin(), at);
1236  }
1237  return quo;
1238  }
1239  /**
1240  * Monic division
1241  * Assuming the leading coefficient of dividend is 1
1242  * Return quotient
1243  *
1244  * @param b: The dividend polynomial
1245  * @param rem: The remainder polynomial
1246  **/
1248  *rem = *this;
1249  return rem->monicDivide(b);
1250  }
1251  /**
1252  * Lazy pseudo dividsion
1253  * Return the quotient and itself becomes remainder
1254  * e is the exact number of division steps
1255  *
1256  * @param b: The dividend polynomial
1257  * @param c: The leading coefficient of b to the power e
1258  * @param d: That to the power deg(a) - deg(b) + 1 - e
1259  **/
1261  if (d == NULL)
1262  d = new Ring;
1263  int da = degree(), db = b.degree();
1264  if (b.isZero() || !db) {
1265  std::cout << "BPAS: error, dividend is zero or constant from SparseUnivariatePolynomial<Ring>." << std::endl;
1266  exit(1);
1267  }
1268  c->one(), d->one();
1269  if (isConstant()) {
1271  r.zero();
1272  return r;
1273  }
1274  if (name != b.name) {
1275  std::cout << "BPAS: error, trying to pseudo divide between Ring[" << name << "] and Ring[" << b.name << "]." << std::endl;
1276  exit(1);
1277  }
1278 
1279  if (da < db) {
1281  r.name = name;
1282  return r;
1283  }
1284 
1286  quo.name = name;
1287  Ring blc = b.leadingTerm().coef;
1288 
1289  int e = 0, diff = da - db;
1290  while (degree() >= db) {
1291  UnivariateTerm<Ring> at = leadingTerm();
1292  UnivariateTerm<Ring> nlc;
1293  nlc.coef = -at.coef;
1294  nlc.exp = at.exp - db;
1295 
1296  *c *= blc;
1297  e++;
1298  pomopo(blc, nlc, b);
1299  at.exp = nlc.exp;
1300  quo.terms.insert(quo.terms.begin(), at);
1301  }
1302  for (int i = e; i <= diff; ++i)
1303  *d *= blc;
1304  return quo;
1305  }
1306  /**
1307  * Lazy pseudo dividsion
1308  * Return the quotient
1309  * e is the exact number of division steps
1310  *
1311  * @param b: The divident polynomial
1312  * @param rem: The remainder polynomial
1313  * @param c: The leading coefficient of b to the power e
1314  * @param d: That to the power deg(a) - deg(b) + 1 - e
1315  **/
1317  *rem = *this;
1318  return rem->lazyPseudoDivide(b, c, d);
1319  }
1320  /**
1321  * Pseudo dividsion
1322  * Return the quotient and itself becomes remainder
1323  *
1324  * @param b: The divident polynomial
1325  * @param d: The leading coefficient of b
1326  * to the power deg(a) - deg(b) + 1
1327  **/
1329  Ring c;
1330  if (d == NULL)
1331  d = new Ring;
1333  quo *= *d;
1334  *this *= *d;
1335  *d *= c;
1336  return quo;
1337  }
1338  /**
1339  * Pseudo dividsion
1340  * Return the quotient
1341  *
1342  * @param b: The divident polynomial
1343  * @param rem: The remainder polynomial
1344  * @param d: The leading coefficient of b
1345  * to the power deg(a) - deg(b) + 1
1346  **/
1348  Ring c;
1350  quo *= *d;
1351  *rem *= *d;
1352  *d *= c;
1353  return quo;
1354  }
1355  /**
1356  * Compute k-th derivative
1357  *
1358  * @param k: k-th derivative
1359  **/
1360  inline void differentiate(int k) {
1361  if (k <= 0) { return; }
1362  int i = 0;
1363  while (i < terms.size()) {
1364  if (terms[i].exp >= k) {
1365  for (int j = 0; j < k; ++j)
1366  terms[i].coef *= (terms[i].exp - j);
1367  terms[i].exp -= k;
1368  i++;
1369  }
1370  else
1371  terms.erase(terms.begin());
1372  }
1373  }
1374  /**
1375  * Compute integral with constant of integration set to 0
1376  *
1377  * @param
1378  **/
1381  int i = t.terms.size()-1;
1382  while (i > -1) {
1383  t.terms[i].coef /= (t.terms[i].exp + 1);
1384  t.terms[i].exp += 1;
1385  i--;
1386  }
1387  return t;
1388  }
1389  /**
1390  * Is trailing coefficient zero
1391  *
1392  * @param
1393  **/
1395  if (isZero())
1396  return 1;
1397  int n = terms.size();
1398  if (n && terms[0].exp > 0)
1399  return 1;
1400  return 0;
1401  }
1402  /**
1403  * Evaluate f(x)
1404  *
1405  * @param x: Evaluation point
1406  **/
1407  inline Ring evaluate(Ring x) {
1408  int d = terms.size() - 1;
1409  if (d < 0) { return Ring(); }
1410  int e = terms[d].exp - 1;
1411  Ring px = terms[d].coef;
1412  d--;
1413  for (int i = e; i > -1; --i) {
1414  px *= x;
1415  if (i == terms[d].exp && d > -1) {
1416  px += terms[d].coef;
1417  d--;
1418  }
1419  }
1420  return px;
1421  }
1422 
1423  /**
1424  * Subresultant Chain
1425  * Return the list of subresultants
1426  *
1427  * @param q: The other sparse univariate polynomial
1428  **/
1429  inline std::vector< SparseUnivariatePolynomial<Ring> > subresultantChain (SparseUnivariatePolynomial<Ring>& q) {
1430  if (name != q.name) {
1431  std::cout << "BPAS: error, trying to compute subresultant chains between Ring[" << name << "] and Ring[" << q.name << "]." << std::endl;
1432  exit(1);
1433  }
1434 
1435  std::vector< SparseUnivariatePolynomial<Ring> > S;
1437  if (q.degree() > degree()) {
1438  a = q;
1439  b = *this;
1440  }
1441  else {
1442  a = *this;
1443  b = q;
1444  }
1445  int k = a.degree() - b.degree();
1446  Ring s = b.leadingCoefficient() ^ k;
1447 
1448  SparseUnivariatePolynomial<Ring> A = b, B = a, C = -b;
1449  B.pseudoDivide(C);
1450  int delta = 0;
1451  while (B.degree()) {
1452  delta = A.degree() - B.degree();
1453  S.insert(S.begin(), B);
1454  if (delta > 1) {
1455  if (S.size() < 2)
1456  C = LazardSe(A, B);
1457  else
1458  C = LazardSe(S[1], S[0]);
1459  S.insert(S.begin(), C);
1460  }
1461  else { C = B; }
1462  B = DucosSem(A, B, C, s);
1463  A = C;
1464  s = A.leadingCoefficient();
1465  }
1466  S.insert(S.begin(), B);
1467  if (B.isZero()) {
1468  while (S.size() < b.degree())
1469  S.insert(S.begin(), B);
1470  }
1471  return S;
1472  }
1473  /**
1474  * Resultant
1475  *
1476  * @param q: The other sparse univariate polynomial
1477  **/
1479  std::vector< SparseUnivariatePolynomial<Ring> > s = subresultantChain(q);
1480  return s[0];
1481  }
1482  /**
1483  * GCD(p, q)
1484  *
1485  * @param q: The other polynomial
1486  **/
1488  if (isZero()) { return q; }
1489  if (q.isZero()) { return *this; }
1490  if (name != q.name) {
1491  std::cout << "BPAS: error, trying to compute GCD between Ring[" << name << "] and Ring[" << q.name << "]." << std::endl;
1492  exit(1);
1493  }
1494 
1495  SparseUnivariatePolynomial<Ring> a(*this), b(q);
1496  if (a.degree() == 0 || b.degree() == 0) {
1497  a.one();
1498  return a;
1499  }
1500 
1502  r.name = name;
1503 
1504 //std::cout << "is_same: " << std::is_same<Ring, RationalNumber>::value << std::endl;
1505  Ring rng;
1506  if (rng.isPrimeField == 1) {
1507  DenseUnivariateRationalPolynomial f = a.convertToDUQP();
1508  DenseUnivariateRationalPolynomial g = b.convertToDUQP();
1511  }
1512  else {
1513  Ring ca, cb, cr;
1514  ca = a.content();
1515  a /= ca;
1516  cb = b.content();
1517  b /= cb;
1518  std::vector< SparseUnivariatePolynomial<Ring> > R = a.subresultantChain(b);
1519 
1520  r.setCoefficient(0, ca);
1521  r *= cb;
1522  int n = R.size();
1523  bool isZero = 0;
1524  if (n) {
1525  isZero = 1;
1526  for (int i = 0; i < n; ++i) {
1527  if (!R[i].isZero()) {
1528  cr = R[i].content();
1529  R[i] /= cr;
1530  r *= R[i];
1531  isZero = 0;
1532  break;
1533  }
1534  }
1535  }
1536  if (isZero) {
1537  if (a.degree() <= b.degree()) { r *= a; }
1538  else { r *= b; }
1539  }
1540  }
1541  return r;
1542  }
1543  /**
1544  * Square free
1545  *
1546  * @param
1547  **/
1548  inline std::vector< SparseUnivariatePolynomial<Ring> > squareFree() {
1549  std::vector< SparseUnivariatePolynomial<Ring> > sf;
1550  int d = terms.size()-1;
1551  if (!terms[d].exp)
1552  sf.push_back(*this);
1553  else if (terms[d].exp == 1) {
1555  t.name = name;
1556  t += terms[d].coef;
1557  sf.push_back(t);
1558  t = *this / terms[d].coef;
1559  sf.push_back(t);
1560  }
1561  else {
1562  SparseUnivariatePolynomial<Ring> a (*this), b(*this);
1563  b.differentiate(1);
1565  g /= g.content();
1569  z.differentiate(1);
1570  z += y;
1571 
1572  while (!z.isZero()) {
1573  g = x.gcd(z);
1574  g /= g.content();
1575  sf.push_back(g);
1576  x /= g;
1577  y = z / g;
1578  z = -x;
1579  z.differentiate(1);
1580  z += y;
1581  }
1582  sf.push_back(x);
1583 
1584  Ring e;
1585  e.one();
1586  for (int i = 0; i < sf.size(); ++i) {
1587  e *= sf[i].leadingCoefficient();
1588  sf[i] /= sf[i].leadingCoefficient();
1589  }
1591  t.name = name;
1592  t += e;
1593  sf.insert(sf.begin(), t);
1594  }
1595  return sf;
1596  }
1597  /**
1598  * Overload stream operator <<
1599  *
1600  * @param out: Stream object
1601  * @param b: The univariate polynomial
1602  **/
1603  inline friend std::ostream& operator<< (std::ostream &out, SparseUnivariatePolynomial<Ring> b) {
1604  int n = b.terms.size();
1605  if (!n) { out << "0"; }
1606  for (int i = 0; i < n; ++i) {
1607  if (b.terms[i].exp) {
1608  if (b.terms[i].coef.isNegativeOne())
1609  out << "-";
1610  else if (i && b.terms[i].coef.isConstant() >= 0)
1611  out << "+";
1612  if (!b.terms[i].coef.isConstant())
1613  out << "(" << b.terms[i].coef << ")*";
1614  else if (!b.terms[i].coef.isOne() && !b.terms[i].coef.isNegativeOne())
1615  out << b.terms[i].coef << "*";
1616  out << b.name;
1617  if (b.terms[i].exp > 1)
1618  out << "^" << b.terms[i].exp;
1619  }
1620  else {
1621  if (b.terms[i].coef.isConstant()) { out << b.terms[i].coef; }
1622  else { out << "(" << b.terms[i].coef << ")"; }
1623  }
1624  }
1625  return out;
1626  }
1627 
1628  inline DenseUnivariateRationalPolynomial convertToDUQP() {
1629  bool isDense = 1;
1630  int k = 0, n = terms.size(), d = 0;
1631  if (n) { d = terms[n-1].exp; }
1633  res.setVariableName(name);
1634  for (int i = 0; i <= d; ++i) {
1635  if (k < n) {
1636  if (!terms[k].coef.isConstant()) {
1637  isDense = 0;
1638  break;
1639  }
1640  else if (terms[k].exp == i) {
1641  res.setCoefficient(i, RationalNumber(terms[k].coef));
1642  k++;
1643  }
1644  }
1645  }
1646  if (!isDense) { res.zero(); }
1647  return res;
1648  }
1649  inline DenseUnivariateIntegerPolynomial convertToDUZP() {
1650  bool isDense = 1;
1651  int k = 0, n = terms.size(), d = 0;
1652  if (n) { d = terms[n-1].exp; }
1654  res.setVariableName(name);
1655  for (int i = 0; i <= d; ++i) {
1656  if (k < n) {
1657  if (!terms[k].coef.isConstant()) {
1658  isDense = 0;
1659  break;
1660  }
1661  else if (terms[k].exp == i) {
1662  res.setCoefficient(i, Integer(terms[k].coef));
1663  k++;
1664  }
1665  }
1666  }
1667  if (!isDense) { res.zero(); }
1668  return res;
1669  }
1670 };
1671 
1672 #endif
1673 /* This file is part of the BPAS library http://www.bpaslib.org
1674 
1675  BPAS is free software: you can redistribute it and/or modify
1676  it under the terms of the GNU General Public License as published by
1677  the Free Software Foundation, either version 3 of the License, or
1678  (at your option) any later version.
1679 
1680  BPAS is distributed in the hope that it will be useful,
1681  but WITHOUT ANY WARRANTY; without even the implied warranty of
1682  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1683  GNU General Public License for more details.
1684 
1685  You should have received a copy of the GNU General Public License
1686  along with BPAS. If not, see <http://www.gnu.org/licenses/>.
1687 
1688  Copyright: Changbo Chen <changbo.chen@hotmail.com>
1689  Farnam Mansouri <mansouri.farnam@gmail.com>
1690  Marc Moreno Maza <moreno@csd.uwo.ca>
1691  Ning Xie <nxie6@csd.uwo.ca>
1692  Yuzhen Xie <yuzhenxie@yahoo.ca>
1693 
1694 */
1695 
1696 
bool isZero()
Definition: upolynomial.h:469
void negate()
Definition: upolynomial.h:1189
Definition: upolynomial.h:10
std::string variable()
Definition: urpolynomial.h:206
SparseUnivariatePolynomial< Ring > & operator*=(SparseUnivariatePolynomial< Ring > b)
Definition: upolynomial.h:994
SparseUnivariatePolynomial< Ring > operator^(int e)
Definition: upolynomial.h:573
std::vector< SparseUnivariatePolynomial< Ring > > subresultantChain(SparseUnivariatePolynomial< Ring > &q)
Definition: upolynomial.h:1429
void differentiate(int k)
Definition: upolynomial.h:1360
SparseUnivariatePolynomial< Ring > monicDivide(SparseUnivariatePolynomial< Ring > &b)
Definition: upolynomial.h:1200
SparseUnivariatePolynomial< Ring > pseudoDivide(SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem, Ring *d)
Definition: upolynomial.h:1347
void one()
Definition: upolynomial.h:495
Definition: ring.h:290
SparseUnivariatePolynomial< Ring > monicDivide(SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem)
Definition: upolynomial.h:1247
SparseUnivariatePolynomial< Ring > & operator+=(SparseUnivariatePolynomial< Ring > b)
Definition: upolynomial.h:678
std::vector< SparseUnivariatePolynomial< Ring > > squareFree()
Definition: upolynomial.h:1548
SparseUnivariatePolynomial< Ring > & operator>>=(int k)
Definition: upolynomial.h:652
SparseUnivariatePolynomial< Ring > operator+(SparseUnivariatePolynomial< Ring > &b)
Definition: upolynomial.h:669
Definition: uzpolynomial.h:12
int numberOfTerms()
Definition: upolynomial.h:339
bool isTrailingCoefficientZero()
Definition: upolynomial.h:1394
Ring convertToConstant()
Definition: upolynomial.h:539
SparseUnivariatePolynomial< Ring > operator<<(int k)
Definition: upolynomial.h:619
Definition: urpolynomial.h:16
SparseUnivariatePolynomial< Ring > lazyPseudoDivide(SparseUnivariatePolynomial< Ring > &b, Ring *c, Ring *d=NULL)
Definition: upolynomial.h:1260
std::string variable()
Definition: uzpolynomial.h:163
mpz_class coefficient(int k)
Definition: uzpolynomial.h:130
void negativeOne()
Definition: upolynomial.h:517
bool operator!=(SparseUnivariatePolynomial< Ring > &b)
Definition: upolynomial.h:446
SparseUnivariatePolynomial< Ring > & operator^=(int e)
Definition: upolynomial.h:609
bool isNegativeOne()
Definition: upolynomial.h:507
SparseUnivariatePolynomial< Ring > & operator=(SparseUnivariatePolynomial< Ring > b)
Definition: upolynomial.h:431
Ring coefficient(int k)
Definition: upolynomial.h:367
Definition: ring.h:48
Definition: polynomial.h:30
SparseUnivariatePolynomial< Ring > integrate()
Definition: upolynomial.h:1379
SparseUnivariatePolynomial< Ring > & operator<<=(int k)
Definition: upolynomial.h:629
Ring content()
Definition: upolynomial.h:553
SparseUnivariatePolynomial< Ring > resultant(SparseUnivariatePolynomial< Ring > &q)
Definition: upolynomial.h:1478
void zero()
Definition: upolynomial.h:477
Ring evaluate(Ring x)
Definition: upolynomial.h:1407
SparseUnivariatePolynomial< Ring > operator-()
Definition: upolynomial.h:766
void setCoefficient(int e, Ring c)
Definition: upolynomial.h:383
void setVariableName(std::string c)
Definition: upolynomial.h:422
int isConstant()
Definition: upolynomial.h:529
Ring leadingCoefficient()
Definition: upolynomial.h:357
SparseUnivariatePolynomial< Ring > gcd(SparseUnivariatePolynomial< Ring > &q)
Definition: upolynomial.h:1487
SparseUnivariatePolynomial< Ring > operator*(SparseUnivariatePolynomial< Ring > b)
Definition: upolynomial.h:880
Definition: ring.h:166
int degree()
Definition: upolynomial.h:347
mpq_class coefficient(int k)
Definition: urpolynomial.h:174
bool isOne()
Definition: upolynomial.h:485
SparseUnivariatePolynomial< Ring > lazyPseudoDivide(SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem, Ring *c, Ring *d)
Definition: upolynomial.h:1316
DenseUnivariateRationalPolynomial gcd(DenseUnivariateRationalPolynomial q, int type=0)
int degree()
Definition: uzpolynomial.h:101
SparseUnivariatePolynomial< Ring > operator>>(int k)
Definition: upolynomial.h:641
SparseUnivariatePolynomial< Ring > & operator-=(SparseUnivariatePolynomial< Ring > b)
Definition: upolynomial.h:791
SparseUnivariatePolynomial< Ring > operator/(SparseUnivariatePolynomial< Ring > &b)
Definition: upolynomial.h:1047
std::string variable()
Definition: upolynomial.h:414
SparseUnivariatePolynomial< Ring > pseudoDivide(SparseUnivariatePolynomial< Ring > &b, Ring *d=NULL)
Definition: upolynomial.h:1328
int degree()
Definition: urpolynomial.h:145
SparseUnivariatePolynomial< Ring > & operator/=(SparseUnivariatePolynomial< Ring > b)
Definition: upolynomial.h:1058
bool operator==(SparseUnivariatePolynomial< Ring > &b)
Definition: upolynomial.h:454