Search code examples
stack-overflowparistack-sizepari-gp

Stack Overflow when using gp2c but not when using gp directly with the same program (PARI/GP)

So I wanted to calculate a sum from a particular projecteuler question using gp. Here's the, admittedly unreadable, code:

{
n = 10000;
m=100;
sum(k=1,n,eulerphi(k),0.) - (sum(k=1,n,eulerphi(k)*(k * binomial(n-k,m-1) + sum(p = max(m + k - n - 1,1), k-1, (k-p)*binomial(n+p-k-1,m-2),0.)), 0.))/binomial(n,m)
}

This code takes two minutes or three to output the answer on my fairly modest machine but it does it without going over the default parisize = 8000000 (around 8 MB of memory).

Now, I read somewhere that gp2c which compiles gp scripts into c code can improve performance.

So I just made a program.gp file:

calculate() = {n = 10000; m=100; sum(k=1,n,eulerphi(k),0.) - (sum(k=1,n,eulerphi(k)*(k * binomial(n-k,m-1) + sum(p = max(m + k - n - 1,1), k-1, (k-p)*binomial(n+p-k-1,m-2),0.)), 0.))/binomial(n,m)}

And run it with gp2c-run program.gp.

In the interactive prompt that comes up, I just executed calculate(). However, to my surprise, I got a stack overflow with it asking me to increase the stack size even when I changed parisizemax to almost 2 GB.

? default(parisizemax, 2000000000)
  ***   Warning: new maximum stack size = 2000003072 (1907.352 Mbytes).
? calculate()
  *** calculate: Warning: increasing stack size to 16000000.
  *** calculate: Warning: increasing stack size to 32000000.
  *** calculate: Warning: increasing stack size to 64000000.
  *** calculate: Warning: increasing stack size to 128000000.
  *** calculate: Warning: increasing stack size to 256000000.
  *** calculate: Warning: increasing stack size to 512000000.
  *** calculate: Warning: increasing stack size to 1024000000.
  *** calculate: Warning: increasing stack size to 2000003072.
  ***   at top-level: calculate()
  ***                 ^-----------
  *** calculate: the PARI stack overflows !
  current stack size: 2000003072 (1907.352 Mbytes)
  [hint] you can increase 'parisizemax' using default()

  ***   Break loop: type 'break' to go back to GP prompt

Why does the same program, when compiled to c need so much extra memory? For reference, the same program with n = 1000 instead of 10000 only shows the answer after increasing the stack size to 256000000 (250 MB) whereas it just needs the default 8 MB when just using gp. Something doesn't add up.

Solution

  • By default, neither gp2c nor gp2c-run generate code to handle the PARI stack, meaning you will get stack overflows quickly. Use gp2c-run -g program.gp: the -g flag will cause gp2c to clean up the stack as the computation progresses. There is such an example in the gp2c tutorial.