Re: 2.5.1: *** thue: bug in thue (totally rational case), please report

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Georgi Guninski [2012-07-16 10:11]:
> 2.5.1: *** thue: bug in thue (totally rational case), please report
> 
> 
> Pari 2.5.1/2.4.3 told me to report this:
> 
> ? allocatemem();allocatemem();allocatemem();allocatemem();
>   ***   Warning: new stack size = 16000000 (15.259 Mbytes).
> ? pp=x^3 - 537825*x^2 + 537824*x + 1;a=1;tt=thueinit(pp,0);t=thue(tt,a);
>   ***   at top-level: ...;a=1;tt=thueinit(pp,0);t=thue(tt,a)
>   ***                                             ^----------
>   *** thue: bug in thue (totally rational case), please report

This is in principle a known bug
  http://pari.math.u-bordeaux1.fr/cgi-bin/bugreport.cgi?bug=951
for which a possible fix is complicated to implement (described
in Guillaume Hanrot's thesis).

In this case, however, the heuristic criterion used to decide whether
we indeed fall into this problematic "totally rational case" is wrong.
The patch below [ applies to both master and stable ] fixes the problem
in a naive way:

(11:52) gp >  thue(thueinit(x^3-537825*x^2+537824*x+1), 1)
time = 1,364 ms.
%1 = [[0, 1], [1, -537825], [1, 1], [537824, 1], [1, 0]]

I'll try to find something more robust later.

> If allocatemem() is skippped there is no bug for me.

If allocatemem() is skipped, the computation failed (PARI stack overflows)
for me [ on a 64bit machine ].

Cheers,

    K.B.

diff --git a/src/modules/thue.c b/src/modules/thue.c
index d5107a3..f9d2c3f 100644
--- a/src/modules/thue.c
+++ b/src/modules/thue.c
@@ -796,9 +796,10 @@ get_Bx_LLL(long i1, GEN Delta, GEN Lambda, GEN eps5, long prec, baker_s *BS)
     for (;;)
     {
       GEN oldBx = Bx, kappa = utoipos(10);
+      const long cfMAX = 30;
       long cf;
 
-      for (cf = 0; cf < 10; cf++, kappa = muliu(kappa,10))
+      for (cf = 0; cf < cfMAX; cf++, kappa = muliu(kappa,10))
       {
         int res = LLL_1stPass(&B0, kappa, BS, &Bx);
         if (res) break;
@@ -806,7 +807,7 @@ get_Bx_LLL(long i1, GEN Delta, GEN Lambda, GEN eps5, long prec, baker_s *BS)
       }
 
       /* FIXME: TO BE COMPLETED */
-      if (cf == 10)
+      if (cf == cfMAX)
       { /* Semirational or totally rational case */
         GEN Q, ep, q, l0, denbound;
 
-- 
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`