X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?a=blobdiff_plain;f=ginac%2Fnormal.cpp;h=66e682c9a7da88f244a8e6cb0592db81682b2829;hb=eed9352ec69b68db0c5095376746ccf139c5d03a;hp=1e7ed3a290af6aa0395995527658f2096fe1439d;hpb=e5e2ac399c225a8c7248e1879e192eba00067538;p=ginac.git diff --git a/ginac/normal.cpp b/ginac/normal.cpp index 1e7ed3a2..66e682c9 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-2007 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. * @@ -233,14 +233,14 @@ static numeric lcmcoeff(const ex &e, const numeric &l) if (e.info(info_flags::rational)) return lcm(ex_to(e).denom(), l); else if (is_exactly_a(e)) { - numeric c = _num1; + numeric c = *_num1_p; for (size_t i=0; i(e)) { - numeric c = _num1; + numeric c = *_num1_p; for (size_t i=0; i(e)) { if (is_a(e.op(0))) @@ -260,7 +260,7 @@ static numeric lcmcoeff(const ex &e, const numeric &l) * @return LCM of denominators of coefficients */ static numeric lcm_of_coefficients_denominators(const ex &e) { - return lcmcoeff(e, _num1); + return lcmcoeff(e, *_num1_p); } /** Bring polynomial from Q[X] to Z[X] by multiplying in the previously @@ -273,9 +273,9 @@ static ex multiply_lcm(const ex &e, const numeric &lcm) if (is_exactly_a(e)) { size_t num = e.nops(); exvector v; v.reserve(num + 1); - numeric lcm_accum = _num1; + numeric lcm_accum = *_num1_p; for (size_t i=0; i(it->rest)); GINAC_ASSERT(is_exactly_a(it->coeff)); - c = gcd(ex_to(it->coeff), c); + c = gcd(ex_to(it->coeff).numer(), c); + l = lcm(ex_to(it->coeff).denom(), l); it++; } GINAC_ASSERT(is_exactly_a(overall_coeff)); - c = gcd(ex_to(overall_coeff),c); - return c; + c = gcd(ex_to(overall_coeff).numer(), c); + l = lcm(ex_to(overall_coeff).denom(), l); + return c/l; } numeric mul::integer_content() const @@ -610,6 +614,72 @@ bool divide(const ex &a, const ex &b, ex &q, bool check_args) if (!get_first_symbol(a, x) && !get_first_symbol(b, x)) throw(std::invalid_argument("invalid expression in divide()")); + // Try to avoid expanding partially factored expressions. + if (is_exactly_a(b)) { + // Divide sequentially by each term + ex rem_new, rem_old = a; + for (size_t i=0; i < b.nops(); i++) { + if (! divide(rem_old, b.op(i), rem_new, false)) + return false; + rem_old = rem_new; + } + q = rem_new; + return true; + } else if (is_exactly_a(b)) { + const ex& bb(b.op(0)); + int exp_b = ex_to(b.op(1)).to_int(); + ex rem_new, rem_old = a; + for (int i=exp_b; i>0; i--) { + if (! divide(rem_old, bb, rem_new, false)) + return false; + rem_old = rem_new; + } + q = rem_new; + return true; + } + + if (is_exactly_a(a)) { + // Divide sequentially each term. If some term in a is divisible + // by b we are done... and if not, we can't really say anything. + size_t i; + ex rem_i; + bool divisible_p = false; + for (i=0; i < a.nops(); ++i) { + if (divide(a.op(i), b, rem_i, false)) { + divisible_p = true; + break; + } + } + if (divisible_p) { + exvector resv; + resv.reserve(a.nops()); + for (size_t j=0; j < a.nops(); j++) { + if (j==i) + resv.push_back(rem_i); + else + resv.push_back(a.op(j)); + } + q = (new mul(resv))->setflag(status_flags::dynallocated); + return true; + } + } else if (is_exactly_a(a)) { + // The base itself might be divisible by b, in that case we don't + // need to expand a + const ex& ab(a.op(0)); + int a_exp = ex_to(a.op(1)).to_int(); + ex rem_i; + if (divide(ab, b, rem_i, false)) { + q = rem_i*power(ab, a_exp - 1); + return true; + } + for (int i=2; i < a_exp; i++) { + if (divide(power(ab, i), b, rem_i, false)) { + q = rem_i*power(ab, a_exp - i); + return true; + } + } // ... so we *really* need to expand expression. + } + // Polynomial long division (recursive) ex r = a.expand(); if (r.is_zero()) { @@ -710,6 +780,31 @@ static bool divide_in_z(const ex &a, const ex &b, ex &q, sym_desc_vec::const_ite } #endif + if (is_exactly_a(b)) { + const ex& bb(b.op(0)); + ex qbar = a; + int exp_b = ex_to(b.op(1)).to_int(); + for (int i=exp_b; i>0; i--) { + if (!divide_in_z(qbar, bb, q, var)) + return false; + qbar = q; + } + return true; + } + + if (is_exactly_a(b)) { + ex qbar = a; + for (const_iterator itrb = b.begin(); itrb != b.end(); ++itrb) { + sym_desc_vec sym_stats; + get_symbol_stats(a, *itrb, sym_stats); + if (!divide_in_z(qbar, *itrb, q, sym_stats.begin())) + return false; + + qbar = q; + } + return true; + } + // Main symbol const ex &x = var->sym; @@ -726,24 +821,24 @@ static bool divide_in_z(const ex &a, const ex &b, ex &q, sym_desc_vec::const_ite // Compute values at evaluation points 0..adeg vector alpha; alpha.reserve(adeg + 1); exvector u; u.reserve(adeg + 1); - numeric point = _num0; + numeric point = *_num0_p; ex c; for (i=0; i<=adeg; i++) { ex bs = b.subs(x == point, subs_options::no_pattern); while (bs.is_zero()) { - point += _num1; + point += *_num1_p; bs = b.subs(x == point, subs_options::no_pattern); } if (!divide_in_z(a.subs(x == point, subs_options::no_pattern), bs, c, var+1)) return false; alpha.push_back(point); u.push_back(c); - point += _num1; + point += *_num1_p; } // Compute inverses vector rcp; rcp.reserve(adeg + 1); - rcp.push_back(_num0); + rcp.push_back(*_num0_p); for (k=1; k<=adeg; k++) { numeric product = alpha[k] - alpha[0]; for (i=1; i(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)) @@ -834,82 +929,72 @@ ex ex::unit(const ex &x) const /** Compute content part (= unit normal GCD of all coefficients) of a - * multivariate polynomial in Z[x]. The product of unit part, content part, + * 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; - // First, try the integer content + // First, divide out the integer content (which we can calculate very efficiently). + // 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 = e.degree(x); - int ldeg = e.ldegree(x); + int ldeg = r.ldegree(x); if (deg == ldeg) - return e.lcoeff(x) / e.unit(x); - c = _ex0; + return lcoeff * c / lcoeff.unit(x); + ex cont = _ex0; for (int i=ldeg; i<=deg; i++) - c = gcd(e.coeff(x, i), c, NULL, NULL, false); - return c; + cont = gcd(r.coeff(x, i), cont, NULL, NULL, false); + return cont * c; } -/** Compute primitive part of a multivariate polynomial in Z[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; } -/** Compute primitive part of a multivariate polynomial in Z[x] when the +/** Compute primitive part of a multivariate polynomial in Q[x] when the * 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); @@ -918,6 +1003,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 */ @@ -1013,7 +1153,7 @@ numeric ex::max_coefficient() const * @see heur_gcd */ numeric basic::max_coefficient() const { - return _num1; + return *_num1_p; } numeric numeric::max_coefficient() const @@ -1173,9 +1313,9 @@ static ex heur_gcd(const ex &a, const ex &b, ex *ca, ex *cb, sym_desc_vec::const numeric mq = q.max_coefficient(); numeric xi; if (mp > mq) - xi = mq * _num2 + _num2; + xi = mq * (*_num2_p) + (*_num2_p); else - xi = mp * _num2 + _num2; + xi = mp * (*_num2_p) + (*_num2_p); // 6 tries maximum for (int t=0; t<6; t++) { @@ -1198,11 +1338,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; } } @@ -1214,7 +1350,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 @@ -1298,10 +1435,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; @@ -1315,7 +1454,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 @@ -1324,8 +1488,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)) { @@ -1336,6 +1516,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 @@ -1372,11 +1569,71 @@ factored_b: } #endif + if (is_a(aex)) { + if (! bex.subs(aex==_ex0, subs_options::no_pattern).is_zero()) { + if (ca) + *ca = a; + if (cb) + *cb = b; + return _ex1; + } + } + + if (is_a(bex)) { + if (! aex.subs(bex==_ex0, subs_options::no_pattern).is_zero()) { + if (ca) + *ca = a; + if (cb) + *cb = b; + return _ex1; + } + } + + if (is_exactly_a(aex)) { + numeric bcont = bex.integer_content(); + numeric g = gcd(ex_to(aex), bcont); + if (ca) + *ca = ex_to(aex)/g; + if (cb) + *cb = bex/g; + return g; + } + + if (is_exactly_a(bex)) { + numeric acont = aex.integer_content(); + numeric g = gcd(ex_to(bex), acont); + if (ca) + *ca = aex/g; + if (cb) + *cb = ex_to(bex)/g; + return g; + } + // Gather symbol statistics sym_desc_vec sym_stats; get_symbol_stats(a, b, sym_stats); - // The symbol with least degree is our main variable + // The symbol with least degree which is contained in both polynomials + // is our main variable + sym_desc_vec::iterator vari = sym_stats.begin(); + while ((vari != sym_stats.end()) && + (((vari->ldeg_b == 0) && (vari->deg_b == 0)) || + ((vari->ldeg_a == 0) && (vari->deg_a == 0)))) + vari++; + + // No common symbols at all, just return 1: + if (vari == sym_stats.end()) { + // N.B: keep cofactors factored + if (ca) + *ca = a; + if (cb) + *cb = b; + return _ex1; + } + // move symbols which contained only in one of the polynomials + // to the end: + rotate(sym_stats.begin(), vari, sym_stats.end()); + sym_desc_vec::const_iterator var = sym_stats.begin(); const ex &x = var->sym; @@ -1390,17 +1647,19 @@ factored_b: } // Try to eliminate variables - if (var->deg_a == 0) { - ex c = bex.content(x); - ex g = gcd(aex, c, ca, cb, false); + if (var->deg_a == 0 && var->deg_b != 0 ) { + 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); + } else if (var->deg_b == 0 && var->deg_a != 0) { + 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; } @@ -1467,7 +1726,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. @@ -1790,7 +2049,7 @@ static ex frac_cancel(const ex &n, const ex &d) { ex num = n; ex den = d; - numeric pre_factor = _num1; + numeric pre_factor = *_num1_p; //std::clog << "frac_cancel num = " << num << ", den = " << den << std::endl; @@ -2235,6 +2494,17 @@ 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(basis_pref) || is_exactly_a(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); } @@ -2292,7 +2562,7 @@ static ex find_common_factor(const ex & e, ex & factor, exmap & repl) for (size_t i=0; i(x) || is_exactly_a(x)) { + if (is_exactly_a(x) || is_exactly_a(x) || is_a(x)) { ex f = 1; x = find_common_factor(x, f, repl); x *= f; @@ -2351,8 +2621,16 @@ term_done: ; return (new mul(v))->setflag(status_flags::dynallocated); } else if (is_exactly_a(e)) { - - return e.to_polynomial(repl); + 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; @@ -2363,7 +2641,7 @@ term_done: ; * 'a*(b*x+b*y)' to 'a*b*(x+y)'. */ ex collect_common_factors(const ex & e) { - if (is_exactly_a(e) || is_exactly_a(e)) { + if (is_exactly_a(e) || is_exactly_a(e) || is_exactly_a(e)) { exmap repl; ex factor = 1;