Very slow gcd

[benruijl]

The following gcd is extremely slow:

S x1,...,x10;
L F = gcd_(32*x7^13*x8^19*x9*x10^7+56*x5^10*x6^6*x7*x8^22*x9-64*x4^2*x6*x7^6*x8^25*x9^5*x10-20*x4^9*x6*x7^16*x8*x9^5*x10^8-35*x4^9*x5^10*x6^7*x7^4*x8^4*x9^5*x10+40*x4^11*x6^2*x7^9*x8^7*x9^9*x10^2-4*x3^4*x5^5*x6*x7^13*x9^10*x10^7-7*x3^4*x5^15*x6^7*x7*x8^3*x9^10+8*x3^4*x4^2*x5^5*x6^2*x7^6*x8^6*x9^14*x10-16*x3^8*x5^12*x7^13*x10^7-28*x3^8*x5^22*x6^6*x7*x8^3+32*x3^8*x4^2*x5^12*x6*x7^6*x8^6*x9^4*x10-4*x2*x3*x4^6*x5^7*x7^13*x8^4*x10^8-7*x2*x3*x4^6*x5^17*x6^6*x7*x8^7*x10+8*x2*x3*x4^8*x5^7*x6*x7^6*x8^10*x9^4*x10^2+80*x2^2*x3^10*x7^7*x8^19*x9*x10-50*x2^2*x3^10*x4^9*x6*x7^10*x8*x9^5*x10^2-10*x2^2*x3^14*x5^5*x6*x7^7*x9^10*x10-40*x2^2*x3^18*x5^12*x7^7*x10+40*x2^3*x3^8*x6^2*x8^19*x9*x10^7-25*x2^3*x3^8*x4^9*x6^3*x7^3*x8*x9^5*x10^8-10*x2^3*x3^11*x4^6*x5^7*x7^7*x8^4*x10^2-5*x2^3*x3^12*x5^5*x6^3*x9^10*x10^7-20*x2^3*x3^16*x5^12*x6^2*x10^7-5*x2^4*x3^9*x4^6*x5^7*x6^2*x8^4*x10^8-8*x1*x3*x4^7*x5^9*x8^21*x9+5*x1*x3*x4^16*x5^9*x6*x7^3*x8^3*x9^5*x10+x1*x3^5*x4^7*x5^14*x6*x8^2*x9^10+4*x1*x3^9*x4^7*x5^21*x8^2+x1*x2*x3^2*x4^13*x5^16*x8^6*x10-4*x1*x2^5*x4^4*x5^2*x6*x7^13*x8^5*x10^9-7*x1*x2^5*x4^4*x5^12*x6^7*x7*x8^8*x10^2+8*x1*x2^5*x4^6*x5^2*x6^2*x7^6*x8^11*x9^4*x10^3-10*x1*x2^7*x3^10*x4^4*x5^2*x6*x7^7*x8^5*x10^3-5*x1*x2^8*x3^8*x4^4*x5^2*x6^3*x8^5*x10^9+72*x1^2*x2^3*x4*x5*x8^32*x9-45*x1^2*x2^3*x4^10*x5*x6*x7^3*x8^14*x9^5*x10-9*x1^2*x2^3*x3^4*x4*x5^6*x6*x8^13*x9^10-36*x1^2*x2^3*x3^8*x4*x5^13*x8^13-9*x1^2*x2^4*x3*x4^7*x5^8*x8^17*x10+x1^2*x2^5*x3*x4^11*x5^11*x6*x8^7*x10^2-9*x1^3*x2^8*x4^5*x5^3*x6*x8^18*x10^2+48*x1^17*x6^3*x8^19*x9-30*x1^17*x4^9*x6^4*x7^3*x8*x9^5*x10-6*x1^17*x3^4*x5^5*x6^4*x9^10-24*x1^17*x3^8*x5^12*x6^3-6*x1^17*x2*x3*x4^6*x5^7*x6^3*x8^4*x10-6*x1^18*x2^5*x4^4*x5^2*x6^4*x8^5*x10^2,
-48*x3^7*x4*x6*x7*x8^24*x9^2*x10^4+30*x3^7*x4^10*x6^2*x7^4*x8^6*x9^6*x10^5+6*x3^11*x4*x5^5*x6^2*x7*x8^5*x9^11*x10^4+24*x3^15*x4*x5^12*x6*x7*x8^5*x9*x10^4+6*x2*x3^8*x4^7*x5^7*x6*x7*x8^9*x9*x10^5+48*x2^4*x3^3*x6^2*x7^3*x8^27*x9-30*x2^4*x3^3*x4^9*x6^3*x7^6*x8^9*x9^5*x10-6*x2^4*x3^7*x5^5*x6^3*x7^3*x8^8*x9^10-24*x2^4*x3^11*x5^12*x6^2*x7^3*x8^8-6*x2^5*x3^4*x4^6*x5^7*x6^2*x7^3*x8^12*x10+24*x1*x3^19*x8^19*x9-15*x1*x3^19*x4^9*x6*x7^3*x8*x9^5*x10-3*x1*x3^23*x5^5*x6*x9^10-12*x1*x3^27*x5^12-3*x1*x2*x3^20*x4^6*x5^7*x8^4*x10+6*x1*x2^5*x3^7*x4^5*x5^2*x6^2*x7*x8^10*x9*x10^6-6*x1*x2^9*x3^3*x4^4*x5^2*x6^3*x7^3*x8^13*x10^2-40*x1*x2^19*x8^19*x9+25*x1*x2^19*x4^9*x6*x7^3*x8*x9^5*x10+5*x1*x2^19*x3^4*x5^5*x6*x9^10+20*x1*x2^19*x3^8*x5^12+5*x1*x2^20*x3*x4^6*x5^7*x8^4*x10-3*x1^2*x2^5*x3^19*x4^4*x5^2*x6*x8^5*x10^2+5*x1^2*x2^24*x4^4*x5^2*x6*x8^5*x10^2-80*x1^3*x2^4*x3^13*x8^19*x9+50*x1^3*x2^4*x3^13*x4^9*x6*x7^3*x8*x9^5*x10+10*x1^3*x2^4*x3^17*x5^5*x6*x9^10+40*x1^3*x2^4*x3^21*x5^12+10*x1^3*x2^5*x3^14*x4^6*x5^7*x8^4*x10+10*x1^4*x2^9*x3^13*x4^4*x5^2*x6*x8^5*x10^2-24*x1^6*x3*x8^19*x9^14+15*x1^6*x3*x4^9*x6*x7^3*x8*x9^18*x10+3*x1^6*x3^5*x5^5*x6*x9^23+12*x1^6*x3^9*x5^12*x9^13+3*x1^6*x2*x3^2*x4^6*x5^7*x8^4*x9^13*x10+3*x1^7*x2^5*x3*x4^4*x5^2*x6*x8^5*x9^13*x10^2);
P;
.end

[tueda]

Ah, actually this example is just extremely slow:

Time =     131.64 sec    Generated terms =          6
               F         Terms in output =          6
                         Bytes used      =        364

   F =
      8*x8^19*x9 - 5*x4^9*x6*x7^3*x8*x9^5*x10 - x3^4*x5^5*x6*x9^10 - 4*x3^8*
      x5^12 - x2*x3*x4^6*x5^7*x8^4*x10 - x1*x2^5*x4^4*x5^2*x6*x8^5*x10^2;

$ ./run.py --nvars 10 --degree 20 --nterms 10 --coeffpow 1 --nwarmups 0 --nproblems 1 --aout --form --fermat --rings
a.out: 0.035s
FORM: 132.774s
Fermat: 0.580s
Rings: 0.163s

Unlucky case?

[benruijl]

It's only 10000 times as slow :)

I can have a look what's going on.