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

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

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)).
> 
> It passes the test suite and gives a noticeable speedup in my code for
> computing with curves over finite fields.  For example, with this patch,
> multiplying two 10 x 10 matrices over a field of size 59^100 becomes
> about 25% faster when choosing a polynomial of the form x^100 + O(x^3)
> instead of an arbitrary polynomial of degree 100 over F_59; previously
> there was no visible difference.

Thanks, I have applied your patch.
I join a test suite:

p=59,      deg 100: P1:288  P2:396
p=2^607-1, deg 10:  P1:569  P2:608
p=2^607-1, deg 20:  P1:1036 P2:1053
p=2^607-1, deg 30:  P1:1460 P2:1677
p=2^607-1, deg 40:  P1:512  P2:553

Cheers,
Bill

fun(p,P,N=1)=
{
  a=ffgen(P*Mod(1,p),'a);
  b=ffgen(ffinit(p,poldegree(P)),'b);
  M1=matrix(10,10,i,j,random(a));M2=matrix(10,10,i,j,random(a));
  M1b=matrix(10,10,i,j,random(b));M2b=matrix(10,10,i,j,random(b));
  gettime();
  for(i=1,N,M1*M2);
  print1("P1:",gettime());
  for(i=1,N,M1b*M2b);
  print(" P2:",gettime());
}
fun(59,x^100+x+38,100)
fun(2^607-1,x^20+2,10)
fun(2^607-1,x^30+x+52,10)
fun(2^607-1,x^40+x+25,10)
fun(2^607-1,x^100+2*x+58,1)