bridge/class-master/depend/pari/src/basemath/Flx.c
/* as FpX_divrem but working only on ulong types.
 * if relevant, *pr is the last object on stack */
as FpX_divrem but working only on ulong types.
if relevant, *pr is the last object on stack
as FpX_divrem but working only on ulong types . if relevant * pr is the last object on stack
static GEN
Flx_divrem_basecase(GEN x, GEN y, ulong p, GEN *pr)
{
  GEN z,q,c;
  long dx,dy,dy1,dz,i,j;
  ulong p1,inv;
  long sv=x[1];
  dy = degpol(y);
  if (dy<0) pari_err_INV("Flx_divrem",y);
  if (pr == ONLY_REM) return Flx_rem_basecase(x, y, p);
  if (!dy)
  {
    if (pr && pr != ONLY_DIVIDES) *pr = pol0_Flx(sv);
    if (y[2] == 1UL) return Flx_copy(x);
    return Flx_Fl_mul(x, Fl_inv(y[2], p), p);
  }
  dx = degpol(x);
  dz = dx-dy;
  if (dz < 0)
  {
    q = pol0_Flx(sv);
    if (pr && pr != ONLY_DIVIDES) *pr = Flx_copy(x);
    return q;
  }
  x += 2;
  y += 2;
  z = cgetg(dz + 3, t_VECSMALL); z[1] = sv; z += 2;
  inv = uel(y, dy);
  if (inv != 1UL) inv = Fl_inv(inv,p);
  for (dy1=dy-1; dy1>=0 && !y[dy1]; dy1--);
  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? (long) ((p - p1)*inv) % p: 0;
    }
  }
  else
  {
    z[dz] = Fl_mul(inv, x[dx], p);
    for (i=dx-1; i>=dy; --i)
    { 
      p1 = p - uel(x,i);
      for (j=i-dy1; j<=i && j<=dz; j++)
        p1 = Fl_add(p1, Fl_mul(z[j],y[i-j],p), p);
      z[i-dy] = p1? Fl_mul(p - p1, inv, p): 0;
    }
  }
  q = Flx_renormalize(z-2, dz+3);
  if (!pr) return q;
  c = cgetg(dy + 3, t_VECSMALL); c[1] = sv; c += 2;
  if (SMALL_ULONG(p))
  {
    for (i=0; i<dy; i++)
    {
      p1 = (ulong)z[0]*y[i];
      for (j=maxss(1,i-dy1); j<=i && j<=dz; j++)
      {
        p1 += (ulong)z[j]*y[i-j];
        if (p1 & HIGHBIT) p1 %= p;
      }
      c[i] = Fl_sub(x[i], p1%p, p);
    }
  }
  else
  {
    for (i=0; i<dy; i++)
    {
      p1 = Fl_mul(z[0],y[i],p);
      for (j=maxss(1,i-dy1); j<=i && j<=dz; j++)
        p1 = Fl_add(p1, Fl_mul(z[j],y[i-j],p), p);
      c[i] = Fl_sub(x[i], p1, p);
    }
  }
  i=dy-1; while (i>=0 && !c[i]) i--;
  c = Flx_renormalize(c-2, i+3);
  if (pr == ONLY_DIVIDES)
  { if (lg(c) != 2) return NULL; }
  else
    *pr = c;
  return q;
}
static GEN Flx_divrem_basecase ( GEN x , GEN y , ulong p , GEN * pr ) { GEN z , q , c ; long dx , dy , dy1 , dz , i , j ; ulong p1 , inv ; long sv = x [ 1 ] ; dy = degpol ( y ) ; if ( dy < 0 ) pari_err_INV ( " " , y ) ; if ( pr == ONLY_REM ) return Flx_rem_basecase ( x , y , p ) ; if ( ! dy ) { if ( pr && pr != ONLY_DIVIDES ) * pr = pol0_Flx ( sv ) ; if ( y [ 2 ] == 1UL ) return Flx_copy ( x ) ; return Flx_Fl_mul ( x , Fl_inv ( y [ 2 ] , p ) , p ) ; } dx = degpol ( x ) ; dz = dx - dy ; if ( dz < 0 ) { q = pol0_Flx ( sv ) ; if ( pr && pr != ONLY_DIVIDES ) * pr = Flx_copy ( x ) ; return q ; } x += 2 ; y += 2 ; z = cgetg ( dz + 3 , t_VECSMALL ) ; z [ 1 ] = sv ; z += 2 ; inv = uel ( y , dy ) ; if ( inv != 1UL ) inv = Fl_inv ( inv , p ) ; for ( dy1 = dy - 1 ; dy1 >= 0 && ! y [ dy1 ] ; dy1 -- ) ; 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 ? ( long ) ( ( p - p1 ) * inv ) % p : 0 ; } } else { z [ dz ] = Fl_mul ( inv , x [ dx ] , p ) ; for ( i = dx - 1 ; i >= dy ; -- i ) { p1 = p - uel ( x , i ) ; for ( j = i - dy1 ; j <= i && j <= dz ; j ++ ) p1 = Fl_add ( p1 , Fl_mul ( z [ j ] , y [ i - j ] , p ) , p ) ; z [ i - dy ] = p1 ? Fl_mul ( p - p1 , inv , p ) : 0 ; } } q = Flx_renormalize ( z - 2 , dz + 3 ) ; if ( ! pr ) return q ; c = cgetg ( dy + 3 , t_VECSMALL ) ; c [ 1 ] = sv ; c += 2 ; if ( SMALL_ULONG ( p ) ) { for ( i = 0 ; i < dy ; i ++ ) { p1 = ( ulong ) z [ 0 ] * y [ i ] ; for ( j = maxss ( 1 , i - dy1 ) ; j <= i && j <= dz ; j ++ ) { p1 += ( ulong ) z [ j ] * y [ i - j ] ; if ( p1 & HIGHBIT ) p1 %= p ; } c [ i ] = Fl_sub ( x [ i ] , p1 % p , p ) ; } } else { for ( i = 0 ; i < dy ; i ++ ) { p1 = Fl_mul ( z [ 0 ] , y [ i ] , p ) ; for ( j = maxss ( 1 , i - dy1 ) ; j <= i && j <= dz ; j ++ ) p1 = Fl_add ( p1 , Fl_mul ( z [ j ] , y [ i - j ] , p ) , p ) ; c [ i ] = Fl_sub ( x [ i ] , p1 , p ) ; } } i = dy - 1 ; while ( i >= 0 && ! c [ i ] ) i -- ; c = Flx_renormalize ( c - 2 , i + 3 ) ; if ( pr == ONLY_DIVIDES ) { if ( lg ( c ) != 2 ) return NULL ; } else * pr = c ; return q ; }
as FpX_divrem but working only on ulong types.
as FpX_divrem but working only on ulong types .
/* compute -p1 instead of p1 (pb with ulongs otherwise) */ /* compute -p1 instead of p1 (pb with ulongs otherwise) */