Karim BELABAS on Wed, 17 Jul 2002 22:33:17 +0200 (MEST)

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

Re: bnfisintnorm() bug

On Mon, 1 Jul 2002, Igor Schein wrote:
>    realprecision = 28 significant digits
> ? tnf=thueinit(x^7-401);
> time = 14,200 ms.
> ?  thue(tnf,88)
>   ***   division by zero in gdiv, gdivgs or ginv
> Undetected loss of precision.  If I compute tnf at \p140 ( see
> message 1522@pari-dev ), then it works fine.
> For comparison:
> ? bnfisintnorm(bnfinit(x^7-401),88)
>   ***   Warning: insufficient precision for fundamental units, not given.
>   ***   missing units in bnfnewprec.
> Insufficient precision properly detected.

I've rewritten the Thue module and fixed about 10 different (minor) problems
such as the above: truncation errors, division by 0, 32/64-bit dependency,
etc. + general cleanup (killed global variables, nicer looking diagnostics,
use homogeneous integer poleval instead of rational one, fixed comments,

My regression tests run smoothly. Can you check that I've not broken anything?

There's an obvious improvement that is still missing: enumeration of "small"
solutions can be very slow. See, e.g. thue(tnf, 400^7 - 401*250^7) [at \g2
you see it stalled for about 99% of computing time in the final enumeration]

Judging from a small GP script, computing integer roots y (via rootpadicfast)
for each fixed x is about 50 times faster than current implementation
[ evaluate for all (x,y), y dividing a fixed integer depending on x ] when
the bounds are "relatively large". Unfortunately this requires a little work
to code it in C: there's no equivalent to nfroots() over Q [ well, you can
use nfroots(nfinit(x),), but that's quite inefficient ].

I can write one, but maybe there are even better alternatives (e.g sieve-based).
Ideas ?

Also that part of the code will break when the RHS is larger than
2^(32*degree) [ uses C ints internally ]

Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
PARI/GP Home Page: http://www.parigp-home.de/