|Bill Allombert on Mon, 03 Dec 2012 16:04:26 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Work on polrootsff/factorff|
On Sat, Dec 01, 2012 at 09:52:39PM +0100, Bill Allombert wrote: > Dear PARI developers, > > I am working on improving factorff and polrootsff which have historically > been quite slow in PARI. > > I join two benchmarks. The first file is for Trager algorithm (default) and the > second for Berlekamp algorithm. The third column is polrootsff timings and the > fourth is factorff timings. > > We see that Berlekamp is consistently much faster than Trager for large degree. > > There is three oddities: > 1) We did not implement Berlekamp over F_2^n yet, so we are still using Trager > for that case in the second file, so we get indentical results. > > 2) We have dedicated code for Trager over F_2^n but not for polrootsff yet, so > factorff is much faster. Unfortunately implementing Berlekamp over F_2^n is quite a bit of work. (We do not have yet implemented the class F2xqX_*) > 3) For degree 2 polynomials, polrootsff is much slower than factorff, because > the square root function over Fq is slow for large degree. I found a reference for the algorithm: <http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf> Cheers, Bill.