* 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)
}
#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)
const ex& exp_a = a.op(1);
ex pb = b.op(0);
const ex& exp_b = b.op(1);
+
+ // a = p^n, b = p^m, gcd = p^min(n, m)
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;
*cb = _ex1;
return power(p, exp_b);
}
- } else {
- ex p_co, pb_co;
- ex p_gcd = gcd(p, pb, &p_co, &pb_co, false);
- 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
+ }
+
+ 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;
// 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)
+ }
+
+ // 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_pow(const ex& a, const ex& b, ex* ca, ex* cb)