1 #ifndef _UPOLYNOMIAL_H_ 2 #define _UPOLYNOMIAL_H_ 5 #include "../polynomial.h" 6 #include "../IntegerPolynomial/uzpolynomial.h" 7 #include "../RationalNumberPolynomial/urpolynomial.h" 8 #include "../Utils/TemplateHelpers.hpp" 9 #include "../Utils/RandomHelpers.hpp" 46 private Derived_from<Ring, BPASRing<Ring>> {
54 std::vector< UnivariateTerm<Ring> > terms;
57 if (
degree() > 0 && b.degree() > 0 && (name != b.name))
60 int m = b.terms.size();
63 for (
int i = 0; i < n; ++i) {
64 UnivariateTerm<Ring> t = b.terms[i];
65 if (terms[i].coef != t.coef || terms[i].exp != t.exp)
77 n = terms.size(), m++;
79 for (
int i = 0; i < m; ++i) {
80 if (k < n && terms[k].exp == i) {
97 n = terms.size(), m++;
99 for (
int i = 0; i < m; ++i) {
100 if (k < n && terms[k].exp == i) {
113 int ai = 0, m = b.terms.size();
114 int n = terms.size();
173 const UnivariateTerm<Ring>* bterms = b.terms.data();
174 Ring prodCoef, tcoef = t.coef;
175 int prodExp, tExp = t.exp, aExp;
176 for (
int i = 0; i < m; ++i) {
177 prodCoef = tcoef * bterms[i].coef;
178 prodExp = tExp + bterms[i].exp;
180 if (ai >= terms.size()) {
181 terms.emplace_back(prodCoef, prodExp);
184 aExp = terms[ai].exp;
185 while (aExp < prodExp) {
187 if (ai < terms.size())
188 aExp = terms[ai].exp;
190 terms.emplace_back(prodCoef, prodExp);
195 if (aExp == prodExp) {
196 terms[ai].coef += prodCoef;
197 if (!terms[ai].coef.isZero()) {
200 terms.erase(terms.begin()+ai);
203 else if (aExp > prodExp) {
204 terms.emplace(terms.begin()+ai, prodCoef, prodExp);
213 int ai = 0, m = b.terms.size();
215 for (
int i = 0; i < m; ++i) {
216 UnivariateTerm<Ring> product;
217 product.coef = t.coef * b.terms[i].coef;
218 product.exp = t.exp + b.terms[i].exp;
220 if (ai >= terms.size()) {
221 terms.push_back(product);
225 int e1 = terms[ai].exp, e2 = product.exp;
229 if (ai < terms.size())
232 terms.push_back(product);
239 terms[ai].coef += product.coef;
240 if (terms[ai].coef.isZero())
241 terms.erase(terms.begin()+ai);
245 terms.insert(terms.begin()+ai, product);
250 for (
int i = ai; i < terms.size(); ++i)
257 int n = (sd.degree() - sdm.degree()).get_si() - 1;
258 if (!n) {
return sdm; }
259 Ring x = sdm.leadingCoefficient();
261 int a = (int) pow(2, floor(log2(n)));
287 int e = sdm.degree().get_si();
290 Ring ec = se.leadingCoefficient();
300 Ring dc = a.leadingCoefficient();
307 rTemp = a.coefficient(e);
314 rTemp = se.coefficient(e-1);
316 supTemp.setCoefficient(0,rTemp);
318 supTemp.setCoefficient(1,rTemp);
327 Ring mc = sdm.leadingCoefficient();
329 for (
int i = 0; i < e; ++i) {
330 P[i].setVariableName(name);
331 P[i].setCoefficient(i, ec);
333 for (
int i = e+1; d > i; ++i)
335 P[e].setVariableName(name);
336 P[e].setCoefficient(e, ec);
339 res.setCoefficient(1, ec);
340 UnivariateTerm<Ring> t (ec, 1);
341 for(
int i = e+1; i < d; ++i) {
343 ec = -P[i-1].coefficient(e-1);
352 P[i].pomopo(t, P[i-1]);
354 res *= P[d.get_si()-1];
357 for (
int i = 0; i < d; ++i) {
358 P[i] *= a.coefficient(i);
361 D /= a.leadingCoefficient();
364 ec = -res.coefficient(e);
369 res.pomopo(mc, t, D);
374 if ((d - e + 1) % 2 == 1) {
381 inline UnivariateTerm<Ring> leadingTerm()
const {
382 int n = terms.size();
383 if (n) {
return terms[n-1]; }
384 else {
return UnivariateTerm<Ring>(); }
388 mpz_class characteristic;
399 characteristic = e.characteristic;
409 characteristic = e.characteristic;
413 UnivariateTerm<Ring> t;
419 UnivariateTerm<Ring> t;
425 UnivariateTerm<Ring> t;
432 UnivariateTerm<Ring> t;
439 for (
int i = 0; i <= b.degree().get_si(); ++i) {
440 Ring e (
Integer(b.coefficient(i)));
442 UnivariateTerm<Ring> t;
452 for (
int i = 0; i <= b.degree().get_si(); ++i) {
455 UnivariateTerm<Ring> t;
492 int n = terms.size();
493 if (n) {
return terms[n-1].exp; }
503 int n = terms.size();
504 if (n) {
return terms[n-1].coef; }
505 else {
return Ring(); }
508 inline Ring trailingCoefficient()
const {
509 int n = terms.size();
511 return terms[0].coef;
523 int n = terms.size();
524 for (
int i = 0; i < n; ++i) {
525 if (k == terms[i].exp)
526 return terms[i].coef;
527 else if (k < terms[i].exp)
540 UnivariateTerm<Ring> b;
545 int k = terms.size() - 1;
546 if ((k < 0 || b.exp > terms[k].exp) && !c.isZero())
549 for (
int i = 0; i <= k; ++i) {
550 int e1 = terms[i].exp, e2 = b.exp;
552 terms[i].coef = b.coef;
553 if (terms[i].coef.isZero())
554 terms.erase(terms.begin()+i);
559 terms.insert(terms.begin()+i, b);
587 Ring canon = lead.unitCanonical(&ru, &rv);
610 characteristic = e.characteristic;
622 UnivariateTerm<Ring> t;
635 return !(isEqual(b));
661 return !(terms.size());
679 if (terms.size() == 1 && !terms[0].exp)
680 return terms[0].coef.isOne();
691 UnivariateTerm<Ring> t;
703 if (terms.size() == 1 && !terms[0].exp)
704 return terms[0].coef.isNegativeOne();
715 UnivariateTerm<Ring> t;
716 t.coef.negativeOne();
727 if (terms.size() == 1 && !terms[0].exp)
728 return terms[0].coef.isConstant();
738 if (terms.size() && !terms[0].exp)
739 return terms[0].coef;
754 int n = terms.size();
757 for (
int i = 1; i < n; ++i) {
758 c = c.gcd(terms[i].coef);
769 std::cerr <<
"BPAS ERROR: SUP<Ring>::primitivePart NOT YET IMPLEMENTED" << std::endl;
797 if (e % 2) { res *= x; }
839 for (
int i = 0; i < terms.size(); ++i)
840 terms[i].exp += (
unsigned long int) k;
865 unsigned long int e = (
unsigned long int) k;
866 while (i < terms.size()) {
867 if (terms[i].exp >= e) {
871 else { terms.erase(terms.begin()); }
892 if (!terms.size()) {
return (*
this = b); }
893 if (!b.terms.size()) {
return *
this; }
894 if (
isConstant()) {
return (*
this = b + terms[0].coef); }
895 if (b.isConstant()) {
return (*
this += b.terms[0].coef); }
896 if (name != b.name) {
897 std::cout <<
"BPAS: error, trying to add between Ring[" << name <<
"] and Ring[" << b.name <<
"]." << std::endl;
902 for (
int i = 0; i < b.terms.size(); ++i) {
903 UnivariateTerm<Ring> bt = b.terms[i];
904 if (ai >= terms.size()) {
909 int e1 = terms[ai].exp, e2 = bt.exp;
912 if (ai < terms.size())
921 terms[ai].coef += bt.coef;
922 if (terms[ai].coef.isZero())
923 terms.erase(terms.begin()+ai);
927 terms.insert(terms.begin()+ai, bt);
951 UnivariateTerm<Ring> a = terms[0];
955 terms.insert(terms.begin(), a);
959 if (terms[0].coef.isZero())
960 terms.erase(terms.begin());
964 UnivariateTerm<Ring> a;
985 for (
int i = 0; i < terms.size(); ++i) {
986 UnivariateTerm<Ring> t;
987 t.coef = -terms[i].coef;
988 t.exp = terms[i].exp;
989 res.terms.push_back(t);
1010 if (!terms.size()) {
return (*
this = -b); }
1011 if (!b.terms.size()) {
return *
this; }
1012 if (
isConstant()) {
return (*
this = -b + terms[0].coef); }
1013 if (b.isConstant()) {
return (*
this -= b.terms[0].coef); }
1014 if (name != b.name) {
1015 std::cout <<
"BPAS: error, trying to subtract between Ring[" << name <<
"] and Ring[" << b.name <<
"]." << std::endl;
1020 for (
int i = 0; i < b.terms.size(); ++i) {
1021 UnivariateTerm<Ring> t = b.terms[i];
1024 if (ai >= terms.size()) {
1029 int e1 = terms[ai].exp, e2 = t.exp;
1032 if (ai < terms.size())
1041 terms[ai].coef += t.coef;
1042 if (terms[ai].coef.isZero())
1043 terms.erase(terms.begin()+ai);
1047 terms.insert(terms.begin()+ai, t);
1071 UnivariateTerm<Ring> t = terms[0];
1075 terms.insert(terms.begin(), t);
1079 if (terms[0].coef.isZero())
1080 terms.erase(terms.begin());
1084 UnivariateTerm<Ring> t;
1103 int n = terms.size(), m = b.terms.size();
1111 for (
int i = 0; i < m; ++i) {
1112 UnivariateTerm<Ring> bt = b.terms[i];
1113 UnivariateTerm<Ring> t;
1114 t.coef = terms[0].coef * bt.coef;
1116 res.terms.push_back(t);
1122 if (b.degree() == 0) {
1123 UnivariateTerm<Ring> bt = b.terms[0];
1124 for (
int i = 0; i < n; ++i) {
1125 UnivariateTerm<Ring> t;
1126 t.coef = terms[i].coef * bt.coef;
1127 t.exp = terms[i].exp;
1128 res.terms.push_back(t);
1133 if (name != b.name) {
1134 std::cout <<
"BPAS: error, trying to multiply between Ring[" << name <<
"] and Ring[" << b.name <<
"]." << std::endl;
1140 for (
int i = 0; i < n; ++i)
1141 res.pomopo(terms[i], b);
1144 for (
int i = 0; i < m; ++i)
1145 res.pomopo(b.terms[i], *
this);
1149 int s = (m > n) ? m : n;
1152 f0.name = f1.name = name;
1153 for (
int i = 0; i < n; ++i) {
1154 if (terms[i].exp < s)
1155 f0.terms.push_back(terms[i]);
1157 UnivariateTerm<Ring> t (terms[i].coef, terms[i].exp-s);
1158 f1.terms.push_back(t);
1162 g0.name = g1.name = name;
1163 for (
int i = 0; i < m; ++i) {
1164 if (b.terms[i].exp < s)
1165 g0.terms.push_back(b.terms[i]);
1167 UnivariateTerm<Ring> t (b.terms[i].coef, b.terms[i].exp-s);
1168 g1.terms.push_back(t);
1172 t0.name = t1.name = name;
1173 n = f0.terms.size(), m = g0.terms.size();
1175 for (
int i = 0; i < n; ++i)
1176 res.pomopo(f0.terms[i], g0);
1179 for (
int i = 0; i < m; ++i)
1180 res.pomopo(g0.terms[i], f0);
1182 n = f1.terms.size(), m = g1.terms.size();
1184 for (
int i = 0; i < n; ++i)
1185 t0.pomopo(f1.terms[i], g1);
1188 for (
int i = 0; i < m; ++i)
1189 t0.pomopo(g1.terms[i], f1);
1192 n = f0.terms.size(), m = g0.terms.size();
1194 for (
int i = 0; i < n; ++i)
1195 t1.pomopo(f0.terms[i], g0);
1198 for (
int i = 0; i < m; ++i)
1199 t1.pomopo(g0.terms[i], f0);
1202 for (
int i = 0; i < t1.terms.size(); ++i)
1203 t1.terms[i].exp += s;
1205 for (
int i = 0; i < t0.terms.size(); ++i)
1206 t0.terms[i].exp += s;
1244 if (!c.isZero() && !c.isOne()) {
1245 for (
int i = 0; i < terms.size(); ++i)
1248 else if (c.isZero())
1255 if (e != 0 && e != 1) {
1256 for (
int i = 0; i < terms.size(); ++i)
1259 else if (e == 0) {
zero(); }
1290 std::cout <<
"BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1293 if (b.isConstant()) {
return (*
this /= b.terms[0].coef); }
1298 if (name != b.name) {
1299 std::cout <<
"BPAS: error, trying to exact divide between Ring[" << name <<
"] and Ring[" << b.name <<
"]." << std::endl;
1307 UnivariateTerm<Ring> bt = b.leadingTerm();
1309 if (db == 1 && bt.coef.
isOne()) {
1310 if (b.terms.size() > 1) {
1313 UnivariateTerm<Ring> t, at = leadingTerm();
1314 if (!terms[0].exp) {
1315 prev = t.coef = terms[0].coef / b.terms[0].coef;
1317 q.terms.push_back(t);
1320 else { prev.zero(); }
1321 for (
int i = 1; i < at.exp; ++i) {
1322 if (k < terms.size() && terms[k].exp == i) {
1327 t.coef = (e - prev) / b.terms[0].coef;
1328 if (!t.coef.isZero()) {
1330 q.terms.push_back(t);
1334 if (prev == at.coef)
1337 std::cout <<
"BPAS: error, not exact division in SparseUnivariatePolynomial<Ring>." << std::endl;
1342 if (!terms[0].exp) {
1343 std::cout <<
"BPAS: error, not exact division in SparseUnivariatePolynomial<Ring>." << std::endl;
1347 for (
int i = 0; i < terms.size(); ++i)
1355 UnivariateTerm<Ring> at = leadingTerm();
1356 UnivariateTerm<Ring> lc, nlc;
1357 lc.coef = at.coef / bt.coef;
1358 lc.exp = at.exp - bt.exp;
1359 nlc.coef = -lc.coef;
1362 q.terms.insert(q.terms.begin(), lc);
1365 std::cout <<
"BPAS: error, not exact division in SparseUnivariatePolynomial<Ring>." << std::endl;
1388 std::cout <<
"BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1391 else if (!e.isOne()) {
1393 while (i < terms.size()) {
1395 if (terms[i].coef.isZero())
1396 terms.erase(terms.begin()+i);
1405 std::cout <<
"BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1411 if (p.isConstant()) {
1413 return (q /= p.terms[0].coef);
1424 for (
int i = 0; i < terms.size(); ++i)
1425 terms[i].coef = -terms[i].coef;
1437 std::cout <<
"BPAS: error, dividend is zero from SparseUnivariatePolynomial<Ring>." << std::endl;
1440 else if (!b.leadingCoefficient().isOne()) {
1441 std::cout <<
"BPAS: error, leading coefficient is not one in monicDivide() from SparseUnivariatePolynomial<Ring>." << std::endl;
1445 if (b.isConstant()) {
1455 if (name != b.name) {
1456 std::cout <<
"BPAS: error, trying to monic divide between Ring[" << name <<
"] and Ring[" << b.name <<
"]." << std::endl;
1462 UnivariateTerm<Ring> bt = b.leadingTerm();
1463 while (
degree() >= b.degree()) {
1464 UnivariateTerm<Ring> at = leadingTerm();
1465 UnivariateTerm<Ring> nlc;
1466 nlc.coef = -at.coef;
1467 nlc.exp = at.exp - bt.exp;
1470 quo.terms.insert(quo.terms.begin(), at);
1484 std::cout <<
"*this " << *
this << std::endl;
1485 *rem = *
this; std::cout<<
"salam"<<std::endl;
1486 return rem->monicDivide(b);
1502 if (b.isZero() || db == 0) {
1503 std::cout <<
"BPAS: error, dividend is zero or constant from SparseUnivariatePolynomial<Ring>." << std::endl;
1512 if (name != b.name) {
1513 std::cout <<
"BPAS: error, trying to pseudo divide between Ring[" << name <<
"] and Ring[" << b.name <<
"]." << std::endl;
1525 Ring blc = b.leadingTerm().coef;
1530 UnivariateTerm<Ring> at = leadingTerm();
1531 UnivariateTerm<Ring> nlc;
1532 nlc.coef = -at.coef;
1533 nlc.exp = at.exp - db.get_si();
1537 pomopo(blc, nlc, b);
1539 quo.terms.insert(quo.terms.begin(), at);
1541 for (
int i = e; diff >= i; ++i)
1558 return rem->lazyPseudoDivide(b, c, d);
1604 if (k <= 0) {
return; }
1606 while (i < terms.size()) {
1607 if (terms[i].exp >= k) {
1608 for (
int j = 0; j < k; ++j)
1609 terms[i].coef *= Ring(terms[i].exp - j);
1614 terms.erase(terms.begin());
1651 int i = terms.size()-1;
1653 terms[i].coef /= (terms[i].exp + 1);
1677 int n = terms.size();
1678 if (n && terms[0].exp == 0 && terms[0].coef == Ring(0))
1689 int d = terms.size() - 1;
1690 if (d < 0) {
return Ring(); }
1691 int e = terms[d].exp - 1;
1692 Ring px = terms[d].coef;
1694 for (
int i = e; i > -1; --i) {
1696 if (i == terms[d].exp && d > -1) {
1697 px += terms[d].coef;
1709 template <
class LargerRing>
1710 inline LargerRing
evaluate(
const LargerRing& x)
const {
1712 int d = terms.size() - 1;
1713 if (d < 0) {
return LargerRing(); }
1714 int e = terms[d].exp - 1;
1715 LargerRing px = (LargerRing)terms[d].coef;
1718 for (
int i = e; i > -1; --i) {
1720 if (i == terms[d].exp && d > -1) {
1721 a = (LargerRing)terms[d].coef;
1732 int fullSize(chain[chain.size()-2].degree().get_ui()+2);
1736 if (chain.size() < fullSize) {
1737 chain.reserve(fullSize);
1738 for (
int i=chain.size()-2; i>0; --i) {
1739 if (chain[i].
degree() != chain[i-1].degree()+1) {
1740 delta = chain[i].degree().get_ui() - chain[i-1].degree().get_ui();
1743 for (
int j=0; j<delta-2; ++j)
1744 chain.insert(chain.begin()+i,
zero);
1747 for (
int j=0; j<delta-1; ++j)
1748 chain.insert(chain.begin()+i,
zero);
1752 if (chain[0].
degree() != 0) {
1753 for (
int j=0; j<chain[0].degree(); ++j)
1754 chain.insert(chain.begin(),
zero);
1767 if (name != q.name) {
1768 std::cout <<
"BPAS: error, trying to compute subresultant chains between Ring[" << name <<
"] and Ring[" << q.name <<
"]." << std::endl;
1772 if (
degree() == 0 || q.degree() == 0){
1773 std::cout <<
"BPAS: error, Input polynomials to subresultantChain must have positive degree." << std::endl;
1777 std::vector< SparseUnivariatePolynomial<Ring> > S;
1779 if (q.degree() >
degree()) {
1788 int k = (a.degree() - b.degree()).get_si();
1789 Ring s = b.leadingCoefficient() ^ k;
1793 b *= b.leadingCoefficient()^(k-1);
1802 S.insert(S.begin(), B);
1803 delta = A.degree() - B.degree();
1805 C = LazardSe(S[1], S[0], s);
1806 S.insert(S.begin(), C);
1809 if (B.degree() == 0)
1811 B = DucosSem(A, B, C, s);
1813 s = A.leadingCoefficient();
1816 if (S.at(0).degree() > 0) {
1817 S.insert(S.begin(), B);
1820 std::cerr <<
"filling chain..." << std::endl;
1835 for (
int i=s.size()-2; i>0; --i) {
1836 delta = s.at(i).degree() - s.at(i-1).degree();
1838 if (i == 1 && s.at(i-1).isZero())
1842 for (
int j=0; j<n; j++)
1843 s.insert(s.begin()+i-1,sup);
1931 if (
isZero()) {
return q; }
1932 if (q.isZero()) {
return *
this; }
1933 if (name != q.name) {
1934 std::cout <<
"BPAS: error, trying to compute GCD between Ring[" << name <<
"] and Ring[" << q.name <<
"]." << std::endl;
1939 if (a.degree() == 0 || b.degree() == 0) {
1962 std::vector< SparseUnivariatePolynomial<Ring> > R = a.subresultantChain(b);
1964 r.setCoefficient(0, ca.gcd(cb));
1970 for (
int i = 0; i < n; ++i) {
1972 cr = R[i].content();
1981 if (a.degree() <= b.degree()) { r *= a; }
1994 std::vector< SparseUnivariatePolynomial<Ring> > sf;
1995 int d = terms.size()-1;
1997 sf.push_back(*
this);
1998 else if (terms[d].exp == 1) {
2003 t = *
this / terms[d].coef;
2017 while (!z.isZero()) {
2031 for (
int i = 0; i < sf.size(); ++i) {
2032 e *= sf[i].leadingCoefficient();
2033 sf[i] /= sf[i].leadingCoefficient();
2038 sf.insert(sf.begin(), t);
2042 f.setRingElement(sf[0]);
2043 for (
int i = 1; i < sf.size(); ++i) {
2044 f.addFactor(sf[i], i);
2056 inline void print (std::ostream &out)
const {
2057 int n = terms.size();
2058 if (!n) { out <<
"0"; }
2059 for (
int i = 0; i < n; ++i) {
2060 if (this->terms[i].exp) {
2061 if (this->terms[i].coef.isNegativeOne())
2063 else if (i && this->terms[i].coef.isConstant() >= 0)
2065 if (!this->terms[i].coef.isConstant())
2066 out <<
"(" << this->terms[i].coef <<
")*";
2067 else if (!this->terms[i].coef.isOne() && !this->terms[i].coef.isNegativeOne())
2068 out << this->terms[i].coef <<
"*";
2070 if (this->terms[i].exp > 1)
2071 out <<
"^" << this->terms[i].exp;
2074 if (this->terms[i].coef.isConstant()) { out << this->terms[i].coef; }
2075 else { out <<
"(" << this->terms[i].coef <<
")"; }
2082 std::cerr <<
"BPAS ERROR: SMP<Ring>::convertToExpressionTree NOT YET IMPLEMENTED" << std::endl;
2088 int k = 0, n = terms.size(), d = 0;
2089 if (n) { d = terms[n-1].exp; }
2092 for (
int i = 0; i <= d; ++i) {
2094 if (!terms[k].coef.isConstant()) {
2098 else if (terms[k].exp == i) {
2104 if (!isDense) { res.
zero(); }
2110 int k = 0, n = terms.size(), d = 0;
2111 if (n) { d = terms[n-1].exp; }
2114 for (
int i = 0; i <= d; ++i) {
2116 if (!terms[k].coef.isConstant()) {
2120 else if (terms[k].exp == i) {
2126 if (!isDense) { res.
zero(); }
2143 rand_mpq_t(coefBound,1,randVal);
2144 mpq_class coef(randVal);
2146 P.setCoefficient(n, coef);
2147 int nTerms = ceil(sparsity*n);
2149 for(
int i = 0; i < nTerms; i++) {
2152 rand_mpq_t(coefBound,1,randVal);
2153 coef = mpq_class(randVal);
2154 P.setCoefficient(index, coef);
void negate()
Negate the polynomial.
Definition: upolynomial.h:1423
SparseUnivariatePolynomial< Ring > operator-() const
Overload operator -, negate.
Definition: upolynomial.h:982
A univariate polynomial over an arbitrary BPASRing represented sparsely.
Definition: BigPrimeField.hpp:21
SparseUnivariatePolynomial< Ring > operator>>(int k) const
Overload operator >> replace by dividing x^k, and return the quotient.
Definition: upolynomial.h:851
void differentiate(int k)
Compute k-th derivative.
Definition: upolynomial.h:1603
void zero()
Zero polynomial.
Definition: urpolynomial.h:315
bool operator==(const SparseUnivariatePolynomial< Ring > &b) const
Overload operator ==.
Definition: upolynomial.h:643
SparseUnivariatePolynomial< Ring > gcd(const SparseUnivariatePolynomial< Ring > &q) const
GCD(p, q)
Definition: upolynomial.h:1930
void setVariableName(const Symbol &x)
Set variable's name.
Definition: urpolynomial.h:242
LargerRing evaluate(const LargerRing &x) const
Evaluate f(x)
Definition: upolynomial.h:1710
void one()
Set polynomial to 1.
Definition: upolynomial.h:689
An arbitrary-precision complex rational number.
Definition: ComplexRationalNumber.hpp:23
SparseUnivariatePolynomial< Ring > monicDivide(const SparseUnivariatePolynomial< Ring > &b)
Monic division Assuming the leading coefficient of dividend is 1 Return quotient and itself becomes r...
Definition: upolynomial.h:1435
SparseUnivariatePolynomial< Ring > operator+(const SparseUnivariatePolynomial< Ring > &b) const
Overload operator +.
Definition: upolynomial.h:881
RationalNumber coefficient(int k) const
Get a coefficient of the polynomial.
Definition: urpolynomial.h:201
SparseUnivariatePolynomial< Ring > & operator>>=(int k)
Overload operator >>= replace by dividing x^k, and return the quotient.
Definition: upolynomial.h:863
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
bool isConstantTermZero() const
Is trailing coefficient zero.
Definition: upolynomial.h:1674
SparseUnivariatePolynomial< Ring > lazyPseudoDivide(const SparseUnivariatePolynomial< Ring > &b, Ring *c, Ring *d=NULL)
Lazy pseudo dividsion Return the quotient and itself becomes remainder e is the exact number of divis...
Definition: upolynomial.h:1498
Integer numberOfTerms() const
Get the number of terms.
Definition: upolynomial.h:482
SparseUnivariatePolynomial< Ring > & operator=(const SparseUnivariatePolynomial< Ring > &b)
Overload operator =.
Definition: upolynomial.h:604
SparseUnivariatePolynomial< Ring > operator^(long long int e) const
Overload operator ^ replace xor operation by exponentiation.
Definition: upolynomial.h:779
A univariate polynomial with Integer coefficients using a dense representation.
Definition: uzpolynomial.h:13
SparseUnivariatePolynomial< Ring > operator/(const SparseUnivariatePolynomial< Ring > &b) const
Overload operator / EdeDivision.
Definition: upolynomial.h:1277
Integer degree() const
Get degree of the polynomial.
Definition: urpolynomial.h:151
Symbol variable() const
Get variable's name.
Definition: uzpolynomial.h:195
Ring convertToConstant()
Convert to a constant.
Definition: upolynomial.h:737
void setCoefficient(int k, const mpz_class value)
Set a coefficient of the polynomial.
Definition: uzpolynomial.h:164
SparseUnivariatePolynomial< Ring > pseudoDivide(const SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem, Ring *d) const
Pseudo dividsion Return the quotient.
Definition: upolynomial.h:1589
bool operator!=(const SparseUnivariatePolynomial< Ring > &b) const
Overload operator !=.
Definition: upolynomial.h:634
void print(std::ostream &out) const
Overload stream operator <<.
Definition: upolynomial.h:2056
int isConstant() const
Is a constant.
Definition: upolynomial.h:726
A univariate polynomial with RationalNumber coefficients represented densely.
Definition: urpolynomial.h:15
SparseUnivariatePolynomial< Ring > & operator*=(const SparseUnivariatePolynomial< Ring > &b)
Overload operator *=.
Definition: upolynomial.h:1217
Integer coefficient(int k) const
Get a coefficient of the polynomial.
Definition: uzpolynomial.h:151
Ring evaluate(const Ring &x) const
Evaluate f(x)
Definition: upolynomial.h:1688
void negativeOne()
Set polynomial to -1.
Definition: upolynomial.h:713
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
SparseUnivariatePolynomial< Ring > & operator/=(const SparseUnivariatePolynomial< Ring > &b)
Overload operator /= ExactDivision.
Definition: upolynomial.h:1288
void zero()
Zero polynomial.
Definition: uzpolynomial.h:262
Ring coefficient(int k) const
Get a coefficient.
Definition: upolynomial.h:522
std::vector< SparseUnivariatePolynomial< Ring > > subresultantChain(const SparseUnivariatePolynomial< Ring > &q, int filled=0) const
Subresultant Chain Return the list of subresultants.
Definition: upolynomial.h:1766
void integrate()
Compute integral with constant of integration set to 0.
Definition: upolynomial.h:1650
Ring content() const override
Content of the polynomial.
Definition: upolynomial.h:752
Integer degree() const
Get the degree of the polynomial.
Definition: upolynomial.h:491
An arbitrary-precision Integer.
Definition: Integer.hpp:22
An abstract class defining the interface of a univariate polynomial over an arbitrary BPASRing...
Definition: polynomial.h:88
bool isOne() const
Is polynomial a constant 1.
Definition: upolynomial.h:678
SparseUnivariatePolynomial< Ring > & operator<<=(int k)
Overload operator <<= replace by muplitying x^k.
Definition: upolynomial.h:838
void zero()
Zero polynomial.
Definition: upolynomial.h:669
SparseUnivariatePolynomial< Ring > pseudoDivide(const SparseUnivariatePolynomial< Ring > &b, Ring *d=NULL)
Pseudo dividsion Return the quotient and itself becomes remainder.
Definition: upolynomial.h:1569
SparseUnivariatePolynomial< Ring > operator<<(int k) const
Overload operator << replace by muplitying x^k.
Definition: upolynomial.h:827
SparseUnivariatePolynomial< Ring > integral() const
Compute integral with constant of integration 0.
Definition: upolynomial.h:1663
void setCoefficient(int k, const RationalNumber &value)
Set a coefficient of the polynomial.
Definition: urpolynomial.h:213
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
An arbitrary-precision rational number.
Definition: RationalNumber.hpp:24
SparseUnivariatePolynomial< Ring > resultant(const SparseUnivariatePolynomial< Ring > &q)
Resultant.
Definition: upolynomial.h:1920
SparseUnivariatePolynomial< Ring > & operator+=(const SparseUnivariatePolynomial< Ring > &b)
Overload operator+=.
Definition: upolynomial.h:891
SparseUnivariatePolynomial< Ring > lazyPseudoDivide(const SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem, Ring *c, Ring *d) const
Lazy pseudo dividsion Return the quotient e is the exact number of division steps.
Definition: upolynomial.h:1556
Factors< SparseUnivariatePolynomial< Ring > > squareFree() const
Square free.
Definition: upolynomial.h:1993
void setCoefficient(int e, const Ring &c)
Set a coeffcient with its exponent.
Definition: upolynomial.h:539
void differentiate()
Convert current object to its derivative.
Definition: upolynomial.h:1622
bool isZero() const
Is zero polynomial.
Definition: upolynomial.h:660
SparseUnivariatePolynomial< Ring > derivative() const
Compute derivative.
Definition: upolynomial.h:1641
SparseUnivariatePolynomial< Ring > operator*(const SparseUnivariatePolynomial< Ring > &b) const
Multiply another polynomial.
Definition: upolynomial.h:1102
Symbol variable() const
Get variable's name.
Definition: urpolynomial.h:233
SparseUnivariatePolynomial< Ring > & operator-=(const SparseUnivariatePolynomial< Ring > &b)
Overload operator -=.
Definition: upolynomial.h:1009
SparseUnivariatePolynomial< Ring > monicDivide(const SparseUnivariatePolynomial< Ring > &b, SparseUnivariatePolynomial< Ring > *rem) const
Monic division Assuming the leading coefficient of dividend is 1 Return quotient. ...
Definition: upolynomial.h:1483
void setVariableName(const Symbol &c)
Set the variable name.
Definition: upolynomial.h:580
Ring leadingCoefficient() const
Get the leading coefficient.
Definition: upolynomial.h:502
SparseUnivariatePolynomial< Ring > & operator^=(long long int e)
Overload operator ^= replace xor operation by exponentiation.
Definition: upolynomial.h:816
bool isOne() const
Is a 1.
Definition: Integer.hpp:181
std::vector< SparseUnivariatePolynomial< Ring > > monomialBasisSubresultantChain(const SparseUnivariatePolynomial< Ring > &q)
monomialBasisSubResultantChain
Definition: upolynomial.h:1831
Symbol variable() const
Get the variable name.
Definition: upolynomial.h:571
Integer degree() const
Get degree of the polynomial.
Definition: uzpolynomial.h:104
SparseUnivariatePolynomial< Ring > derivative(int k) const
Return k-th derivative.
Definition: upolynomial.h:1631
void setVariableName(const Symbol &x)
Set variable's name.
Definition: uzpolynomial.h:203
bool isNegativeOne() const
Is polynomial a constant -1.
Definition: upolynomial.h:702