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

[bernard.parisse]

Alexei Sheplyakov wrote:

>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).
>  
>
hello,

in this case, you should compute the content with respect to x of p1
and then the gcd of the content with p2. 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.
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).