Re: Help understanding generating functions, (partitioning n into k parts)

[Jacques Gélinas <jacquesg00@hotmail.com>]

>  Try it!
              For the record, with Windows 8.1 64 bits/Intel i5-2.30Ghz (2013)

================== start cut
pnk(n,k)= my(M=vector(n),res=0);M[1]=1;for(i=1,k, for(j=1,n-2*i+1,\
  M[i+j]+=M[j]); res+=M[n-i+1]); return(res);
pnk(1000,300) == 24060233693068843871790330541103
##
================== end paste

2007 2.4.1 cygwin 32 bits (local instead of my) : 157 ms
2010 2.4.3 mingw 32 bits : 62 ms, 46 ms, 63 ms, 62 ms, 47 ms
2014 2.6.2 mingw 32 bits : 63 ms
2017 2.8.2 mingw 64 bits: 79 ms
2019 2.12.1 cygwin 64 bits : 78 ms

1. Looks like GP 32 bits is faster for this calculation.

2. As usual, GP2C will make this function much faster (pnk.gp contains the function code):

# gp2c-run pnk.gp      <==== convert to C & compile & run GP ... how could it be simpler ?
$ ?pnk
pnk: installed function library name: pnk prototype: D0,G,D0,G,
$ pnk(1000,300) == 24060233693068843871790330541103
time = 16 ms.

3. http://pari.math.u-bordeaux.fr/gp.html took 290 ms, not so bad

4. pnk(10000,3000) took 7,900 ms on my 2.12.1 cygwin GP, 
compared to 4,500 ms reported by Bill Alombert for his GP.


Jacques Gélinas