Re: Using local variable for memoizing in recursion

[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


On 12/07/2019 08:40, Дмитрий Рыбас wrote:
> I'm trying to write a function that computes a number of partitions of 
> integer n with no more that k parts.
> As I don't know if there exist short way (and Ramanujan did not give 
> us the formula for that), I use long way: recursion.
>
> M=Map();
> memo_p(n,k)={
> my(res=0);
> if(n==0 && k==0,return(1));
> if(k<1,return(0));
> if(mapisdefined(M,[n,k],&res),return(res));
> if(k>=n,res=numbpart(n);mapput(M,[n,k],res);return(res));
> res=memo_p(n,k-1)+memo_p(n-k,k);
> mapput(M,[n,k],res);
> return(res);}
>
> So, calling memo_p(n,k) returns desired number of partitions, it's O'k
>
> But, all memoized values remain in memory in map variable M, and 
> function memo_p() requires existanse of global variable M.
> One can, of course, just use
>
> kill(M)
>
> by hand but that's not good.
>
> Is it possible to write a function that
> -- creates some local variable M with empty map
> -- gives that variable M to another function (maybe within "main" 
> function) that recusively calculates it's value using given map
> -- returns calculated value
> -- exits, thus destroying that map variable
>
> Thank you,
> Dmitry.
>
> P.S. Running that code on windows 7 (pari/gp version 2.11.0) with
> M=Map();memo_p(10000,3000)
> results in pari/gp executable "gp.exe" crush.



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus