A simple test qualifying the accuracy of Horner's rule for polynomials (Q2387741)

The authors consider the problem of evaluating a polynomial with floating point arithmetic. An evaluation scheme is defined to be faithful if it returns either the rounded up or the rounded down value of the exact result. Faithful rounding is shown to be more accurate than bounding the number of units in the last place of the error. The main results of the paper propose tight sufficient conditions to guarantee faithful rounding on one step of Horner's scheme. The conditions are validated with the IEEE standard for floating point arithmetic using the Coq automatic proof checker. Three programs in Maple, Java and C are also presented that compute an upper bound and an absolute error bound on an arbitrary polynomial and an arbitrary domain for the indeterminate. Subject to a certain criterion, the programs guarantee faithful evaluation, as illustrated by two examples.