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

[Peter Bruin <P.J.Bruin@math.leidenuniv.nl>]

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.  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?

Peter