comp-horner-k

▸ function CompHornerK (p: number[], x: number, K: number): number

Defined in evaluate/double/comp-horner-k.ts:34

Returns a result of evaluating a univariate polynomial using K times compensated Horner's method.

• K times compensated means the error in the evaluation is reduced by roughly (1 / Number.EPSILON)**K which is again roughly 2^(53*K) - it is the same as using double-double-.... (K times) precision in a normal Horner evaluation

• see Algorithms for Accurate, Validated and Fast Polynomial Evaluation, Stef Graillat, Philippe Langlois, Nicolas Louvet

• for K-times compensated with K <= 4 this is the fastest known method, but the running time grows exponentially with K.

• see Algorithms for Accurate, Validated and Fast Polynomial Evaluation, Stef Graillat, Philippe Langlois and Nicolas Louvet

• see also Philippe Langlois, Nicolas Louvet. Faithful Polynomial Evaluation with Compensated Horner Algorithm. ARITH18: 18th IEEE International Symposium on Computer Arithmetic, Jun 2007, Montpellier, France. pp.141–149. ffhal-00107222f

• see also Horner's Method

Parameters:

Name	Type	Description
p	number[]	a polynomial with coefficients given densely as an array of double floating point numbers from highest to lowest power, e.g. [5,-3,0] represents the polynomial 5x^2 - 3x
x	number	the value at which to evaluate the polynomial
K	number	(K - 1) === the number of compensations to do

Returns: number