[GiNaC-devel] [PATCH] gcd: fix heuristics to chose main variable properly

[Alexei Sheplyakov]

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



-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20061120/3a58c97c/attachment.pgp