Karim Belabas on Fri, 16 Jul 2010 00:41:50 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: nffactor vs factornf |
* Luis Felipe Tabera Alonso [2010-07-15 21:25]: > According to the documentation, factornf uses Trager's trick to perform a > factorization over the rationals and nffactor uses Van Hoeij's method, which > is preferable in many cases, but it needs a nf structure. > > I have some complicated number fields where I would like to factor > polynomials. If I already have the nf structure, I can use nffactor without > problems. But for these fields nf is very expensive, so factornf is faster (I > will not factor so many polynomials to do the effort). > > But, as I understand Van Hoeij method, one does not need the nf structure, it > may increase performance though. I am correct? Is there a way to use Van > Hoeij's method without computing nf of the number field? In the 'testing' branch, nffactor can live with a polynomial, instead of an nf structure, and compute internally the parts of the (missing) nf struct that it really needs : \\ trivial example (00:08) gp > nf=nfinit(y^20-2); nffactor(nf,x^10-2); time = 156 ms. (00:08) gp > nffactor(y^20-2, x^10-2); \\ about as fast time = 156 ms. \\ non-trivial example (00:08) gp > p= x^20 - 64857820*x^19 - 3862862*x^18 - 150*x^16 - 30*x^14 - 822*x^13 - 98578*x^11 + 8*x^9 + 43582*x^8 + 45*x^7 - 3033*x^6 - 1958664*x^4 + 493666*x^3 - 44*x + 1 (00:08) gp > nffactor(subst(p,x,y),p); time = 51,047 ms. (00:09) gp > nf=nfinit(subst(p,x,y)); nffactor(nf, p); time = 25,569 ms. N.B: nfinit(p) was very lucky in this case : it tries to factor a general 200-digits integer, and succeeds "quickly" (because the latter is almost prime...) What version are you using ? Cheers, K.B. -- Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP] `