Bill Allombert on Tue, 05 Sep 2017 22:59:15 +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, Aug 29, 2017 at 09:42:01PM +0200, Peter Bruin wrote: > Hi Bill, > > > 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 ? > > This certainly sounds like it is worth trying. My impression is that we > should explicitly split up the Barrett inverse into its constant term > and x^h*f2, in order to take advantage of the zeroes in between. It happens that in practice, speed up occurs even without implementing that (with GMP). > Then > the question is if the choice whether to use Barrett reduction should > only depend on deg f2, or also on the total degree n. I haven't tried > to figure this out; do you have an idea? No, sorry. Cheers, Bill.