Evaluating a constant expression in multiple precision with a guaranteed error bound
Résumé
The evaluation of special functions often involves the evaluation of numerical constants. When the precision of the evaluation is known in advance (e.g., when developing libms) these constants are simply precomputed once for a while. In contrast, when the precision is dynamically chosen by the user (e.g., in multiple precision libraries), the constants must be evaluated on the fly at the required precision and with a rigorous error bound. Often, such constants are easily obtained by means of formulas involving simple numbers and functions. In principle, it is not a difficult work to write multiple precision code for evaluating such formulas with a rigorous roundoff analysis: one only has to study how roundoff errors propagate through subexpressions. However, this work is painful and error-prone and it is difficult for a human being to be perfectly rigorous in this process. Moreover, the task quickly becomes impractical when the size of the formula grows. In this article, we present an algorithm that takes as input a constant formula and that automatically produces code for evaluating it in arbitrary precision with a rigorous error bound. It has been implemented in the Sollya free software tool and its behavior is illustrated on several examples.
L'évaluation de fonction spéciales nécessite souvent d'évaluer certaines constantes. Lorsque la précision est connue à l'avance (par exemple, lorsqu'on développe une libm), ces constantes sont simplement précalculées une fois pour toutes. Mais lorsque la précision est fixée par l'utilisateur au moment de l'évaluation (comme c'est le cas pour les bibliothèques en précision arbitraire), les constantes doivent être évaluées à la volée à la précision demandée et en bornant rigoureusement les erreurs. Souvent, ce genre de constantes est donné par des formules faisant intervenir des fonctions simples et des entiers. En principe, écrire du code en précision arbitraire pour évaluer ce genre de formule avec une analyse rigoureuse des erreurs d'arrondi n'est pas une tâche difficile. Il suffit d'étudier comment les erreurs d'arrondi se propagent à travers les sous-expressions. Cependant, ce travail est ingrat, délicat, et il est difficile pour un être humain de rester parfaitement rigoureux. De plus, la tâche devient vite inabordable lorsque la formule grossit. Dans cet article, nous présentons un algorithme qui prend en entrée une formule constante et qui produit automatiquement du code pour l'évaluer en précision arbitraire et avec une borne d'erreur rigoureuse. Nous l'avons implémenté de façon expérimentale dans l'outil libre Sollya, et nous illustrons son comportement sur plusieurs exemples.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...