Fast Multiple-Precision Evaluation of Elementary Functions

Journal of the ACM - Tập 23 Số 2 - Trang 242-251 - 1976
Richard P. Brent1
1Computer Centre, Australian National University, Box 4, Canberra, ACT 2600, Australia

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

ABRAMOWITZ M., 1964, Handbook of mathematical functions with formulas, graphs, and mathematical tables

BEELER M, 1972, R Hakmem Memo No. 239, M.I.T. Artfficial Intelligence Lab., M I T., 70

BORCHA DT, Gesammelte Werke. Berlin, 1888, 455

BRENT R P, 1974, Dec., 126

BRENT R P, 1976, J.F. Traub, Ed, 151

BRENT R.P., Computer Solutwn of Nonlinear Equations

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

CARLSON B.C, 1971, Algorithms involving arithmetic and geometric means, Amer. Math. Monthly, 78, 496, 10.1080/00029890.1971.11992791

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

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

FISCHER, 1974, Fast on-line integer multiphcation, J. Compu~. System Scis., 9, 317, 10.1016/S0022-0000(74)80047-4

GA, 1876, Bd., 3, 362

P~R R.W., 1974, M.I.T. Artificml Intelligence Lab.

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

KNUTH D.E., 1969, The Art of Computer Proqramm~nq

LAGRANGE J.L., 1868, Parm, 267

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

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

SCHOSHAGE A., 1971, Schnelle Multiphkation grosset Zahlen, Computing, 7, 281, 10.1007/BF02242355

SCHROEPPEL R., 1975, Unpubhshed manuscript dated

SHA, 1962, S, D., AND WRENCH, J.W. CMculatmn of v to 100,000 decorums, Ma~h Compug., 16, 76

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

THACHER H.C, 1961, iterated square root expansions for the inverse cosine and inverse hyperbolic cosine, Math. Comput., 15, 399, 10.1090/S0025-5718-1961-0135228-5

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 23 Số 2

242-251

Thông tin tác giả