* computation, square-free factorization and rational function normalization. */
/*
- * GiNaC Copyright (C) 1999-2004 Johannes Gutenberg University Mainz, Germany
+ * GiNaC Copyright (C) 1999-2005 Johannes Gutenberg University Mainz, Germany
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
#include <algorithm>
#endif
-/** Return pointer to first symbol found in expression. Due to GiNaC´s
+/** Return pointer to first symbol found in expression. Due to GiNaC's
* internal ordering of terms, it may not be obvious which symbol this
* function returns for a given expression.
*
* polynomial in Q[x]. The product of unit part, content part, and primitive
* part is the polynomial itself.
*
- * @param x variable in which to compute the unit part
+ * @param x main variable
* @return unit part
- * @see ex::content, ex::primpart */
+ * @see ex::content, ex::primpart, ex::unitcontprim */
ex ex::unit(const ex &x) const
{
ex c = expand().lcoeff(x);
if (is_exactly_a<numeric>(c))
- return c < _ex0 ? _ex_1 : _ex1;
+ return c.info(info_flags::negative) ?_ex_1 : _ex1;
else {
ex y;
if (get_first_symbol(c, y))
* multivariate polynomial in Q[x]. The product of unit part, content part,
* and primitive part is the polynomial itself.
*
- * @param x variable in which to compute the content part
+ * @param x main variable
* @return content part
- * @see ex::unit, ex::primpart */
+ * @see ex::unit, ex::primpart, ex::unitcontprim */
ex ex::content(const ex &x) const
{
- if (is_zero())
- return _ex0;
if (is_exactly_a<numeric>(*this))
return info(info_flags::negative) ? -*this : *this;
+
ex e = expand();
if (e.is_zero())
return _ex0;
// If the leading coefficient of the quotient is an integer, we are done.
ex c = e.integer_content();
ex r = e / c;
- ex lcoeff = r.lcoeff(x);
+ int deg = r.degree(x);
+ ex lcoeff = r.coeff(x, deg);
if (lcoeff.info(info_flags::integer))
return c;
// GCD of all coefficients
- int deg = r.degree(x);
int ldeg = r.ldegree(x);
if (deg == ldeg)
- return lcoeff * c;
+ return lcoeff * c / lcoeff.unit(x);
ex cont = _ex0;
for (int i=ldeg; i<=deg; i++)
cont = gcd(r.coeff(x, i), cont, NULL, NULL, false);
}
-/** Compute primitive part of a multivariate polynomial in Q[x].
- * The product of unit part, content part, and primitive part is the
- * polynomial itself.
+/** Compute primitive part of a multivariate polynomial in Q[x]. The result
+ * will be a unit-normal polynomial with a content part of 1. The product
+ * of unit part, content part, and primitive part is the polynomial itself.
*
- * @param x variable in which to compute the primitive part
+ * @param x main variable
* @return primitive part
- * @see ex::unit, ex::content */
+ * @see ex::unit, ex::content, ex::unitcontprim */
ex ex::primpart(const ex &x) const
{
- if (is_zero())
- return _ex0;
- if (is_exactly_a<numeric>(*this))
- return _ex1;
-
- ex c = content(x);
- if (c.is_zero())
- return _ex0;
- ex u = unit(x);
- if (is_exactly_a<numeric>(c))
- return *this / (c * u);
- else
- return quo(*this, c * u, x, false);
+ // We need to compute the unit and content anyway, so call unitcontprim()
+ ex u, c, p;
+ unitcontprim(x, u, c, p);
+ return p;
}
* content part is already known. This function is faster in computing the
* primitive part than the previous function.
*
- * @param x variable in which to compute the primitive part
+ * @param x main variable
* @param c previously computed content part
* @return primitive part */
ex ex::primpart(const ex &x, const ex &c) const
{
- if (is_zero())
- return _ex0;
- if (c.is_zero())
+ if (is_zero() || c.is_zero())
return _ex0;
if (is_exactly_a<numeric>(*this))
return _ex1;
+ // Divide by unit and content to get primitive part
ex u = unit(x);
if (is_exactly_a<numeric>(c))
return *this / (c * u);
}
+/** Compute unit part, content part, and primitive part of a multivariate
+ * polynomial in Q[x]. The product of the three parts is the polynomial
+ * itself.
+ *
+ * @param x main variable
+ * @param u unit part (returned)
+ * @param c content part (returned)
+ * @param p primitive part (returned)
+ * @see ex::unit, ex::content, ex::primpart */
+void ex::unitcontprim(const ex &x, ex &u, ex &c, ex &p) const
+{
+ // Quick check for zero (avoid expanding)
+ if (is_zero()) {
+ u = _ex1;
+ c = p = _ex0;
+ return;
+ }
+
+ // Special case: input is a number
+ if (is_exactly_a<numeric>(*this)) {
+ if (info(info_flags::negative)) {
+ u = _ex_1;
+ c = abs(ex_to<numeric>(*this));
+ } else {
+ u = _ex1;
+ c = *this;
+ }
+ p = _ex1;
+ return;
+ }
+
+ // Expand input polynomial
+ ex e = expand();
+ if (e.is_zero()) {
+ u = _ex1;
+ c = p = _ex0;
+ return;
+ }
+
+ // Compute unit and content
+ u = unit(x);
+ c = content(x);
+
+ // Divide by unit and content to get primitive part
+ if (c.is_zero()) {
+ p = _ex0;
+ return;
+ }
+ if (is_exactly_a<numeric>(c))
+ p = *this / (c * u);
+ else
+ p = quo(e, c * u, x, false);
+}
+
+
/*
* GCD of multivariate polynomials
*/
ex dummy;
if (divide_in_z(p, g, ca ? *ca : dummy, var) && divide_in_z(q, g, cb ? *cb : dummy, var)) {
g *= gc;
- ex lc = g.lcoeff(x);
- if (is_exactly_a<numeric>(lc) && ex_to<numeric>(lc).is_negative())
- return -g;
- else
- return g;
+ return g;
}
}
/** Compute GCD (Greatest Common Divisor) of multivariate polynomials a(X)
- * and b(X) in Z[X].
+ * and b(X) in Z[X]. Optionally also compute the cofactors of a and b,
+ * defined by a = ca * gcd(a, b) and b = cb * gcd(a, b).
*
* @param a first multivariate polynomial
* @param b second multivariate polynomial
// Input polynomials of the form poly^n are sometimes also trivial
if (is_exactly_a<power>(a)) {
ex p = a.op(0);
+ const ex& exp_a = a.op(1);
if (is_exactly_a<power>(b)) {
- if (p.is_equal(b.op(0))) {
+ ex pb = b.op(0);
+ const ex& exp_b = b.op(1);
+ if (p.is_equal(pb)) {
// a = p^n, b = p^m, gcd = p^min(n, m)
- ex exp_a = a.op(1), exp_b = b.op(1);
if (exp_a < exp_b) {
if (ca)
*ca = _ex1;
*cb = _ex1;
return power(p, exp_b);
}
- }
+ } else {
+ ex p_co, pb_co;
+ ex p_gcd = gcd(p, pb, &p_co, &pb_co, check_args);
+ if (p_gcd.is_equal(_ex1)) {
+ // a(x) = p(x)^n, b(x) = p_b(x)^m, gcd (p, p_b) = 1 ==>
+ // gcd(a,b) = 1
+ if (ca)
+ *ca = a;
+ if (cb)
+ *cb = b;
+ return _ex1;
+ // XXX: do I need to check for p_gcd = -1?
+ } else {
+ // there are common factors:
+ // a(x) = g(x)^n A(x)^n, b(x) = g(x)^m B(x)^m ==>
+ // gcd(a, b) = g(x)^n gcd(A(x)^n, g(x)^(n-m) B(x)^m
+ if (exp_a < exp_b) {
+ return power(p_gcd, exp_a)*
+ gcd(power(p_co, exp_a), power(p_gcd, exp_b-exp_a)*power(pb_co, exp_b), ca, cb, false);
+ } else {
+ return power(p_gcd, exp_b)*
+ gcd(power(p_gcd, exp_a - exp_b)*power(p_co, exp_a), power(pb_co, exp_b), ca, cb, false);
+ }
+ } // p_gcd.is_equal(_ex1)
+ } // p.is_equal(pb)
+
} else {
if (p.is_equal(b)) {
// a = p^n, b = p, gcd = p
if (cb)
*cb = _ex1;
return p;
+ }
+
+ ex p_co, bpart_co;
+ ex p_gcd = gcd(p, b, &p_co, &bpart_co, false);
+
+ if (p_gcd.is_equal(_ex1)) {
+ // a(x) = p(x)^n, gcd(p, b) = 1 ==> gcd(a, b) = 1
+ if (ca)
+ *ca = a;
+ if (cb)
+ *cb = b;
+ return _ex1;
+ } else {
+ // a(x) = g(x)^n A(x)^n, b(x) = g(x) B(x) ==> gcd(a, b) = g(x) gcd(g(x)^(n-1) A(x)^n, B(x))
+ return p_gcd*gcd(power(p_gcd, exp_a-1)*power(p_co, exp_a), bpart_co, ca, cb, false);
}
- }
+ } // is_exactly_a<power>(b)
+
} else if (is_exactly_a<power>(b)) {
ex p = b.op(0);
if (p.is_equal(a)) {
*cb = power(p, b.op(1) - 1);
return p;
}
+
+ ex p_co, apart_co;
+ const ex& exp_b(b.op(1));
+ ex p_gcd = gcd(a, p, &apart_co, &p_co, false);
+ if (p_gcd.is_equal(_ex1)) {
+ // b=p(x)^n, gcd(a, p) = 1 ==> gcd(a, b) == 1
+ if (ca)
+ *ca = a;
+ if (cb)
+ *cb = b;
+ return _ex1;
+ } else {
+ // there are common factors:
+ // a(x) = g(x) A(x), b(x) = g(x)^n B(x)^n ==> gcd = g(x) gcd(g(x)^(n-1) A(x)^n, B(x))
+
+ return p_gcd*gcd(apart_co, power(p_gcd, exp_b-1)*power(p_co, exp_b), ca, cb, false);
+ } // p_gcd.is_equal(_ex1)
}
#endif
// Try to eliminate variables
if (var->deg_a == 0) {
- ex c = bex.content(x);
- ex g = gcd(aex, c, ca, cb, false);
+ ex bex_u, bex_c, bex_p;
+ bex.unitcontprim(x, bex_u, bex_c, bex_p);
+ ex g = gcd(aex, bex_c, ca, cb, false);
if (cb)
- *cb *= bex.unit(x) * bex.primpart(x, c);
+ *cb *= bex_u * bex_p;
return g;
} else if (var->deg_b == 0) {
- ex c = aex.content(x);
- ex g = gcd(c, bex, ca, cb, false);
+ ex aex_u, aex_c, aex_p;
+ aex.unitcontprim(x, aex_u, aex_c, aex_p);
+ ex g = gcd(aex_c, bex, ca, cb, false);
if (ca)
- *ca *= aex.unit(x) * aex.primpart(x, c);
+ *ca *= aex_u * aex_p;
return g;
}
*/
/** Compute square-free factorization of multivariate polynomial a(x) using
- * Yun´s algorithm. Used internally by sqrfree().
+ * Yun's algorithm. Used internally by sqrfree().
*
* @param a multivariate polynomial over Z[X], treated here as univariate
* polynomial in x.