Improve gcd(a, b) where one argument is a power of a symbol.
authorRichard Kreckel <kreckel@ginac.de>
Wed, 31 Jan 2018 09:04:25 +0000 (10:04 +0100)
committerRichard Kreckel <kreckel@ginac.de>
Wed, 31 Jan 2018 09:04:25 +0000 (10:04 +0100)
commite7d79ac4ff7654908b7688bc1373624119682f5c
treedb6929f179d2ee69522831c2a61f6eec7a9dd7fc
parentd0ff428fb5b7bb565a0aea69e05e5705d840c16d
Improve gcd(a, b) where one argument is a power of a symbol.

The already implemented recursion
  gcd(x^n, x*p(x)) -> x*gcd(x^(n-1), p(x))
is not ambitious enough: If p(x) has a factor of x, it just goes through
the same step again, and if p(x) has a factor which is a power of x, this
is reapeted many times.

Example:
  gcd(x^n, expand(x^n*(1+x)))
used to go recurse through the gcd routine n times, which could
easily lead to a stack overflow for n about 10^5.

To improve the situation, introduce a special case for gcd where one
argument is a power of a symbol and just cancel the common factor.

This turned out to be the root cause of segfaults in matrix elimination
algorithms, as reported by Patrick Schulz and Vitaly Magerya:
Cf. <https://www.ginac.de/pipermail/ginac-list/2018-January/thread.html>
ginac/normal.cpp