Hi, On Mon, Nov 20, 2006 at 09:02:23PM +0100, bernard.parisse wrote:
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).
in this case, you should compute the content with respect to x of p1 and then the gcd of the content with p2.
The old code used to do so: if (var->deg_a == 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) { 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); if (ca) *ca *= aex_u * aex_p; return g; } This is exactly what leads to inferior performance (example is attached).
A good candidate for the gcd will be the gcd of p2 with a random integer linear combination of the coeffs of p1 with respect to x.
I'm not trying to provide a [better] guess. The point is to prevent the code from making particulary bad ones, especially when polynomials in question are relatively prime.
Anyway, heuristic gcd is most of the time not a good choice if there are more than a few variables. Modular gcd is in my experience faster (and this is theoretically also true).
I agree with you completely. But unfortunately GiNaC is not well suited for doing modular arithmetics [yet] :( Best regards, Alexei -- All science is either physics or stamp collecting.