Karim BELABAS on Fri, 26 Nov 1999 18:11:14 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: polynomial degree too large |
[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/