Name

chorner — evaluate a polynomial represented by an array of double using the compensated Horner scheme of Graillat, Langlois, and Louvet [1], or double complex using the scheme of Graillat and Ménissier-Morain [2].

Synopsis

#include <chorner.h>
extern double crhorner( const double * p,
  size_t n,
  double x);
 
extern double complex cchorner( const double complex * p,
  size_t n,
  double complex x);
 

DESCRIPTION

The crhorner function evalatutes the (real) polynomial p, represented as by an n-array of doubles at the value x. The coefficient of the constant term is at index 0, of the linear term at index 1 and so on (so this is opposite to the common and strange Matlab representation). Note that the polynomial is of order n−1.

The cchorner function evaluates a complex polynomial.

The compensated Horner scheme takes account of, and corrects for, the cancellation errors which occur in the uncompensated Horner scheme. The result is an accuracy which is the same as if one had used a Horner scheme with 128-bit (quadruple precision) floating point arithmetic and rounded the result down to 64-bit (double precision), but at much lower computational cost.

The algorithm depends crucially on the structure of IEEE 754 floating point arithmentic and an error will be raised if the macro __STDC_IEC_559 indicating its presence is not defined at compilation.

RETURN VALUE

The estimate of p(x), as a double (crhorner) or double complex (cchorner). In the case that n is zero, zero will be returned.

AUTHORS

J.J. Green, from the algorithm described in [1] and [2].

Bibliography

[1] S. Graillat, Ph. Langlois, and N. Louvet. Compensated Horner Scheme. Université de Perpignan Via Domitia. RR2005-04.

[2] S. Graillat and Valérie Ménissier-Morain. Compensated Horner scheme in complex floating point arithmetic. Proceedings of the 8th Conference on Real Numbers and Computers, Santiago de Compostela, Spain, July 7–9, 2008. 133–146.