Re: polynomial degree too large

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

[Marc Kellog:]
> How can I get PARI-GP to let me have a polynomial with huge degree?  My
> version 2.0.17 beta won't let me have a monomial with exponent larger than
> 2^16 (x^65532 is ok, x^65533 gives me a "degree overflow" error).
> 
> However, it does let me set series precision up to 2^24.

Which is a bug. As a placeholder, a series object can indeed contain that
many terms, but PARI won't be able to handle any of the objects thus
created. You'll get a valuation overflow immediately (in 2.0.18) or a
corrupted object liable to crash the session (2.0.17 and before). The
number of significant terms for a series and a maximum degree for a
polynomial are in fact the same.

> Is there a simple fix for my problem?

Yes and no.

First the 'no' part: PARI wasn't made to handle large (esp. sparse)
objects. Hence memory use will be huge and many basic operations (say
Euclidean division) will take a _lot_ of time on polynomials of degree
65533 (even monomials).

The 'yes' part: the values are hardcoded but can be changed in at least 2
ways.

a) easy way: get a 64bit machine

b) when a) is not an option [ in fact, it's usually a bad idea to use PARI
on 64bit machines, it's consistently (much) slower than on comparable 32
bit processors ], remains the hacker's way:

  In src/headers/parigen.h (lines 54.ff) you can find the following code
  defining the bitmasks for the second codeword of polynomial objects
  [ I added the comments ] :

#ifndef LONG_IS_64BIT
[...]
#   define LGEFBITS    (0x0000ffffUL) // 2^16 - 1 = 3 + 65532
                                      // (lgef(x) - 3 is the degree)
[...]
#   define VARNSHIFT   16

# ifndef OLD_CODES
[...]
#   define VARNBITS    (0x3fff0000UL)
[...]
#   define MAXVARN     16383 // decimal for 0x3fff = VARNBITS >> VARNSHIFT

  You can change these values, reducing the number of variable names (if
  you need 16383 variables then you should be using vectors not individual
  names). For instance

#   define LGEFBITS    (0x000fffffUL) // 2^20 - 1 = 3 + 1048572
[...]
#   define VARNSHIFT   20

# ifndef OLD_CODES
[...]
#   define VARNBITS    (0x3ff00000UL)
[...]
#   define MAXVARN     1023 // decimal for 0x3ff

But anything non trivial involving polynomials of degree 1048572 will be
infinitely slow... (and even a single monomial produced by GP will need 3MB
of memory). If you also want series involving that many terms you'll have
to modify the other bitmasks (increase PRECPBITS and lower VALPBITS).

Good luck,

    Karim.


__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://hasse.mathematik.tu-muenchen.de/ntsw/pari/