Re: Speed up {Flx,FpX,FpXQX}_divrem_basecase for suitable polynomials

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

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.