Multiple-Precision Zero-Finding Methods and the Complexity of Elementary Function Evaluation
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1975
- Accession Number
- ADA014059
Entities
People
- Richard P. Brent
Organizations
- Carnegie Mellon University