Karim BELABAS on Thu, 21 Feb 2002 19:56:59 +0100 (MET)

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

Re: [PARI] LGEFBITS and list manipulations

On Thu, 14 Feb 2002, Philippe Elbaz-Vincent wrote:
> I need to manipulate huge lists of data under PARI, and I've noticed that
> under a 32 bits architecture, the max length is 65533.
> could someone explain to me why on a 32 bits machine LGEFBITS is limited
> to 65533, in particular for list creations and manipulations (listcreate,
> etc...)

Short-sighted overloading of lgef() macro. This used to correspond only to
the degree of a polynomial [ which were limited to "small" degrees since only
naïve algorithms were implemented; besides, the codeword for "degree" is
also used for "variable number", so larger degree means less variables ]

Instead of introducing a new macro to deal with the new type t_LIST, the old
one was re-used, thereby imposing the same limitation on list size than for
polynomial degrees.

You can modify that in a dedicated gp binary (modify also VARNBITS, VARNSHIFT
and MAXVARN)  [ This is painful, btw, far too many hardcoded when they can
all be computed from a small subset. I'll change it. ]

But beware you will have less variables to play with.

> Usually what is the best way (in term of efficiency) to manipulate lists of
> arbitrary length (but quite large btw) with PARI ?

The short (possibly unhelpful) answer is: write in C. It's memory efficient
and faster (albeit only by a constant factor in both cases).

Long answer: make that lists of lists of ... Then the maximum length becomes
about 2^(16n) where n is your recursion level.  Possibly use hashing
techniques to balance out the various lists (and speed up comparisons).

Hope this helps,

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/