Karim.Belabas on Sat, 7 Jul 2001 13:26:50 +0200 (MEST)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Another PARI failure of ellheight on elliptic curve [[1,-1,0,-1884,31951]] for LINUX 800MHz Athlon only (fwd)

On Fri, 6 Jul 2001, Martin Prickett wrote: [directly to me, not to the list]
> Many thanks for your earlier patch which we implemented. It did solve the
> problems we had with the example I gave. However, this afternoon, I have
> discovered that if I take curve e=ellinit([1,-1,0,-1884,31951]) and point
> P=[-591/64,115117/512] then ellheight(e,P) causes my computer to run out
> of memory on my Linux 800 MHz Athlon machine.

This is more annoying: given the input (ellinit structure at precision \p28),
there's no way the AGM can converge with the requested relative precision.
Hence yet another infinite loop (still in ellpointtoz, but independant of the
previous problem).

Please apply the following patch: it allows ellpointtoz to get out of the
infinite loop, at the expense of returning a result which has lower relative
accuracy than requested (exhibited by the number of significant digits
printed) when it becomes apparent that no progress can be made.

Of course, if you actually want that much precision, you'll have to re-run
the computation (including the ellinit) after increasing the default
'realprecision'.  I could have made it automatic (it can easily be recomputed
from the given "e"), but it seems like a waste to have each function
recompute its own private copy of the structure at extended precision.

I could also make it raise an exception ("precision too low in ..."), but
that seems less user-friendly than returning a result which is after all
completely correct: it only prints less significant digits than implicitly

Hope this helps,


Index: src/modules/elliptic.c
RCS file: /home/megrez/cvsroot/pari/src/modules/elliptic.c,v
retrieving revision 1.22
retrieving revision 1.23
diff -c -r1.22 -r1.23
*** src/modules/elliptic.c	2001/07/06 09:19:38	1.22
--- src/modules/elliptic.c	2001/07/07 11:11:57	1.23
*** 806,811 ****
--- 806,812 ----
      if (gsigne(greal(b)) != sw) b = gneg_i(b);
      a = gmul2n(gadd(gadd(a0,b0),gmul2n(b,1)),-2);
      r1 = gsub(a,b);
+     if (gcmp0(r1) || gexpo(r1) < gexpo(a) - bit_accuracy(prec)) break;
      p1 = gsqrt(gdiv(gadd(x0,r1),x0),prec);
      x1 = gmul(x0,gsqr(gmul2n(gaddsg(1,p1),-1)));
      r1 = gsub(x1,x0);

Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
PARI/GP Home Page: http://www.parigp-home.de/