bridge/class-master/depend/pari/src/basemath/Flx.c
/* separate from Flx_divrem for maximal speed. */
separate from Flx_divrem for maximal speed.
separate from Flx_divrem for maximal speed .
static GEN
Flx_rem_basecase(GEN x, GEN y, ulong p)
{
  pari_sp av;
  GEN z, c;
  long dx,dy,dy1,dz,i,j;
  ulong p1,inv;
  long vs=x[1];
  dy = degpol(y); if (!dy) return pol0_Flx(x[1]);
  dx = degpol(x);
  dz = dx-dy; if (dz < 0) return Flx_copy(x);
  x += 2; y += 2;
  inv = y[dy];
  if (inv != 1UL) inv = Fl_inv(inv,p);
  for (dy1=dy-1; dy1>=0 && !y[dy1]; dy1--);
  c = cgetg(dy+3, t_VECSMALL); c[1]=vs; c += 2; av=avma;
  z = cgetg(dz+3, t_VECSMALL); z[1]=vs; z += 2;
  if (SMALL_ULONG(p))
  {
    z[dz] = (inv*x[dx]) % p;
    for (i=dx-1; i>=dy; --i)
    {
      p1 = p - x[i]; 
      for (j=i-dy1; j<=i && j<=dz; j++)
      {
        p1 += z[j]*y[i-j];
        if (p1 & HIGHBIT) p1 %= p;
      }
      p1 %= p;
      z[i-dy] = p1? ((p - p1)*inv) % p: 0;
    }
    for (i=0; i<dy; i++)
    {
      p1 = z[0]*y[i];
      for (j=maxss(1,i-dy1); j<=i && j<=dz; j++)
      {
        p1 += z[j]*y[i-j];
        if (p1 & HIGHBIT) p1 %= p;
      }
      c[i] = Fl_sub(x[i], p1%p, p);
    }
  }
  else
  {
    ulong pi = get_Fl_red(p);
    z[dz] = Fl_mul_pre(inv, x[dx], p, pi);
    for (i=dx-1; i>=dy; --i)
    {
      p1 = p - x[i]; 
      for (j=i-dy1; j<=i && j<=dz; j++)
        p1 = Fl_addmul_pre(p1, z[j], y[i - j], p, pi);
      z[i-dy] = p1? Fl_mul_pre(p - p1, inv, p, pi): 0;
    }
    for (i=0; i<dy; i++)
    {
      p1 = Fl_mul_pre(z[0],y[i],p,pi);
      for (j=maxss(1,i-dy1); j<=i && j<=dz; j++)
        p1 = Fl_addmul_pre(p1, z[j], y[i - j], p, pi);
      c[i] = Fl_sub(x[i], p1, p);
    }
  }
  i = dy-1; while (i>=0 && !c[i]) i--;
  avma=av;
  return Flx_renormalize(c-2, i+3);
}
static GEN Flx_rem_basecase ( GEN x , GEN y , ulong p ) { pari_sp av ; GEN z , c ; long dx , dy , dy1 , dz , i , j ; ulong p1 , inv ; long vs = x [ 1 ] ; dy = degpol ( y ) ; if ( ! dy ) return pol0_Flx ( x [ 1 ] ) ; dx = degpol ( x ) ; dz = dx - dy ; if ( dz < 0 ) return Flx_copy ( x ) ; x += 2 ; y += 2 ; inv = y [ dy ] ; if ( inv != 1UL ) inv = Fl_inv ( inv , p ) ; for ( dy1 = dy - 1 ; dy1 >= 0 && ! y [ dy1 ] ; dy1 -- ) ; c = cgetg ( dy + 3 , t_VECSMALL ) ; c [ 1 ] = vs ; c += 2 ; av = avma ; z = cgetg ( dz + 3 , t_VECSMALL ) ; z [ 1 ] = vs ; z += 2 ; if ( SMALL_ULONG ( p ) ) { z [ dz ] = ( inv * x [ dx ] ) % p ; for ( i = dx - 1 ; i >= dy ; -- i ) { p1 = p - x [ i ] ; for ( j = i - dy1 ; j <= i && j <= dz ; j ++ ) { p1 += z [ j ] * y [ i - j ] ; if ( p1 & HIGHBIT ) p1 %= p ; } p1 %= p ; z [ i - dy ] = p1 ? ( ( p - p1 ) * inv ) % p : 0 ; } for ( i = 0 ; i < dy ; i ++ ) { p1 = z [ 0 ] * y [ i ] ; for ( j = maxss ( 1 , i - dy1 ) ; j <= i && j <= dz ; j ++ ) { p1 += z [ j ] * y [ i - j ] ; if ( p1 & HIGHBIT ) p1 %= p ; } c [ i ] = Fl_sub ( x [ i ] , p1 % p , p ) ; } } else { ulong pi = get_Fl_red ( p ) ; z [ dz ] = Fl_mul_pre ( inv , x [ dx ] , p , pi ) ; for ( i = dx - 1 ; i >= dy ; -- i ) { p1 = p - x [ i ] ; for ( j = i - dy1 ; j <= i && j <= dz ; j ++ ) p1 = Fl_addmul_pre ( p1 , z [ j ] , y [ i - j ] , p , pi ) ; z [ i - dy ] = p1 ? Fl_mul_pre ( p - p1 , inv , p , pi ) : 0 ; } for ( i = 0 ; i < dy ; i ++ ) { p1 = Fl_mul_pre ( z [ 0 ] , y [ i ] , p , pi ) ; for ( j = maxss ( 1 , i - dy1 ) ; j <= i && j <= dz ; j ++ ) p1 = Fl_addmul_pre ( p1 , z [ j ] , y [ i - j ] , p , pi ) ; c [ i ] = Fl_sub ( x [ i ] , p1 , p ) ; } } i = dy - 1 ; while ( i >= 0 && ! c [ i ] ) i -- ; avma = av ; return Flx_renormalize ( c - 2 , i + 3 ) ; }
separate from Flx_divrem for maximal speed.
separate from Flx_divrem for maximal speed .
/* compute -p1 instead of p1 (pb with ulongs otherwise) */ /* compute -p1 instead of p1 (pb with ulongs otherwise) */