X-Git-Url: https://ginac.de/ginac.git//ginac.git?a=blobdiff_plain;ds=sidebyside;f=ginac%2Fnormal.cpp;h=64c34ac290037348d835420d49ff1b2bf019000a;hb=0e2c1a2f1b97b9b3ea3c9ac81e0d943c5694fd3a;hp=cb7e35ef1db41c318bcb5d9fdd4339d6f4c8f1ee;hpb=9feaa6e9f50b5dc224966af616a4828db461d69d;p=ginac.git diff --git a/ginac/normal.cpp b/ginac/normal.cpp index cb7e35ef..64c34ac2 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 @@ -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)); @@ -730,24 +730,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 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++) { @@ -1247,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; } } @@ -1348,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; @@ -1365,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 @@ -1374,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)) { @@ -1386,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 @@ -1842,7 +1898,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;