+/** Get numerator and denominator of an expression. If the expresison is not
+ * of the normal form "numerator/denominator", it is first converted to this
+ * form and then a list [numerator, denominator] is returned.
+ *
+ * @see ex::normal
+ * @return a list [numerator, denominator] */
+ex ex::numer_denom() const
+{
+ exmap repl, rev_lookup;
+
+ ex e = bp->normal(repl, rev_lookup, 0);
+ GINAC_ASSERT(is_a<lst>(e));
+
+ // Re-insert replaced symbols
+ if (repl.empty())
+ return e;
+ else
+ return e.subs(repl, subs_options::no_pattern);
+}
+
+
+/** Rationalization of non-rational functions.
+ * This function converts a general expression to a rational function
+ * by replacing all non-rational subexpressions (like non-rational numbers,
+ * non-integer powers or functions like sin(), cos() etc.) to temporary
+ * symbols. This makes it possible to use functions like gcd() and divide()
+ * on non-rational functions by applying to_rational() on the arguments,
+ * calling the desired function and re-substituting the temporary symbols
+ * in the result. To make the last step possible, all temporary symbols and
+ * their associated expressions are collected in the map specified by the
+ * repl parameter, ready to be passed as an argument to ex::subs().
+ *
+ * @param repl collects all temporary symbols and their replacements
+ * @return rationalized expression */
+ex ex::to_rational(exmap & repl) const
+{
+ return bp->to_rational(repl);
+}
+
+// GiNaC 1.1 compatibility function
+ex ex::to_rational(lst & repl_lst) const
+{
+ // Convert lst to exmap
+ exmap m;
+ for (lst::const_iterator it = repl_lst.begin(); it != repl_lst.end(); ++it)
+ m.insert(std::make_pair(it->op(0), it->op(1)));
+
+ ex ret = bp->to_rational(m);
+
+ // Convert exmap back to lst
+ repl_lst.remove_all();
+ for (exmap::const_iterator it = m.begin(); it != m.end(); ++it)
+ repl_lst.append(it->first == it->second);
+
+ return ret;
+}
+
+ex ex::to_polynomial(exmap & repl) const
+{
+ return bp->to_polynomial(repl);
+}
+
+// GiNaC 1.1 compatibility function
+ex ex::to_polynomial(lst & repl_lst) const
+{
+ // Convert lst to exmap
+ exmap m;
+ for (lst::const_iterator it = repl_lst.begin(); it != repl_lst.end(); ++it)
+ m.insert(std::make_pair(it->op(0), it->op(1)));
+
+ ex ret = bp->to_polynomial(m);
+
+ // Convert exmap back to lst
+ repl_lst.remove_all();
+ for (exmap::const_iterator it = m.begin(); it != m.end(); ++it)
+ repl_lst.append(it->first == it->second);
+
+ return ret;
+}
+
+/** Default implementation of ex::to_rational(). This replaces the object with
+ * a temporary symbol. */
+ex basic::to_rational(exmap & repl) const
+{
+ return replace_with_symbol(*this, repl);
+}
+
+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
+ 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)) {
+ 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)) {
+
+ 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)) {
+
+ 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();
+}
+
+