[GiNaC-devel] Bug in sqrfree

[Richard B. Kreckel]

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 at 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 at 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/>