Bill Allombert on Mon, 23 Jan 2017 21:46:29 +0100


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

Re: Getting a very large polynomial into pari/gp


On Sun, Jan 01, 2017 at 06:39:03PM +0100, Bill Allombert wrote:
> On Sun, Jan 01, 2017 at 03:47:11AM +0000, Neill Clift wrote:
> > On 12/31/2016 9:05 AM, Bill Allombert wrote:
> > > The libpari library provides a set of functions to deal with polynomials
> > > over F_p that implement the half-GCD algorithm but they are not directly
> > > available in GP.
> > >
> > > Try:
> > > install("FpX_gcd","GGG")
> > > p = 2^64-59;
> > > a = Pol(read("a.gp"));
> > > b = Pol(read("b.gp"));
> > > FpX_gcd(a,b,p)
> > >
> > > and actually since p is less than 2^64 there is another function that
> > > use a more compact representation of polynomials (Vecsmall), but the
> > > above function will do the conversions for you.
> > > Read about FpX, FpX_gcd, Flx and Flx_gcd in the documentation.
> > While the other gcd ran overnight this one failed in an hour.
> > 
> > (18:03) gp > FpX_gcd(a,b,p)
> >    ***   at top-level: FpX_gcd(a,b,p)
> >    ***                 ^--------------
> >    *** FpX_gcd: not enough memory
> > (19:08) gp >
> > 
> > This seems to be different from the stack size messages I have got 
> > (stack size set to 64G).

Without a copy of a and b, I cannot ascertain what cause this, but
the halfgcd algorithm use much more memory than the normal one.

If you like, send me your polynomial and I try that on a machine with
3TB of RAM.

Cheers,
Bill.