MULTIPLE-PRECISION ZERO-FINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATION

RICHARD P. BRENT

Abstract

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) log_{2} n as n → ∞, 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.

Comments

Only the Abstract is given here. The full paper appeared as [3]. This paper gives the quadratically convergent “Gauss-Legendre” algorithm [2] for the computation of π (discovered independently by Salamin [6]), and gives algorithms for computing elementary functions which are simpler and faster than those of [5]. It also gives a fast algorithm for computing the first n terms in an arbitrary power F (x)^{q} of a formal power series F (x) in one variable. A related paper (written earlier) is [4].

Errata

Page 152, line −10: replace “performe” by “perform”. Page 172, line 7: replace “β_{i}” by “β”.

1991 Mathematics Subject Classification. Primary 65D20, 65Y20; Secondary 15F25, 33B10, 33E05, 41A25, 68Q25.

Key words and phrases. Analytic complexity, arithmetic-geometric mean, computational complexity, elementary function, elliptic integral, evaluation of π, exponential, Landen transformation, logarithm, multiple-precision arithmetic, trigonometric function.

CR Categories. 5.12, 5.15, 5.25.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1976, Academic Press.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1999, R. P. Brent. rpb028a typeset using AMS-L^{A}TEX.

References

[1] R. S. Anderssen and R. P. Brent (editors), The Complexity of Computational Problem Solving, University of Queensland Press, Brisbane, 1976, 262 pp. LC 76-374278, ISBN 0-7022-1213-X. rpb031.

[2] J. M. Borwein and P. B. Borwein, Pi and the AGM, John Wiley and Sons, New York, 1987.

[3] R. P. Brent, “Multiple-precision zero-finding methods and the complexity of elementary function evaluation”, in Analytic Computational Complexity (edited by J. F. Traub), Academic Press, New York, 1975, 151–176. MR 52#15938, 54#11843; Zbl 342.65031. Retyped in L^{A}TEX, Oxford, 1999. Also appeared as a Technical Report, Department of Computer Science, Carnegie-Mellon University (July 1975), 26 pp. rpb028.

[4] R. P. Brent, “The complexity of multiple-precision arithmetic”, in [1, 126–165]. rpb032.

[5] R. P. Brent, “Fast multiple-precision evaluation of elementary functions”, J. ACM 23 (1976), 242–251. MR 52#16111, Zbl 324.65018. Also appeared as Report TR STAN-CS-75-515, Department of Computer Science, Stanford University (August 1975), 22 pp. rpb034.

[6] E. Salamin, “Computation of π using arithmetic-geometric mean”, Mathematics of Computation 30, 1976, 565–570.

Computer Centre, Australian National University, Canberra