+ex basic::to_polynomial(exmap & repl) const
+{
+ return replace_with_symbol(*this, repl);
+}
+
+
+/** Implementation of ex::to_rational() for symbols. This returns the
+ * unmodified symbol. */
+ex symbol::to_rational(exmap & repl) const
+{
+ return *this;
+}
+
+/** Implementation of ex::to_polynomial() for symbols. This returns the
+ * unmodified symbol. */
+ex symbol::to_polynomial(exmap & repl) const
+{
+ return *this;
+}
+
+
+/** Implementation of ex::to_rational() for a numeric. It splits complex
+ * numbers into re+I*im and replaces I and non-rational real numbers with a
+ * temporary symbol. */
+ex numeric::to_rational(exmap & repl) const
+{
+ if (is_real()) {
+ if (!is_rational())
+ return replace_with_symbol(*this, repl);
+ } else { // complex
+ numeric re = real();
+ numeric im = imag();
+ ex re_ex = re.is_rational() ? re : replace_with_symbol(re, repl);
+ ex im_ex = im.is_rational() ? im : replace_with_symbol(im, repl);
+ return re_ex + im_ex * replace_with_symbol(I, repl);
+ }
+ return *this;
+}
+
+/** Implementation of ex::to_polynomial() for a numeric. It splits complex
+ * numbers into re+I*im and replaces I and non-integer real numbers with a
+ * temporary symbol. */
+ex numeric::to_polynomial(exmap & repl) const
+{
+ if (is_real()) {
+ if (!is_integer())
+ return replace_with_symbol(*this, repl);
+ } else { // complex
+ numeric re = real();
+ numeric im = imag();
+ ex re_ex = re.is_integer() ? re : replace_with_symbol(re, repl);
+ ex im_ex = im.is_integer() ? im : replace_with_symbol(im, repl);
+ return re_ex + im_ex * replace_with_symbol(I, repl);
+ }
+ return *this;
+}
+
+
+/** Implementation of ex::to_rational() for powers. It replaces non-integer
+ * powers by temporary symbols. */
+ex power::to_rational(exmap & repl) const
+{
+ if (exponent.info(info_flags::integer))
+ return power(basis.to_rational(repl), exponent);
+ else
+ return replace_with_symbol(*this, repl);
+}
+
+/** Implementation of ex::to_polynomial() for powers. It replaces non-posint
+ * powers by temporary symbols. */
+ex power::to_polynomial(exmap & repl) const
+{
+ if (exponent.info(info_flags::posint))
+ return power(basis.to_rational(repl), exponent);
+ else if (exponent.info(info_flags::negint))
+ {
+ ex basis_pref = collect_common_factors(basis);
+ if (is_exactly_a<mul>(basis_pref) || is_exactly_a<power>(basis_pref)) {
+ // (A*B)^n will be automagically transformed to A^n*B^n
+ ex t = power(basis_pref, exponent);
+ return t.to_polynomial(repl);
+ }
+ else
+ return power(replace_with_symbol(power(basis, _ex_1), repl), -exponent);
+ }
+ else
+ return replace_with_symbol(*this, repl);
+}
+
+
+/** Implementation of ex::to_rational() for expairseqs. */
+ex expairseq::to_rational(exmap & repl) const
+{
+ epvector s;
+ s.reserve(seq.size());
+ epvector::const_iterator i = seq.begin(), end = seq.end();
+ while (i != end) {
+ s.push_back(split_ex_to_pair(recombine_pair_to_ex(*i).to_rational(repl)));
+ ++i;
+ }
+ ex oc = overall_coeff.to_rational(repl);
+ if (oc.info(info_flags::numeric))
+ return thisexpairseq(s, overall_coeff);
+ else
+ s.push_back(combine_ex_with_coeff_to_pair(oc, _ex1));
+ return thisexpairseq(s, default_overall_coeff());
+}
+
+/** Implementation of ex::to_polynomial() for expairseqs. */
+ex expairseq::to_polynomial(exmap & repl) const
+{
+ epvector s;
+ s.reserve(seq.size());
+ epvector::const_iterator i = seq.begin(), end = seq.end();
+ while (i != end) {
+ s.push_back(split_ex_to_pair(recombine_pair_to_ex(*i).to_polynomial(repl)));
+ ++i;
+ }
+ ex oc = overall_coeff.to_polynomial(repl);
+ if (oc.info(info_flags::numeric))
+ return thisexpairseq(s, overall_coeff);
+ else
+ s.push_back(combine_ex_with_coeff_to_pair(oc, _ex1));
+ return thisexpairseq(s, default_overall_coeff());
+}
+
+
+/** Remove the common factor in the terms of a sum 'e' by calculating the GCD,
+ * and multiply it into the expression 'factor' (which needs to be initialized
+ * to 1, unless you're accumulating factors). */
+static ex find_common_factor(const ex & e, ex & factor, exmap & repl)
+{
+ if (is_exactly_a<add>(e)) {
+
+ size_t num = e.nops();
+ exvector terms; terms.reserve(num);
+ ex gc;
+
+ // Find the common GCD
+ for (size_t i=0; i<num; i++) {
+ ex x = e.op(i).to_polynomial(repl);
+
+ if (is_exactly_a<add>(x) || is_exactly_a<mul>(x) || is_a<power>(x)) {
+ ex f = 1;
+ x = find_common_factor(x, f, repl);
+ x *= f;
+ }
+
+ if (i == 0)
+ gc = x;
+ else
+ gc = gcd(gc, x);
+
+ terms.push_back(x);
+ }
+
+ if (gc.is_equal(_ex1))
+ return e;
+
+ // The GCD is the factor we pull out
+ factor *= gc;
+
+ // Now divide all terms by the GCD
+ for (size_t i=0; i<num; i++) {
+ ex x;
+
+ // Try to avoid divide() because it expands the polynomial
+ ex &t = terms[i];
+ if (is_exactly_a<mul>(t)) {
+ for (size_t j=0; j<t.nops(); j++) {
+ if (t.op(j).is_equal(gc)) {
+ exvector v; v.reserve(t.nops());
+ for (size_t k=0; k<t.nops(); k++) {
+ if (k == j)
+ v.push_back(_ex1);
+ else
+ v.push_back(t.op(k));
+ }
+ t = (new mul(v))->setflag(status_flags::dynallocated);
+ goto term_done;
+ }
+ }
+ }
+
+ divide(t, gc, x);
+ t = x;
+term_done: ;
+ }
+ return (new add(terms))->setflag(status_flags::dynallocated);
+
+ } else if (is_exactly_a<mul>(e)) {
+
+ size_t num = e.nops();
+ exvector v; v.reserve(num);
+
+ for (size_t i=0; i<num; i++)
+ v.push_back(find_common_factor(e.op(i), factor, repl));
+
+ return (new mul(v))->setflag(status_flags::dynallocated);
+
+ } else if (is_exactly_a<power>(e)) {
+ const ex e_exp(e.op(1));
+ if (e_exp.info(info_flags::integer)) {
+ ex eb = e.op(0).to_polynomial(repl);
+ ex factor_local(_ex1);
+ ex pre_res = find_common_factor(eb, factor_local, repl);
+ factor *= power(factor_local, e_exp);
+ return power(pre_res, e_exp);
+
+ } else
+ return e.to_polynomial(repl);
+
+ } else
+ return e;
+}
+
+
+/** Collect common factors in sums. This converts expressions like
+ * 'a*(b*x+b*y)' to 'a*b*(x+y)'. */
+ex collect_common_factors(const ex & e)
+{
+ if (is_exactly_a<add>(e) || is_exactly_a<mul>(e) || is_exactly_a<power>(e)) {
+
+ exmap repl;
+ ex factor = 1;
+ ex r = find_common_factor(e, factor, repl);
+ return factor.subs(repl, subs_options::no_pattern) * r.subs(repl, subs_options::no_pattern);
+
+ } else
+ return e;
+}
+
+
+/** Resultant of two expressions e1,e2 with respect to symbol s.
+ * Method: Compute determinant of Sylvester matrix of e1,e2,s. */
+ex resultant(const ex & e1, const ex & e2, const ex & s)
+{
+ const ex ee1 = e1.expand();
+ const ex ee2 = e2.expand();
+ if (!ee1.info(info_flags::polynomial) ||
+ !ee2.info(info_flags::polynomial))
+ throw(std::runtime_error("resultant(): arguments must be polynomials"));
+
+ const int h1 = ee1.degree(s);
+ const int l1 = ee1.ldegree(s);
+ const int h2 = ee2.degree(s);
+ const int l2 = ee2.ldegree(s);
+
+ const int msize = h1 + h2;
+ matrix m(msize, msize);
+
+ for (int l = h1; l >= l1; --l) {
+ const ex e = ee1.coeff(s, l);
+ for (int k = 0; k < h2; ++k)
+ m(k, k+h1-l) = e;
+ }
+ for (int l = h2; l >= l2; --l) {
+ const ex e = ee2.coeff(s, l);
+ for (int k = 0; k < h1; ++k)
+ m(k+h2, k+h2-l) = e;
+ }
+
+ return m.determinant();
+}
+
+