Fast Multiple-Precision Evaluation of Elementary Functions

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 &Ogr;(2-n), in &Ogr;(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 &Ogr;(n log2(n) log log(n)) operations. Special cases include the evaluation of constants such as &pgr;, e, and e&pgr;. The algorithms depend on the theory of elliptic integrals, using the arithmetic-geometric mean iteration and ascending Landen transformations.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: Michael Beeler , R. W Gosper , Rich Schroeppel, HAKMEM, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 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: Richard P. Brent, A Fortran Multiple-Precision Arithmetic Package, ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.57-70, March 1978 [doi>10.1145/355769.355775]
• 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: William Gosper, Acceleration of Series, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 14: GUILLOUV, J., AND BOUYER, M 1,000,000 decimals de pi. Unpublished manuscript
• 15: Donald E. Knuth, The state of the Art of Computer Programming, Stanford University, Stanford, CA, 1976
• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

General Terms:
Algorithms, Measurement, Performance, Theory, Verification