Re: 64bit bug

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

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]