Re: Fast evaluation of recursive functions

[Charles Greathouse <crgreathouse@gmail.com>]

This is a hard problem (undecidable in general). Even tagging functions manually isn’t that easy (in C with gcc extensions): deciding what is pure and const is difficult. I’d love to see this in PARI but it seems somewhere between “major research project” and “don’t even bother”.

On Sun, Feb 4, 2024 at 8:01 AM Christian Krause <me@ckrause.org> wrote:

Hello Bill and Ruud,

Thanks for your super-fast answers and suggestions. I generate GP code from another language. In general, they are systems of recursive functions. While I don't want to output the vector-based version to the users, it is a neat alternative to speed up the computation which should work for my use case.

Regarding side effects: why does PARI not know which of its own functions have side effects and which don't? In general, I would expect all arithmetic operations to be free of side effects. Even if it doesn't work in all cases, PARI could automatically infer whether it is applicable or not, and cache under the hood. IMHO, such kind of optimization can and should be done inside the computation engine. Kevin's script is rather a workaround.

Best regards,

Christian

On Sun, 4 Feb 2024 at 12:29, Ruud H.G. van Tol <rvtol@isolution.nl> wrote:

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