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

Sylvie Boldo 1 Marc Daumas
1 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Polynomials are used in many applications and hidden in libraries such as libm. Whereas the accuracy of the functions used by linear algebra have long been studied, little is available to decide on one scheme to evaluate a polynomial. Common knowledge solely emphasizes that Horner's rule is a good scheme unless the indeterminate is close to one of the polynomial's roots. We propose here a criterion for one step of Horner's scheme to be faithful. A result is defined to be faithful when it was correctly rounded whereas the rounding mode (up, down or to the nearest) cannot be known by the user. Our criterion is checked against the IEEE standard for floating point arithmetic using the Coq automatic proof checker. We then present three programs in Maple, Java and C that check the criterion for a whole polynomial associated with a domain for the indeterminate and a possible truncation error. An example of use is given with the approximation of elementary functions.
Type de document :
Article dans une revue
Numerical Algorithms, Springer Verlag, 2004, 37 (1-4), pp.45-60. 〈10.1023/B:NUMA.0000049487.98618.61〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 19:04:34
Dernière modification le : vendredi 20 avril 2018 - 15:44:23
Document(s) archivé(s) le : dimanche 4 avril 2010 - 20:50:02





Sylvie Boldo, Marc Daumas. A simple test qualifying the accuracy of Horner's rule for polynomials. Numerical Algorithms, Springer Verlag, 2004, 37 (1-4), pp.45-60. 〈10.1023/B:NUMA.0000049487.98618.61〉. 〈inria-00071879〉



Consultations de la notice


Téléchargements de fichiers