Re: Efficient way to define and evaluate polynomial function

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

On Wed, May 13, 2020 at 06:50:59PM +0200, Jérôme Raulin wrote:
> Hi,
> 
> Let's suppose that I need to evaluate many times the sum of the 5th power of
> the first 'n' integers. 1st implementation is to define :
> 
> sum_n_5(n) = (2*n^6 + 6*n^5 + 5*n^4 - n^2) \ 12;

Yes, this is not good.

> and call it directly. Still it not efficient and a better way is to use
> Horner form such as (the difference is small but for larger degree
> polynomial the difference may be huge) :
> 
> sumn_5(n) = n^2 * (-1 + n^2 * (5 + n * (6 + 2 * n))) \ 12;
> 
> Still the best way would be to directly use the polynomial form built from
> the coefficients so that Pari can use its internal polynomial evaluation
> function:
> 
> Pol([2, 6, 5, 0, -1, 0, 0])/12
> 
> But I fail to define a callable function this way. Surely subst(Pol([2, 6,
> 5, 0, -1, 0, 0],x),x,n)\12 is not at all what to be done.

Why not ? 

sumn_5(n) = subst(Pol([2, 6, 5, 0, -1, 0, 0]),'x,n)/12;

I suggest this one:

my(P=(2*n^6 + 6*n^5 + 5*n^4 - n^2)); sumn_5(n)=subst(P,'n,n)/12

and
my(P=(2*n^6 + 6*n^5 + 5*n^4 - n^2)); sumn_5(n)=eval(P)/12

Of course PARI has more fancy algorithms to evaluate polynomial
but they depend on the application.

Cheers,
Bill.