Re: Fast evaluation of recursive functions

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

On Sun, Feb 04, 2024 at 02:01:34PM +0100, Christian Krause 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.

Doing that for all function without qualification would slowdown GP
a lot and lead to unreasonnable memory usage.

Kevin script gives control of memoization to the user, which is good.

Beside, if you only want one value of a(n), using this method is almost
always suboptimal.

Consider this version of a(n):

a(n)=my(a1=1,a2=1);for(i=3,n,[a1,a2]=[a1+a2,a1]);a1;
? A=a(10^6);
  ***   last result computed in 8,814 ms.
? B=fibonacci(10^6);
  ***   last result computed in 4 ms.
? A==B
%16 = 1

(Do not even try this with a(n) memoizing or the previous one, 
this will eat all your memory).

Cheers,
Bill.