Multiple-precision zero-finding methods and the complexity of elementary function evaluation

Understand

We consider methods for finding high-precision approximations to simple zeros of smooth functions.

• As an application, we give 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)lg(n), where M(n) is the time required to multiply floating-point numbers with n-bit fractions.