Xavier Roblot on Fri, 22 Jan 1999 15:53:11 -0500

 Re: nffactor() timing

```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");
```