Karim BELABAS on Wed, 23 Oct 2002 12:42:27 +0200 (MEST)

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

Re: excessive bnrstark() memory requirements

On Wed, 23 Oct 2002, Igor Schein wrote:

> On Tue, Oct 22, 2002 at 09:37:30PM +0200, Karim BELABAS wrote:
>> On Mon, 30 Sep 2002, Igor Schein wrote:
>>> the following command runs out of 2GB stack on 32bit platform:
>>> bnrstark(bnrinit(bnfinit(y^3+y^2-1706*y+26543),1,1),,1);
>>> Is it possible to do something about it?
>> I've made a few obvious improvements to memory usage in stark.c:InitPrimes().
>> I still doubt the above will run to completion: you're trying to construct a
>> field of degree 93...
> Well, it ran to a completion, albeit not satisfying one:
> ***   object too big, length can't fit in a codeword
> Any idea what's too big here?

The routines estimates it needs about 49035875 coefficients to reliably
compute the L-series value. The maximum length of an object on 32-bit machine
is 16777215 < 49035875 [ actually, the coefficient fit because they are
generated from the ones of prime index, but the auxiliary constant arrays
don't ].

At this point, I don't want to complicate this set of routines with
alternative strategies (time/space tradeoff, backup to disc, etc). The
algorithms and estimates are probably far from optimal.

You can try on 64-bit... [somehow I'm still dubious].

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/