Ilya Zakharevich on Thu, 09 May 2019 13:31:41 +0200


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

Evaluation of polynomials: precision loss


To calculate some Fourier transforms, I need to evaluate polynomials
of very high degree.  Is PARI going to use Horner’s method?

If so, then the rounding errors would accumulate, right?  One can
fight this with using Horner’s method for short runs only, and combine
short runs using Horner’s method for a power of argument.  (Somewhat
similar to “a step” of FFT — but without speedups.)

Additionally, for me the point of evaluation is a root of
unity — which also has numerical errors.  There does not seem to exist
a way to avoid *these* accumulating for a general polynomial — unless
one does substpol(P,x^N,x0^N) first (calculating x0^N using
transcendental functions), right?

However, the way I implemented substpol() initially, it would not
optimize for a power of variable — so it may be painfully
slow — unless something has changed…

Ilya