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

[Mike Day <mike_liz.day@tiscali.co.uk>]

I've just noticed an edge-condition failure in Karim's version (below):
need to replace
   vecsum(t[a-1]);  \\ at end of function by
   vecsum(t[kx]);   \\ was problem when a=1 !

Mike

On 14/07/2019 13:33, Mike Day wrote:

Again, I forgot to copy to the Forum!
Mike

-------- Forwarded Message --------

Subject:	Re: Fwd: Re: Using local variable for memoizing in recursion
Date:	Sun, 14 Jul 2019 13:26:00 +0100
From:	Mike Day <mike_liz.day@tiscali.co.uk>
To:	Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>

Thanks, Karim,  for doing some optimisation.  I'll have a look.

I'd accepted Dmitry's assertion that execution of a particular line took
half the execution time,  so sought a way to avoid the calculation.

I see you're using "if ( ) " in preference to my earlier (...)%k1, and my latest
use of a look-up array for the indices.  So an if() construct is efficient enough
here.

I still wonder,  though,  how I can _examine_ a function's performance,
line by line,   in order to optimise by hand/eye/brain...

And while we're at it,  is Dmitry's use of a vector of vectors,  t, to be
preferred to my earlier use of a matrix, also t,  with similar dimensions?

Cheers,

Mike

On 14/07/2019 12:23, Karim Belabas wrote:

* 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]
`

Virus-free. www.avast.com