X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Fnormal.cpp;h=1808bcb90bc9722d5f78121b9c1f613896355e51;hp=67fbf93612beaa629ed2df6a987152e56a546374;hb=fa13c6831b809abdae9eb2c17b33d2eff8e4878c;hpb=73081e1cccfec32a9e9dab6a5e4b063b3fa0e7fb;ds=sidebyside diff --git a/ginac/normal.cpp b/ginac/normal.cpp index 67fbf936..1808bcb9 100644 --- a/ginac/normal.cpp +++ b/ginac/normal.cpp @@ -6,7 +6,7 @@ * 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 @@ -20,7 +20,7 @@ * * 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 @@ -84,7 +84,7 @@ static struct _stat_print { #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. * @@ -819,14 +819,14 @@ static bool divide_in_z(const ex &a, const ex &b, ex &q, sym_desc_vec::const_ite * 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(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)) @@ -841,15 +841,14 @@ ex ex::unit(const ex &x) const * 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(*this)) return info(info_flags::negative) ? -*this : *this; + ex e = expand(); if (e.is_zero()) return _ex0; @@ -858,15 +857,15 @@ ex ex::content(const ex &x) const // 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); @@ -874,28 +873,19 @@ ex ex::content(const ex &x) const } -/** 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(*this)) - return _ex1; - - ex c = content(x); - if (c.is_zero()) - return _ex0; - ex u = unit(x); - if (is_exactly_a(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; } @@ -903,18 +893,17 @@ ex ex::primpart(const ex &x) const * 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(*this)) return _ex1; + // Divide by unit and content to get primitive part ex u = unit(x); if (is_exactly_a(c)) return *this / (c * u); @@ -923,6 +912,61 @@ ex ex::primpart(const ex &x, const ex &c) const } +/** 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(*this)) { + if (info(info_flags::negative)) { + u = _ex_1; + c = abs(ex_to(*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(c)) + p = *this / (c * u); + else + p = quo(e, c * u, x, false); +} + + /* * GCD of multivariate polynomials */ @@ -1203,11 +1247,7 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const 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(lc) && ex_to(lc).is_negative()) - return -g; - else - return g; + return g; } } @@ -1219,7 +1259,8 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const /** 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 @@ -1303,10 +1344,12 @@ factored_b: // Input polynomials of the form poly^n are sometimes also trivial if (is_exactly_a(a)) { ex p = a.op(0); + const ex& exp_a = a.op(1); if (is_exactly_a(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; @@ -1320,7 +1363,32 @@ factored_b: *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 @@ -1329,8 +1397,24 @@ factored_b: 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(b) + } else if (is_exactly_a(b)) { ex p = b.op(0); if (p.is_equal(a)) { @@ -1341,6 +1425,23 @@ factored_b: *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 @@ -1396,16 +1497,18 @@ factored_b: // 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; } @@ -1472,7 +1575,7 @@ ex lcm(const ex &a, const ex &b, bool check_args) */ /** 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.