FAST MULTIPLE-PRECISION EVALUATION OF ELEMENTARY FUNCTIONS

RICHARD P. BRENT

Abstract

Let f(x) be one of the usual elementary functions (exp, log, artan, sin, cosh, etc.), and let M(n) be the number of single-precision operations required to multiply n-bit integers. It is shown that f(x) can be evaluated, with relative error O(2^{−n}), in O(M(n) log(n)) operations as n → ∞, for any floating-point number x (with an n-bit fraction) in a suitable finite interval. From the Schönhage-Strassen bound on M(n), it follows that an n-bit approximation to f(x) may be evaluated in O(n log^{2}(n) log log(n)) operations. Special cases include the evaluation of constants such as π, e, and e^{π}. The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric mean iteration and ascending Landen transformations.

Comments

Only the Abstract is given here. The full paper appeared as [5]. For related work see [1, 2, 4].

References

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

2. 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. Also appeared as a Technical Report, Department of Computer Science, Carnegie-Mellon University (July 1975), 26 pp. rpb028.

3. 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.

4. R. P. Brent, “The complexity of multiple-precision arithmetic”, in [3, 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.

Computer Centre, Australian National University, Canberra, Australia

1991 Mathematics Subject Classification. Primary 65D20, 65Y20; Secondary 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, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM’s copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb034a typeset using AMS-L^{A}TEX