Hello! Heuristic code in gcd [very] often makes bad choice of the main variable. In particular, if one of polynomials (say, p2) does not contain the variable x which _is contained_ in another one (say, p1), than gcd(p1, p2) will use such a variable as a main, so subsequent calculation becomes unnecessary complicated. Fixing this substantially improves worst case performance (less than minute versus infinity). Best regards, Alexei -- All science is either physics or stamp collecting. --- ginac/normal.cpp | 46 +++++++++++++++++++++++++++++++++++++++++++--- 1 files changed, 43 insertions(+), 3 deletions(-) diff --git a/ginac/normal.cpp b/ginac/normal.cpp index b2a4e8c..1cbf3c2 100644 --- a/ginac/normal.cpp +++ b/ginac/normal.cpp @@ -1589,11 +1589,51 @@ factored_b: } } + if (is_exactly_a<numeric>(aex)) { + numeric bcont = bex.integer_content(); + numeric g = gcd(ex_to<numeric>(aex), bcont); + if (ca) + *ca = ex_to<numeric>(aex)/g; + if (cb) + *cb = bex/g; + return g; + } + + if (is_exactly_a<numeric>(bex)) { + numeric acont = aex.integer_content(); + numeric g = gcd(ex_to<numeric>(bex), acont); + if (ca) + *ca = aex/g; + if (cb) + *cb = ex_to<numeric>(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; @@ -1607,14 +1647,14 @@ factored_b: } // Try to eliminate variables - if (var->deg_a == 0) { + 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_u * bex_p; return g; - } else if (var->deg_b == 0) { + } 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); -- 1.4.3.3