Re: Using local variable for memoizing in recursion

[Дмитрий Рыбас <drybas@gmail.com>]

Short add-on

offset is redundant variable. Without it, new version of pnkv():

pnkv_3(n,k) = {my(k1=k+1,k2=k+2,t=vector(k2,i,vector(k1)), kx=k1, ky=0);
    t[k1][2]=1;
    for(i=1, n-1,
       for(j=2,k1,
          ky=1+(k1-j+i)%(k1); /* to be optimized, takes half the CPU time */
          t[k2][j]=t[kx][j-1]+t[ky][j]);
       kx=1+(k+i)%(k1);
       t[kx]=t[k2]);
return(t[k2])}

пт, 12 июл. 2019 г. в 19:05, Дмитрий Рыбас <drybas@gmail.com>:

Mike,

I'm interested in both (memoization and partitions).

Thank you for code, it works indeed fast! 

I don't get why you need declaration of 

j=vector(k+1,i,[k+3-i,i])

in pnkv(), so I just deleted it.

Also, I don't see why you use max(0,n-1) so I just put 

for(i=1,n-1,

Also, the

if(l==k+1, return(tk));   

check is irrelevant (variable l does not exist by that time), so I deleted it as well.

Line

          ky=1+(k+2-l+offset)%(k+1);

takes about half the time of total runtime, I beleive that it can be furhter optimized as well.

So your pnkv() might be like that:

pnkv_2(n,k) = {my(k1=k+1,k2=k+2,t=vector(k2,i,vector(k1)), offset=0, kx=k1, ky=0);
    t[k1][2]=1;
    for(i=1, n-1,
       for(j=2,k1,
          ky=1+(k2-j+offset)%(k1); /* to be optimized, takes half the CPU time */
          t[k2][j]=t[kx][j-1]+t[ky][j]);
       offset++;
       kx=1+(k+offset)%(k1);
       t[kx]=t[k2]);
return(t[k2])}

Regards,

Dmitry.

пт, 12 июл. 2019 г. в 12:37, Mike Day <mike_liz.day@tiscali.co.uk>:

Dmitry, I don't know if you're more interested in memoisation or in the
partition application.
Anyway,  there was correspondence on partition functions towards the end
of April, 2019.
I posted a couple of functions, pnkv and pnkd for vectors of numbers of
partitions. (Hans L's
ideas might also be worth examining - he started that thread.)

So, for example:

(09:56) gp > vecsum(pnkv(1000,100))
time = 328 ms.
%6 = 15658181104580771094597751280645
(09:56) gp > memo_p(1000,100)
%7 = 15658181104580771094597751280645
(09:56) gp > memo_p(1000,200)
time = 3,548 ms.
%8 = 23936196137126761153040765380638
(09:57) gp > vecsum(pnkv(1000,200))
time = 704 ms.
%9 = 23936196137126761153040765380638
(09:57) gp > vecsum(pnkv(10000,200))%1000000  \\ quite a big number!
time = 7,658 ms.
%11 = 563365

As you say,  memo_p crashes version 2.11.1 in Windows 10 for (10000,3000);
FWIW, my function doesn't crash (or crush),  but does keep you waiting! :

(10:14) gp > vecsum(pnkv(10000,3000))%1000000
time = 2min, 17,563 ms.
%13 = 513003

In case it's of any use to you, I'm listing the function once again,
here, for your
convenience. Probably not great Pari GP code - I'm an APL/J-er by
preference!

pnkv(n,k) = {my(j=vector(k+1,i,[k+3-i,i]),
              t=matrix(1+k,1+k), tk=vector(1+k), offset=0, kx=k+1, ky);
    t[k+1,2]=1;
    for(i=1, max(0, n-1),
       for(l=2,k+1,
          ky=1+(k+2-l+offset)%(k+1);
          tk[l]=t[kx,l-1]+t[ky,l] ;
          );
       if(l==k+1, return(tk));
       offset++;
       kx=1+(k+offset)%(k+1);
       t[kx,]=tk;
    );
tk;

}

Might be of some use,

Mike