Karim BELABAS on Thu, 1 May 2003 02:09:26 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: 64bit bug |
On Tue, 29 Apr 2003, Karim BELABAS wrote: > On Mon, 28 Apr 2003, Igor Schein wrote: >> the following commands gets stuck in an infinite loop: >> >> factorpadic(x^3-1,3,10,1); > > Can't reproduce this on alpha. Can you debug it and try to pinpoint the > source of the problem ? I'm still not able to reproduce it, but I think I got it from staring at the code. Here's how I understand it: factorpadic(,1) cheats on the number field code by building a dummy (incomplete) nf structure for a possibly reducible (squarefree) polynomial [ T = x^3 - 1, here ]. Then primedec() is called to factor p in the maximal (etale) order of Q[X] / (T), and the fun starts: primedec is not aware we're cheating, and computes some useless data, in particular p-uniformizer and anti-uniformizer [ not needed from the point of view of factorff ]. The latter requires computing norms, by computing a resultant Res(T, A) for a rational polynomial A [ for an nf it would never be done that way, but we don't have an nf and primedec is clever enough to notice the structure lacks needed data, and use other available norm routines ]. It is known that the result is an integer though, so the code cleverly computes Res(T, primitive_part(A)), calling a modular algorithm and telling it the expected denominator. The ZY_ZXY_ResBound routine computes an upper bound B for the resultant using floating point computations, taking into account the known denominator. And actually computes log_2 B. Unfortunately, it was not expected that the norm of a non-zero element would be 0 [ too bad, we are not over a field... ], and it was not taken into account that we could have log_2 B < 0 ! The return value is typecast to (unsigned long), so a huge integer. This is interpreted as a forthcoming tough computation, requiring the computation of a better bound, using a floating point resultant computation. Unfortunately, the corresponding bound is still 0, and this is flagged as a precision error since we were expecting a large number. So increase precision and retry. Too bad, bound remains 0 --> oo loop. (Trivial) Fix: ensure the return value of ZY_ZXY_ResBound is non-negative. [ which is inexpensive and makes the routine more robust in any case: good thing ] Committed to CVS. Does it work now ??? Karim. P.S: There are many other things that could be corrected, but factorpadic(,1) is obsolete, and I don't want to maintain it. Especially since it can't work without major undocumented cheats (interface abuses) against a large set of other routines. This is bound to break again and again as the code evolves. -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathématiques, Bât. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud http://www.math.u-psud.fr/~belabas/ F-91405 Orsay (France) http://www.parigp-home.de/ [PARI/GP]