Ruud H.G. van Tol on Sun, 04 Feb 2024 12:29:19 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Fast evaluation of recursive functions 


On 2024-02-04 11:31, Christian Krause wrote:
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. 

For that, you would need to be able to detect absence of side effects.
Example: a(n) = getabstime() + n



I found the following GP script which implements a cache:
https://user42.tuxfamily.org/pari-memoize/index.html
<https://user42.tuxfamily.org/pari-memoize/index.html>
That is Kevin Ryde's memoize.gp, and it works really well, so don't hesitate to use it.
See also https://pari.math.u-bordeaux.fr/pub/pari/manuals/2.15.4/users.pdf 3.2.11.
With a single integer parameter of limited range, a bitmap could be used to flag known values. 
But memoization generally uses a map.

-- Ruud