Multiple-Precision Zero-Finding Methods and the Complexity of Elementary Function Evaluation.

摘要

The author considers methods for finding high-precision approximations to simple zeros of smooth functions. As an application, the author gives fast methods for evaluating the elementary functions log(x), exp(x), sin(x) etc. to high precision. For example, if x is a positive floating-point number with an n-bit fraction, then (under rather weak assumptions) an n-bit approximation to log(x) or exp(x) may be computed in time asymptotically equal to 13M(n) log of n to the base 2 as n approaches infinity, where M(n) is the time required to multiply floating-point numbers with n-bit fractions. Similar results are given for the other elementary functions, and some analogies with operations on formal power series are mentioned.