Karim Belabas on Mon, 06 Aug 2012 03:35:50 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polisirreducible(f*Mod(1,2)) vs. factormod(f,2) |
* Bill Allombert [2011-10-24 23:34] >* Max Alekseyev [2011-10-24 17:32]: >> Why polisirreducible(f*Mod(1,2)) is not much faster (if fact, even >> slightly slower) than factormod(f,2) on average? >> Factoring is an overkill for testing irreducibility but that's >> currently not true in PARI/GP. >> >> ? q = vector(1000,i,random(10^4)); >> ? for(i=1,#q,factormod( x^q[i]+x+1,2) ) >> ? ## >> *** last result computed in 4min, 6,019 ms. >> ? for(i=1,#q,polisirreducible( (x^q[i]+x+1)*Mod(1,2) ) ) >> ? ## >> *** last result computed in 4min, 8,812 ms. > > Currently, the implementation of polisirreducible simply call factor(). > Probably because this avoided the duplication of the code to compute > the coefficient field (which is a rather fragile operation). I just changed this, since that code in now abstracted in RgX_type()... There are still a few cases where polisirreducible() still calls factor() although it doesn't need to [ non prime finite fields in particular ], but the situation has improved somewhat: ? q = vector(1000,i,random(10^4)); ? for(i=1,#q,factormod(x^q[i]+x+1,2)) time = 1min, 148 ms. ? for(i=1,#q,polisirreducible( (x^q[i]+x+1)*Mod(1,2) ) ) time = 5,204 ms. N.B. The factormod() part has been improved as well. In pari.stable: ? for(i=1,#q,factormod( x^q[i]+x+1,2)) time = 3min, 13,572 ms. The timings are still unimpressive: they could be improved by implementing better algorithms, in particular iterated Frobenius (= Shoup-von zur Gathen) 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-bordeaux1.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] `