Re: polredabs() arch-dependent behavior

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

* Igor Schein <igor@txc.com> [2004-01-13 19:46]:
> the following command works instantaneously on 64bit architecture:
> 
> ? {#polredabs(
> x^32 - 272*x^30 + 26520*x^28 - 1271600*x^26 + 35003680*x^24 - 603552224*x^22
>  + 6870103376*x^20 - 53322479072*x^18 + 287642983160*x^16 - 1088541888192*x^
> 14 + 2892828010656*x^12 - 5358926519104*x^10 + 6800229039232*x^8 - 572504516
> 5696*x^6 + 3020092633280*x^4 - 892896952448*x^2 + 111612119056
> ,4)}
> 14
> 
> but runs forever on 32bit.

10 minutes (PIII 1GHz, slow) is not forever.

Besides, I do not thing there is a bug here. Given the high degree and
(annoying) Galois structure, I would not expect fast termination.

In both cases, one only gets sensible running times because (roughly) the
first half of the basis vectors for the maximal order are found to generate a
subfield.

Here, a floating point LLL has a slightly different behaviour on 32bit and
64bit machines (not all accuracies are available on 64bit machines, and there
are subtly different rounding patterns). This gives two different acceptable
bases i.e both are correct LLL-reduced outputs to the routine. 

On 32bit machines, only the first 15 vectors generate a subfield; add the
16th and you get the whole field. On 64bit, the first 16 vectors still
generate a subfield. ( Essentially, vectors 16 and 17 are permuted, both
having almost the same length. )

Hence the difference.

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/ 
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]