Favati P., Lotti G., Menchi O., Romani F. Separable Asymptotic Cost of Evaluating Elementary Functions. Technical report, 1996. |

Abstract (English) |
The asymptotic computational cost of evaluating a real function $f(x)$ in a point $x$, in the bit model of computation, is analyzed, with $x$ varying in an interval containing also critical points for the function $f$. We find an upper bound to the cost as a function of two variables: the number $d$ of correct digits in the result and the point $x$. More precisely we study a class of algorithms for which it is possible to give upper bounds on the cost as functions of 'separated variables' $d$ and $x$, that is as products of two functions, each of one variable. We find conditions under which elementary functions can be computed through algorithms belonging to this class. | |

Subject | G.1.0 General 65Y20 Complexity and performance of numerical algorithms |

Open access Restricted Private