Re: Using local variable for memoizing in recursion

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

On Fri, Jul 12, 2019 at 07:05:36PM +0300, Дмитрий Рыбас wrote:
> 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.

This function is one where GP2C makes a big difference
if you add type markers:

pnkv_3(n:small,k:small) =
{
  my(k1:small=k+1,k2:small=k+2,t=vector(k2,i,vector(k1)), kx:small=k1, ky:small=0);
    t[k1][2]=1;
    for(i:small=1, n-1,
       for(j:small=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])
}

with gp:
? pnkv_3(10000,200);
? ##
  ***   last result computed in 1,268 ms.
with gp2c-run -g
? pnkv_3(10000,200);
? ##
  ***   last result computed in 260 ms.

Cheers,
Bill.