article

Free access

Fast Multiple-Precision Evaluation of Elementary Functions

Author:

Richard P. BrentAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 2

Pages 242 - 251

https://doi.org/10.1145/321941.321944

Published: 01 April 1976 Publication History

Abstract

Let ƒ(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 ƒ(x) can be evaluated, with relative error Ο(2^-n), in Ο(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 ƒ(x) may be evaluated in Ο(n log²(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.

References

[1]

ABRAMOWITZ, M., AND STEGUN, I.A. Handbook of mathematical functions with formulas, graphs, and mathematical tables. National Bureau of Standards, Washington, D.C., 1964; Dover, 1965, Ch. 17.

[2]

BEELER, M, GOSPEl, R.W, xsv SCHROEPPEL, R Hakmem Memo No. 239, M.I.T. Artfficial Intelligence Lab., M I T., Cambridge, Mass., 1972, pp. 70-71

[3]

BORCHAttDT, C W. Gesammelte Werke. Berlin, 1888, pp. 455-462

[4]

BRENT, R P. The complexity of multiple-precision arithmetic. Proc Seminar on Complexity of Computattonal Problem Solving (held at Austrahan National U., Dec. 1974), Queensland U. Press, Brisbane, Australia 1975, pp 126-165

[5]

BRENT, R P. Multiple-precision zero-finding methods and the complexity of elementary functmn evaluation Proc Symp. on Analytic Computational Complexity, J.F. Traub, Ed, Academm Press, New York, 1976, pp 151-176.

[6]

BRENT, R.P. Computer Solutwn of Nonlinear Equations. Academm Press, New York (to appear), Ch. 6.

[7]

BRENT, R P. A Fortran multiple-precision arithmetic package. Submitted to a technical journal.

[8]

CARLSON, B.C Algorithms involving arithmetic and geometric means. Amer. Math. Monthly 78 (May 1971), 496-505.

[9]

CARLSON, B C. An algorithm for computing logarithms and arctangents. Math. Comput. ~6 (Aprd 1972), 543-549.

[10]

FINKEL, R, GUIBAs, L, AND SIMONYI, C Manuscript in preparation.

[11]

FISCHER, M j, ASB STOCKMEYER, L J Fast on-line integer multiphcation. J. Compu~. System Scis. 9 (Dec. 1974), 317-331

[12]

GAuss, C.F Carl Fmedmch Gauss Werke, Bd. 3 Gottingen, 1876, pp. 362-403.

[13]

GosP~R, R.W. Acceleratton of series. Memo No 304, M.I.T. Artificml Intelligence Lab., M I.T, Cambridge, Mass, 1974.

[14]

GUILLOUV, J., AND BOUYER, M 1,000,000 decimals de pi. Unpublished manuscript

[15]

KNUTH, D.E. The Art of Computer Proqramm~nq, Vol. 2 Addison-Wesley, Reading, Mass, 1969. Errata and addenda: Rep. CS 194, Computer Sci Dep., Stanford U., Stanford, Calif., 1970.

[16]

LAGRANGE, J.L. Oeuvres de Lagrange, Tome $ Gauthmr-Vlllars, Parm, 1868, pp. 267-272.

[17]

LEGENDRE, A.M Exercwes de CalculIntegral, Vol. 1. Paris, 1811, p. 61.

[18]

SALAMIN, E. Computation of ~ using arithmetic-geometric mean. To appear in Math. Comput.

[19]

SCHOSHAGE, A., ASD STRASSEN, V. Schnelle Multiphkation grosset Zahlen. Computing 7 (1971), 281-292.

[20]

SCHROEPPEL, R. Unpubhshed manuscript dated May 1975

[21]

SHAs~:S, D., AND WRENCH, J.W. CMculatmn of v to 100,000 decorums. Ma~h Compug. 16 (1962), 76-99.

[22]

SWEENEY, D W. On the computatmn of Euler's constant Math. Comput. 17 (1963), 170-178.

[23]

THACHER, H.C. iterated square root expansions for the inverse cosine and inverse hyperbolic cosine. Math. Comput. 15 (1961), 399--403.

Cited By

Witkowski OSchwitzgebel E(2024)The Ethics of Life as It Could Be: Do We Have Moral Obligations to Artificial Life?Artificial Life10.1162/artl_a_0043630:2(193-215)Online publication date: 1-May-2024
https://doi.org/10.1162/artl_a_00436
van der Hoeven JJohansson F(2024)Fast multiple precision exp(x) with precomputations2024 IEEE 31st Symposium on Computer Arithmetic (ARITH)10.1109/ARITH61463.2024.00023(80-87)Online publication date: 10-Jun-2024
https://doi.org/10.1109/ARITH61463.2024.00023
Zhu FShuai ZLu YSu HYu RLi XZhao QShuai J(2024)oBABC: A one-dimensional binary artificial bee colony algorithm for binary optimizationSwarm and Evolutionary Computation10.1016/j.swevo.2024.10156787(101567)Online publication date: Jun-2024
https://doi.org/10.1016/j.swevo.2024.101567
Show More Cited By

Index Terms

Fast Multiple-Precision Evaluation of Elementary Functions
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

Recommendations

Integration of elementary functions

We extend a recent algorithm of Trager to a decision procedure for the indefinite integration of elementary functions. We can express the integral as an elementary function or prove that it is not elementary. We show that if the problem of integration ...
Fast Evaluation of the Elementary Functions in Single Precision

In this paper we will introduce a new method for the fast evaluation of the elementary functions in single precision based on the evaluation of truncated Taylor series using a difference method. We assume the availability of large and fast (at least for ...
On multivariate orthogonal polynomials and elementary symmetric functions
Abstract
We study families of multivariate orthogonal polynomials with respect to the symmetric weight function in d variables
$\begin{matrix} B_{γ} (x) = \prod_{i = 1}^{d} ω (x_{i}) \prod_{i < j} {| x_{i} - x_{j} |}^{2 γ + 1}, x \in {(a, b)}^{d}, \end{matrix}$
for $γ > - 1$ , where $ω (t)$ is an univariate weight function in $t \in (a, b)$ and $x = (x_{1}, x_{2}, \dots, x_{d})$ with ... $_{}$ $_{}$ $_{}$ $_{}$ $_{}$ $_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 23, Issue 2

April 1976

176 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321941

Issue’s Table of Contents

Copyright © 1976 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1976

Published in JACM Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

261
Total Citations
View Citations
1,946
Total Downloads

Downloads (Last 12 months)193
Downloads (Last 6 weeks)34

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Witkowski OSchwitzgebel E(2024)The Ethics of Life as It Could Be: Do We Have Moral Obligations to Artificial Life?Artificial Life10.1162/artl_a_0043630:2(193-215)Online publication date: 1-May-2024
https://doi.org/10.1162/artl_a_00436
van der Hoeven JJohansson F(2024)Fast multiple precision exp(x) with precomputations2024 IEEE 31st Symposium on Computer Arithmetic (ARITH)10.1109/ARITH61463.2024.00023(80-87)Online publication date: 10-Jun-2024
https://doi.org/10.1109/ARITH61463.2024.00023
Zhu FShuai ZLu YSu HYu RLi XZhao QShuai J(2024)oBABC: A one-dimensional binary artificial bee colony algorithm for binary optimizationSwarm and Evolutionary Computation10.1016/j.swevo.2024.10156787(101567)Online publication date: Jun-2024
https://doi.org/10.1016/j.swevo.2024.101567
Nam KHwang SLee KZhou J(2024)A Transcendental Number-Based Random Insertion Method for Privacy ProtectionAdvances in Information and Communication10.1007/978-3-031-54053-0_42(637-649)Online publication date: 17-Mar-2024
https://doi.org/10.1007/978-3-031-54053-0_42
Jindal GGaillard L(2023)On the Order of Power Series and the Sum of Square Roots ProblemProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597079(354-362)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597079
Kauers MNuspl PPillwein V(2023)Order bounds for C2-finite sequencesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597070(389-397)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597070
Nguyen LSigg SLietzen JFindling RRuttik K(2023)Camouflage Learning: Feature Value Obscuring Ambient Intelligence for Constrained DevicesIEEE Transactions on Mobile Computing10.1109/TMC.2021.309227122:2(781-796)Online publication date: 1-Feb-2023
https://doi.org/10.1109/TMC.2021.3092271
Dong RMelczer SMezzarobba M(2023)Computing error bounds for asymptotic expansions of regular P-recursive sequencesMathematics of Computation10.1090/mcom/388893:346(977-1017)Online publication date: 16-Aug-2023
https://doi.org/10.1090/mcom/3888
van der Hoeven J(2023)Fuchsian holonomic sequencesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-023-00616-4Online publication date: 24-Sep-2023
https://doi.org/10.1007/s00200-023-00616-4
Doctor TWitkowski OSolomonova EDuane BLevin M(2022)Biology, Buddhism, and AI: Care as the Driver of IntelligenceEntropy10.3390/e2405071024:5(710)Online publication date: 16-May-2022
https://doi.org/10.3390/e24050710
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents