Re: Fast evaluation of recursive functions

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

On Sun, Feb 04, 2024 at 11:31:19AM +0100, Christian Krause wrote:
> Hello,
> I'm extensively using recursive function definitions and need to compute
> the first 0..N terms of them, for example
> 
> a(n)=if(n<2,1,a(n-1)+a(n-2))
> 
> for(n=0,100,print(a(n)))
> 
> The computation is very slow because PARI/GP apparently does not re-use
> previously computed terms.
> 
> I found the following GP script which implements a cache:
> https://user42.tuxfamily.org/pari-memoize/index.html
> 
> However, I was wondering if there is any *built-in support* for caching
> (recursive) function values?
> 
> An alternative could be to calculate recursive function terms
> incrementally. Is there any syntax/pattern in GP available for this?

Sure:

a(n)=
{
  my(V=vector(n));
  V[1]=1; V[2]=1;
  for(i=3, n, 
    V[i] = V[i-1] + V[i-2]
  );
  V;
}

? a(100)
%3 = [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,19740274219868223167,31940434634990099905,51680708854858323072,83621143489848422977,135301852344706746049,218922995834555169026,354224848179261915075]

Cheers,
Bill