Bill Allombert on Thu, 24 Aug 2017 23:14:16 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Speed up {Flx,FpX,FpXQX}_divrem_basecase for suitable polynomials |
On Tue, Sep 08, 2015 at 11:47:30AM +0200, Peter Bruin wrote: > Bonjour, > > When computing with non-prime finite fields, one is often free to choose > a defining polynomial f (of some given degree n) over the prime field. > If we write f in the form c*X^n + f1 with deg(f1) < n, then for division > with remainder modulo f, it "should be" best to take deg(f1) as small as > possible. However, the current code for division with remainder in PARI > does not yet give an advantage in that case. > > The attached patch modifies the functions {Flx,FpX,FpXQX}_divrem_basecase > and Flx_rem_basecase in order to reduce the complexity of computing the > (quotient and) remainder of g by f from O((deg g - deg f)(deg f)) to > O((deg g - deg f)(deg f1)). Hello Peter, are you still interest in this topic ? You patch only covers the basecase, however the Barrett reduction method more or less takes advantage of deg(f1) being small already because this leads to a Barrett inverse with a special shape: 1/c+x^h*f2 with deg(f2) small (and h large). So the functions F*_get_red could be changed to detect this situation and use a different threshold in this case. What do you think ? Cheers, Bill.