Roland Dreier on Tue, 27 Oct 1998 15:26:03 -0600 (CST)


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

Re: Large input to gp


On Tue, 27 Oct 1998, Karim BELABAS wrote:
> [Roland Dreier:]
> > I have the output of a gp program which produced a polynomial of degree
> > 3425 (!?) over F_5.  The program took a while to run, and I'd like to be
> > able to just read the polynomial into gp and continue working.  But just
> > feeding the output back in results in:
> > 
> > parisize = 40000000, primelimit = 500000, buffersize = 30000
> > ? res=Mod(1, 5)*sss1^3425 + Mod(4, 5)*sss1^3422 +
> > [lots and lots and lots deleted here]
> > + Mod(1, 5)*sss1 + Mod(3, 5)
> > 
> >   ***   the PARI stack overflows !!!
> > 
> >   ***   Warning: doubling stack size; new stack = 80000000.
> >   ***   not enough memory
> > 
> > What should I do here?
> 
> The problem is that given the form used to save the polynomial, GP has to
> expand the expression, doing one addition at a time, allocating a huge chunk
> of memory to hold the new polynomial (and all its coefficients, there's no
> sparse representation in PARI...) each time. Since the formula is not really
> parsed in advance, no garbage collecting can occur at this point, hence the
> stack overflows quickly.
> 
> The "easy" way to recover your polynomial is to cut it into smaller pieces
> in your file. A better solution (assuming you have perl on your machine):
> 
> 1) Save the following script, say, in sos.pl
> (maybe change the first line to the actual location of the perl binary on
> your system, e.g /usr/bin/perl under Linux)
> 
> #!/usr/local/bin/perl
> print "[";
> while(<>)
> {
>   s/\*\w+\^\d+//g;
>   s/\+/,/g; s/\n//; print;
> } 
> print "]";
> 
> 2) Assuming the polynomial is in file bigpol, type (under GP)
> 
>   vec = extern("sos.pl bigpol"); \\ creates a vector from the coefficients
>   pol = Polrev(vec, sss1);       \\ recover the polynomial.
> 
> This should work with default stack...
> 
>    Karim.

Thanks for the advice.  There was one oversight in your reply that I
should warn anyone else who may need this trick: the perl script that
converts from a polynomial to a vector does not take into account any
coefficients that may be zero.  I had to adapt the script to take into
account the degree of each term and output appropriate zero coefficients
as well.

Thanks,
Roland