Fast Multiple-Precision Evaluation of Elementary Functions
Open Access
- 1 April 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (2) , 242-251
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 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.Keywords
This publication has 6 references indexed in Scilit:
- MULTIPLE-PRECISION ZERO-FINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATION1976
- Fast on-line integer multiplicationJournal of Computer and System Sciences, 1974
- An algorithm for computing logarithms and arctangentsMathematics of Computation, 1972
- Schnelle Multiplikation großer ZahlenComputing, 1971
- Algorithms Involving Arithmetic and Geometric MeansThe American Mathematical Monthly, 1971
- Iterated square root expansions for the inverse cosine and inverse hyperbolic cosineMathematics of Computation, 1961