X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=blobdiff_plain;f=ginac%2Fnormal.cpp;h=db1ca467e422f856e4687bb3b5b58f3889ada51c;hp=98efe98539e264fea938294fcd3aa0e54cfeb053;hb=b87f623d787279a123c8db77cef2c84bc5874239;hpb=6d225ee55693c0617d254e6fa283c00c71bd2919 diff --git a/ginac/normal.cpp b/ginac/normal.cpp index 98efe985..db1ca467 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. * @@ -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 @@ -710,6 +714,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 +755,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 +863,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 +937,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 +1087,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 +1247,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 +1272,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 +1284,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 +1369,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 +1388,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 +1422,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 +1450,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,6 +1503,26 @@ 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; + } + } + // Gather symbol statistics sym_desc_vec sym_stats; get_symbol_stats(a, b, sym_stats); @@ -1391,16 +1542,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; } @@ -1467,7 +1620,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 +1943,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; @@ -2351,8 +2504,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::posint)) { + 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 +2524,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; @@ -2375,4 +2536,37 @@ ex collect_common_factors(const ex & 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(); +} + + } // namespace GiNaC