Re: Fwd: Re: Using local variable for memoizing in recursion

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Mike Day [2019-07-14 12:31]:
> OK - here's a version which presets a vector of indices,  ix,
> so you don't need the divide modulo k1.
> It doesn't appear to affect the performance much, though,
> at least in my Windows 10 interpreter  version.  I haven't
> discovered how to do gp2c ...
> 
> pnkv_4(n,k) = {my(k1=k+1,k2=k+2,t=vector(k2,i,vector(k1)), kx=k1, ky=0,
>   ix=vector(1+2*k1-1,i,1+(k2-i)%k1), offset=k1);
>     t[k1][2]=1;
>     for(i=1, n-1,
>        for(j=2,k1,
>           ky=ix[j+offset];
>           t[k2][j]=t[kx][j-1]+t[ky][j]);
> \\ to examine the current indices...
> \\ print(i," ",offset," ",vector(k,l,ix[l+1+offset]));
>        if(offset, offset--, offset=k);
>        kx=1+(k+i)%(k1);
>        t[kx]=t[k2]);
> return(t[k2])}
> 
> Tips on how to optimise line by line would be helpful!

Here's my take:

\\ vecsum(pnkv_4(n,k)), assuming n > 1
pnk_4(n,k) =
{ my(k1 = k+1, kx = k1, a = 1, t = vector(k1, i, vector(k)));
  t[k1][1] = 1;
  for (i = 1, n-1,
    my(ky = a);
    t[a] = vector(k, j, if (!(ky--), ky = k1);
                        if (j == 1, t[ky][1]
                                  , t[kx][j-1] + t[ky][j]));
    kx = a; if (a++ > k1, a = 1));
  vecsum(t[a-1]);
}

(12:47) gp > vecsum(pnkv_4(10000,3000))
time = 31,224 ms.
%1 = 36167251325636291851786878829976856243927867494801874150751474019863050338273687745917678081066889663513003

(12:47) gp > pnk_4(10000,3000)
time = 24,893 ms.
%2 = 36167251325636291851786878829976856243927867494801874150751474019863050338273687745917678081066889663513003

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`