Re: nffactor() timing

[Xavier Roblot <roblot@cs.concordia.ca>]

Igor Schein wrote:
>
> I define functions f and g as follows:
> ? f(x)=x^16+x^12+x^5+1
> ? polredabs(f(x))
> x^16 - x^11 + x^4 + 1
> ? g(x)=x^16-x^11+x^4+1
>
> Then I try all 4 possible combinations:
>
> nffactor(nfinit(g(y)),g(x))
> nffactor(nfinit(g(y)),f(x))
> 
> nffactor(nfinit(f(y)),g(x))
> nffactor(nfinit(f(y)),f(x))
> 
> The first two return the result in 12 seconds on Ultra-60.
> The last two take forever ( I ran for 1.5 hours, then gave up).
> "exposant considere" and precision keep doubling, and I don't know if
> it'd ever finish.

The precision must be increased when the exposant is doubled. This is corrected
in the following patch, there were also some precision adjustements needed and a
couple of typos. This should make it work.

Xavier Roblot

*** ./src/modules/nffactor.c.orig	Wed Dec 16 19:17:58 1998
--- ./src/modules/nffactor.c		Fri Jan 22 15:43:37 1999
***************
*** 842,850 ****
  	       (long)C);
  
    k2=gmul2n(gmulgs(glog(gdivgs(gmul2n(C,2),n),DEFAULTPREC),n),-1);
!   if (signe(k2)<0) k2=gun;
!   if (fl) k2=mulrr(k2,dbltor(1.1));
! 
    minp=gmin(gexp(gmul2n(k2,-6),BIGDEFAULTPREC), maxp);
    minp=gceil(minp);
  
--- 842,850 ----
  	       (long)C);
  
    k2=gmul2n(gmulgs(glog(gdivgs(gmul2n(C,2),n),DEFAULTPREC),n),-1);
!   if (!fl) k2=mulrr(k2,dbltor(1.1));  
!   if (gcmp(k2, gun)<0) k2=gun;
!   
    minp=gmin(gexp(gmul2n(k2,-6),BIGDEFAULTPREC), maxp);
    minp=gceil(minp);
  
***************
*** 896,906 ****
    affir(mulii(absi(dk),gpui(p,k,0)),p2);
    p2=shifti(gceil(mplog(p2)),-1);
  
! #ifdef LONG_IS_64BIT
!   newprec=max(DEFAULTPREC, (long)(itos(p2)*pariK1+4));
! #else
!   newprec=max(DEFAULTPREC, (long)(itos(p2)*pariK1+8));
! #endif
  
    if (DEBUGLEVEL>=4)
      fprintferr("nouvelle precision : %ld\n",newprec);
--- 896,902 ----
    affir(mulii(absi(dk),gpui(p,k,0)),p2);
    p2=shifti(gceil(mplog(p2)),-1);
  
!   newprec = MEDDEFAULTPREC + (long)(itos(p2)*pariK1);
  
    if (DEBUGLEVEL>=4)
      fprintferr("nouvelle precision : %ld\n",newprec);
***************
*** 1257,1263 ****
  T2_matrix_pow(GEN nf, GEN T2, GEN pr, GEN C, GEN kmax, long prec)
  {
    long N,k,av=avma,av1,lim,DEBUG2=DEBUGLEVEL;
!   GEN p1,p3,p,u,C2,rep;
  
    DEBUGLEVEL=0;
    k=itos(kmax);
--- 1253,1259 ----
  T2_matrix_pow(GEN nf, GEN T2, GEN pr, GEN C, GEN kmax, long prec)
  {
    long N,k,av=avma,av1,lim,DEBUG2=DEBUGLEVEL;
!   GEN p1,p3,p2,p,u,C2,rep;
  
    DEBUGLEVEL=0;
    k=itos(kmax);
***************
*** 1304,1310 ****
--- 1300,1315 ----
  
      if (test_mat(p3,p,C2,k,N)) break;
  
+     /* il faut augmenter la precision en meme temps */
+     p2=cgetr(DEFAULTPREC);
+     affir(gpuigs(p,k),p2);
+     p2=shifti(gceil(mplog(p2)),-1);
+     prec += (long)(itos(p2)*pariK1);
+     T2=nf_init_t2(nf,prec);
+     if (DEBUG2>=4)
+       fprintferr("nouvelle precision : %ld\n",prec);
      k = k<<1; p1 = idealmullll(nf,p1,p1);
+ 
      if (low_stack(lim, (av1+3*bot)>>2))
      {
        if (DEBUGMEM>1) err(warnmem,"T2_matrix_pow");