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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Jul 18, 2019 at 05:31:20PM +0300, Дмитрий Рыбас wrote:
> Mike,
> 
> Thanks to user *mihaild *on russian scientific forum dxdy.ru , here is the
> best (so far), iterative (non-recursive), low-memory (one vector of lenght
> n) algorithm for partitions function p(n,k) calculation:
> 
> 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);
> }
> 
> Try it!

Thanks!
This is the version with type annotation for GP2C:

pnk(n:small,k:small)=
{
  my(M=vector(n),res:int=0);
  M[1]=1;
  for(i:small=1,k,
    for(j:small=1,n-2*i+1,
       M[i+j]+=M[j]);
    res+=M[n-i+1]:int);
  return(res);
}

For pnk(10000,3000):
With GP:   4,585 ms.
With GP2C:   609 ms

Cheers,
Bill