Hi, Jens Vollinga wrote:
there seems to be a bug in the sqrfree function in GiNaC. The attached program when run will sooner or later stall (stuck in an infinite loop inside sqrfree()). I am not too familiar with the new code there, so I'd first like to ask the other devs whether they have any idea about it?
Depending on term ordering, runtime appears to go exponentially: rbk@wallace:~$ cat sqrfreebug.cpp #include <ginac/ginac.h> #include <iostream> using namespace std; using namespace GiNaC; int main(int argc, char* argv[]) { int n = atoi(argv[1]); for (int rep=0; rep<24; ++rep) { symbol a("a"), b("b"), e("e"), h("h"); ex expr = (a*b+e)*pow(h,n); expr = expr.expand(); expr = sqrfree(expr); } return 0; } rbk@wallace:~$ for i in $(seq 10 24); do printf "$i: "; /usr/bin/time --format="%Us" ./a.out $i; done 10: 0.07s 11: 0.08s 12: 0.10s 13: 0.15s 14: 0.17s 15: 0.23s 16: 0.30s 17: 0.61s 18: 1.28s 19: 2.47s 20: 5.24s 21: 8.14s 22: 20.49s 23: 45.45s 24: 68.89s Gdb hints at the culprit being the polynomial division routine that is called by sqrfree. The behavior seems to be new, indeed. So, a bisection could provide some more insight. Bye -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>