bridge/class-master/depend/pari/src/basemath/QX_factor.c
/* Assume A a squarefree ZX; return the vector of its rational roots */
Assume A a squarefree ZX; return the vector of its rational roots
Assume A a squarefree ZX ; return the vector of its rational roots
static GEN
DDF_roots(GEN A)
{
  GEN p, lc, lcpol, z, pe, pes2, bound;
  long i, m, e, lz;
  ulong pp;
  pari_sp av;
  pari_timer T;
  if (DEBUGLEVEL>2) timer_start(&T);
  pp = pick_prime(A, 1, &T);
  if (!pp) return cgetg(1,t_VEC); 
  p = utoipos(pp);
  lc = leading_coeff(A);
  if (is_pm1(lc))
  { lc = NULL; lcpol = A; }
  else
  { lc = absi_shallow(lc); lcpol = ZX_Z_mul(A, lc); }
  bound = root_bound(A); if (lc) bound = mulii(lc, bound);
  e = logintall(addiu(shifti(bound, 1), 1), p, &pe) + 1;
  pe = mulii(pe, p);
  pes2 = shifti(pe, -1);
  if (DEBUGLEVEL>2) timer_printf(&T, "Root bound");
  av = avma;
  z = ZpX_roots(A, p, e); lz = lg(z);
  z = deg1_from_roots(z, varn(A));
  if (DEBUGLEVEL>2) timer_printf(&T, "Hensel lift (mod %lu^%ld)", pp,e);
  for (m=1, i=1; i < lz; i++)
  {
    GEN q, r, y = gel(z,i);
    if (lc) y = ZX_Z_mul(y, lc);
    y = centermod_i(y, pe, pes2);
    if (! (q = ZX_divides(lcpol, y)) ) continue;
    lcpol = q;
    r = negi( constant_coeff(y) );
    if (lc) {
      r = gdiv(r,lc);
      lcpol = Q_primpart(lcpol);
      lc = absi_shallow( leading_coeff(lcpol) );
      if (is_pm1(lc)) lc = NULL; else lcpol = ZX_Z_mul(lcpol, lc);
    }
    gel(z,m++) = r;
    if (gc_needed(av,2))
    {
      if (DEBUGMEM>1) pari_warn(warnmem,"DDF_roots, m = %ld", m);
      gerepileall(av, lc? 3:2, &z, &lcpol, &lc);
    }
  }
  if (DEBUGLEVEL>2) timer_printf(&T, "Recombination");
  z[0] = evaltyp(t_VEC) | evallg(m); return z;
}
static GEN DDF_roots ( GEN A ) { GEN p , lc , lcpol , z , pe , pes2 , bound ; long i , m , e , lz ; ulong pp ; pari_sp av ; pari_timer T ; if ( DEBUGLEVEL > 2 ) timer_start ( & T ) ; pp = pick_prime ( A , 1 , & T ) ; if ( ! pp ) return cgetg ( 1 , t_VEC ) ; p = utoipos ( pp ) ; lc = leading_coeff ( A ) ; if ( is_pm1 ( lc ) ) { lc = NULL ; lcpol = A ; } else { lc = absi_shallow ( lc ) ; lcpol = ZX_Z_mul ( A , lc ) ; } bound = root_bound ( A ) ; if ( lc ) bound = mulii ( lc , bound ) ; e = logintall ( addiu ( shifti ( bound , 1 ) , 1 ) , p , & pe ) + 1 ; pe = mulii ( pe , p ) ; pes2 = shifti ( pe , -1 ) ; if ( DEBUGLEVEL > 2 ) timer_printf ( & T , " " ) ; av = avma ; z = ZpX_roots ( A , p , e ) ; lz = lg ( z ) ; z = deg1_from_roots ( z , varn ( A ) ) ; if ( DEBUGLEVEL > 2 ) timer_printf ( & T , " " , pp , e ) ; for ( m = 1 , i = 1 ; i < lz ; i ++ ) { GEN q , r , y = gel ( z , i ) ; if ( lc ) y = ZX_Z_mul ( y , lc ) ; y = centermod_i ( y , pe , pes2 ) ; if ( ! ( q = ZX_divides ( lcpol , y ) ) ) continue ; lcpol = q ; r = negi ( constant_coeff ( y ) ) ; if ( lc ) { r = gdiv ( r , lc ) ; lcpol = Q_primpart ( lcpol ) ; lc = absi_shallow ( leading_coeff ( lcpol ) ) ; if ( is_pm1 ( lc ) ) lc = NULL ; else lcpol = ZX_Z_mul ( lcpol , lc ) ; } gel ( z , m ++ ) = r ; if ( gc_needed ( av , 2 ) ) { if ( DEBUGMEM > 1 ) pari_warn ( warnmem , " " , m ) ; gerepileall ( av , lc ? 3 : 2 , & z , & lcpol , & lc ) ; } } if ( DEBUGLEVEL > 2 ) timer_printf ( & T , " " ) ; z [ 0 ] = evaltyp ( t_VEC ) | evallg ( m ) ; return z ; }
Assume A a squarefree ZX; return the vector of its rational roots
Assume A a squarefree ZX ; return the vector of its rational roots
/* no root */