Karim BELABAS on Wed, 8 Oct 2003 20:50:04 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polcompositum() vs factornf() performance comparison |
On Wed, 8 Oct 2003, Igor Schein wrote: > ? p1= x^16+8*x^14+148*x^12-184*x^10+5680*x^8-102304*x^6+546088*x^4-1557232*x^2+4351396; > ? p2=x^16+8*x^14-152*x^12+416*x^10+13030*x^8-12904*x^6+15688*x^4+954368*x^2+657721; > ? # > timer = 1 (on) > ? poldegree((p=polcompositum(p1,p2))[#p]) > time = 1,110 ms. > 32 > ? matsize(factornf(p1,subst(p2,x,y))) > time = 2,260 ms. > [8, 2] > > Basically, I am verifying in 2 different ways that 2 number fields are > non-isomorphic, but it turns out factornf ( for which nfisisom is a > wrapper ) No. It depends on the input data. The interface is completely inappropriate because I did not finish the implantation of my variant of van Hoeij's algorithm in arbitrary orders. It should always call nfroots. Currently it only does so when the 2nd argument is of nf type. > is twice slower!! > Any comment? Yes. Both commands return much more information than your stated needs. The first one is a bit less wasteful [ factoring over Z is easier than over a number field of degree 16. Here you compute many extra gcds ]. nfisisom(p1, nfinit(p2)) should be about 10 times faster. The nfinit call can be replaced by nfinit([p2, nfbasis(p2, 1)]) if the discriminant of p2 is not smooth. Also possible is nfroots( nfinit(subst(p2,x,y)), p1 ) which should be about as fast. If you don't need the isomorphism, you can improve a little on the above, but it's not available from GP. Cheers, Karim. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://www.parigp-home.de/ [PARI/GP]