[GiNaC-devel] multivariate factorization (ginac/ginsh)

[Alexei Sheplyakov]

> > ># The following seems to take forever:
> > >
> > >>t;
> > >-E20^16*E4^8*E5^8*E1^16*q^4-(E10^24-E20^8*E5^16)*E4^16*E1^8+E2^24*E20^16*E5^8*q^4
> > >>factor(t);
> > >
> > ># ctrl-C
> > >  ginsh  815.46s user 3.39s system 94% cpu 14:26.22 total
> > >
> > >
> > >Is the latter a huge-ish task or does ginac have a performance issue here?
> 
> > I ran the example and I get an exception! So, it seems there is a bug somewhere.
> 
> It looks like a bug in gcd routines.  Proof: try computing
> 
> gcd(expand(t), expand(diff(t, q)))

The patch below should fix it. I'll post the proper patch (with a test case,
explanatory commit message, and all that) tomorrow.
 
 
diff --git a/ginac/polynomial/pgcd.cpp b/ginac/polynomial/pgcd.cpp
index 6e5e6b2..ef3748d 100644
--- a/ginac/polynomial/pgcd.cpp
+++ b/ginac/polynomial/pgcd.cpp
@@ -121,6 +121,8 @@ ex pgcd(const ex& A, const ex& B, const exvector& vars, const long p)
 			// evaluation point is bad. Skip it.
 			continue;
 		}
+		if (img_gcd_deg == 0)
+			return cont_gcd;
 
 		// Image has the same degree as the previous one
 		// (or at least not higher than the limit)
@@ -145,8 +147,6 @@ ex pgcd(const ex& A, const ex& B, const exvector& vars, const long p)
 			if (divide_in_z_p(Aprim, C, dummy1, vars, p) &&
 					divide_in_z_p(Bprim, C, dummy2, vars, p))
 				return (cont_gcd*C).expand().smod(pn);
-			else if (img_gcd_deg == 0)
-				return cont_gcd;
 			// else continue building the candidate
 		} 
 	} while(true);



Best regards,
	Alexei