* computation, square-free factorization and rational function normalization. */
/*
- * GiNaC Copyright (C) 1999-2008 Johannes Gutenberg University Mainz, Germany
+ * GiNaC Copyright (C) 1999-2011 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
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include <algorithm>
-#include <map>
-
#include "normal.h"
#include "basic.h"
#include "ex.h"
#include "pseries.h"
#include "symbol.h"
#include "utils.h"
+#include "polynomial/chinrem_gcd.h"
+
+#include <algorithm>
+#include <map>
namespace GiNaC {
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.
+// code below is commented-out because it leads to a significant slowdown
+// 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)
// gcd helper to handle partially factored polynomials (to avoid expanding
// large expressions). At least one of the arguments should be a power.
-static ex gcd_pf_pow(const ex& a, const ex& b, ex* ca, ex* cb, bool check_args);
+static ex gcd_pf_pow(const ex& a, const ex& b, ex* ca, ex* cb);
// gcd helper to handle partially factored polynomials (to avoid expanding
// large expressions). At least one of the arguments should be a product.
-static ex gcd_pf_mul(const ex& a, const ex& b, ex* ca, ex* cb, bool check_args);
+static ex gcd_pf_mul(const ex& a, const ex& b, ex* ca, ex* cb);
/** Compute GCD (Greatest Common Divisor) of multivariate polynomials a(X)
* and b(X) in Z[X]. Optionally also compute the cofactors of a and b,
}
// Partially factored cases (to avoid expanding large expressions)
- if (is_exactly_a<mul>(a) || is_exactly_a<mul>(b))
- return gcd_pf_mul(a, b, ca, cb, check_args);
+ if (!(options & gcd_options::no_part_factored)) {
+ if (is_exactly_a<mul>(a) || is_exactly_a<mul>(b))
+ return gcd_pf_mul(a, b, ca, cb);
#if FAST_COMPARE
- if (is_exactly_a<power>(a) || is_exactly_a<power>(b))
- return gcd_pf_pow(a, b, ca, cb, check_args);
+
if (is_exactly_a<power>(a) || is_exactly_a<power>(b))
+ return gcd_pf_pow(a, b, ca, cb);
#endif
+ }
// Some trivial cases
ex aex = a.expand(), bex = b.expand();
// Try heuristic algorithm first, fall back to PRS if that failed
ex g;
- bool found = heur_gcd(g, aex, bex, ca, cb, var);
- if (found) {
- // heur_gcd have already computed cofactors...
- if (g.is_equal(_ex1)) {
- // ... but we want to keep them factored if possible.
- if (ca)
- *ca = a;
- if (cb)
- *cb = b;
+ if (!(options & gcd_options::no_heur_gcd)) {
+ bool found = heur_gcd(g, aex, bex, ca, cb, var);
+ if (found) {
+ // heur_gcd have already computed cofactors...
+ if (g.is_equal(_ex1)) {
+ // ... but we want to keep them factored if possible.
+ if (ca)
+ *ca = a;
+ if (cb)
+ *cb = b;
+ }
+ return g;
}
- return g;
- }
#if STATISTICS
- else {
- heur_gcd_failed++;
- }
+ else {
+ heur_gcd_failed++;
+ }
#endif
+ }
+ if (options & gcd_options::use_sr_gcd) {
+ g = sr_gcd(aex, bex, var);
+ } else {
+ exvector vars;
+ for (std::size_t n = sym_stats.size(); n-- != 0; )
+ vars.push_back(sym_stats[n].sym);
+ g = chinrem_gcd(aex, bex, vars);
+ }
- g = sr_gcd(aex, bex, var);
if (g.is_equal(_ex1)) {
// Keep cofactors factored if possible
if (ca)
return g;
}
-static ex gcd_pf_pow(const ex& a, const ex& b, ex* ca, ex* cb, bool check_args)
-{
- if (is_exactly_a<power>(a)) {
- ex p = a.op(0);
- const ex& exp_a = a.op(1);
- if (is_exactly_a<power>(b)) {
- 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)
- if (exp_a < exp_b) {
- if (ca)
- *ca = _ex1;
- if (cb)
- *cb = power(p, exp_b - exp_a);
- return power(p, exp_a);
- } else {
- if (ca)
- *ca = power(p, exp_a - exp_b);
- if (cb)
- *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 (ca)
- *ca = power(p, a.op(1) - 1);
- 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)
+// gcd helper to handle partially factored polynomials (to avoid expanding
+// large expressions). Both arguments should be powers.
+static ex gcd_pf_pow_pow(const ex& a, const ex& b, ex* ca, ex* cb)
+{
+ ex p = a.op(0);
+ const ex& exp_a = a.op(1);
+ ex pb = b.op(0);
+ const ex& exp_b = b.op(1);
- } else if (is_exactly_a<power>(b)) {
- ex p = b.op(0);
- if (p.is_equal(a)) {
- // a = p, b = p^n, gcd = p
+ // a = p^n, b = p^m, gcd = p^min(n, m)
+ if (p.is_equal(pb)) {
+ if (exp_a < exp_b) {
if (ca)
*ca = _ex1;
if (cb)
- *cb = power(p, b.op(1) - 1);
- return p;
+ *cb = power(p, exp_b - exp_a);
+ return power(p, exp_a);
+ } else {
+ if (ca)
+ *ca = power(p, exp_a - exp_b);
+ if (cb)
+ *cb = _ex1;
+ return power(p, exp_b);
}
+ }
- 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
+ ex p_co, pb_co;
+ ex p_gcd = gcd(p, pb, &p_co, &pb_co, false);
+ // a(x) = p(x)^n, b(x) = p_b(x)^m, gcd (p, p_b) = 1 ==> gcd(a,b) = 1
+ if (p_gcd.is_equal(_ex1)) {
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))
+ // XXX: do I need to check for p_gcd = -1?
+ }
- 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)
+ // 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) {
+ ex pg = gcd(power(p_co, exp_a), power(p_gcd, exp_b-exp_a)*power(pb_co, exp_b), ca, cb, false);
+ return power(p_gcd, exp_a)*pg;
+ } else {
+ ex pg = gcd(power(p_gcd, exp_a - exp_b)*power(p_co, exp_a), power(pb_co, exp_b), ca, cb, false);
+ return power(p_gcd, exp_b)*pg;
}
}
-static ex gcd_pf_mul(const ex& a, const ex& b, ex* ca, ex* cb, bool check_args)
+static ex gcd_pf_pow(const ex& a, const ex& b, ex* ca, ex* cb)
{
- if (is_exactly_a<mul>(a)) {
- if (is_exactly_a<mul>(b) && b.nops() > a.nops())
- goto factored_b;
-factored_a:
- size_t num = a.nops();
- exvector g; g.reserve(num);
- exvector acc_ca; acc_ca.reserve(num);
- ex part_b = b;
- for (size_t i=0; i<num; i++) {
- ex part_ca, part_cb;
- g.push_back(gcd(a.op(i), part_b, &part_ca, &part_cb, check_args));
- acc_ca.push_back(part_ca);
- part_b = part_cb;
- }
+ if (is_exactly_a<power>(a) && is_exactly_a<power>(b))
+ return gcd_pf_pow_pow(a, b, ca, cb);
+
+ if (is_exactly_a<power>(b) && (! is_exactly_a<power>(a)))
+ return gcd_pf_pow(b, a, cb, ca);
+
+ GINAC_ASSERT(is_exactly_a<power>(a));
+
+ ex p = a.op(0);
+ const ex& exp_a = a.op(1);
+ if (p.is_equal(b)) {
+ // a = p^n, b = p, gcd = p
if (ca)
- *ca = (new mul(acc_ca))->setflag(status_flags::dynallocated);
+ *ca = power(p, a.op(1) - 1);
if (cb)
- *cb = part_b;
- return (new mul(g))->setflag(status_flags::dynallocated);
- } else if (is_exactly_a<mul>(b)) {
- if (is_exactly_a<mul>(a) && a.nops() > b.nops())
- goto factored_a;
-factored_b:
- size_t num = b.nops();
- exvector g; g.reserve(num);
- exvector acc_cb; acc_cb.reserve(num);
- ex part_a = a;
- for (size_t i=0; i<num; i++) {
- ex part_ca, part_cb;
- g.push_back(gcd(part_a, b.op(i), &part_ca, &part_cb, check_args));
- acc_cb.push_back(part_cb);
- part_a = part_ca;
- }
+ *cb = _ex1;
+ return p;
+ }
+
+ ex p_co, bpart_co;
+ ex p_gcd = gcd(p, b, &p_co, &bpart_co, false);
+
+ // a(x) = p(x)^n, gcd(p, b) = 1 ==> gcd(a, b) = 1
+ if (p_gcd.is_equal(_ex1)) {
if (ca)
- *ca = part_a;
+ *ca = a;
if (cb)
- *cb = (new mul(acc_cb))->setflag(status_flags::dynallocated);
- return (new mul(g))->setflag(status_flags::dynallocated);
+ *cb = b;
+ return _ex1;
+ }
+ // 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))
+ ex rg = gcd(power(p_gcd, exp_a-1)*power(p_co, exp_a), bpart_co, ca, cb, false);
+ return p_gcd*rg;
+}
+
+static ex gcd_pf_mul(const ex& a, const ex& b, ex* ca, ex* cb)
+{
+ if (is_exactly_a<mul>(a) && is_exactly_a<mul>(b)
+ && (b.nops() > a.nops()))
+ return gcd_pf_mul(b, a, cb, ca);
+
+ if (is_exactly_a<mul>(b) && (!is_exactly_a<mul>(a)))
+ return gcd_pf_mul(b, a, cb, ca);
+
+ GINAC_ASSERT(is_exactly_a<mul>(a));
+ size_t num = a.nops();
+ exvector g; g.reserve(num);
+ exvector acc_ca; acc_ca.reserve(num);
+ ex part_b = b;
+ for (size_t i=0; i<num; i++) {
+ ex part_ca, part_cb;
+ g.push_back(gcd(a.op(i), part_b, &part_ca, &part_cb, false));
+ acc_ca.push_back(part_ca);
+ part_b = part_cb;
}
+ if (ca)
+ *ca = (new mul(acc_ca))->setflag(status_flags::dynallocated);
+ if (cb)
+ *cb = part_b;
+ return (new mul(g))->setflag(status_flags::dynallocated);
}
/** Compute LCM (Least Common Multiple) of multivariate polynomials in Z[X].
git://www.ginac.de / ginac.git / blobdiff