Fast multiple-precision evaluation of elementary functions

34. R. P. Brent, Fast multiple-precision evaluation of elementary functions, J. ACM 23 (1976), 242-251. MR 52#16111.
Preliminary version appeared as Report TR STAN-CS-75-515, Department of Computer Science, Stanford University, August 1975, 22 pp.

Abstract: dvi (3K), pdf (79K).

Paper: pdf (601K).


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


One of the results of this paper is the "Gauss-Legendre" or "Brent-Salamin" algorithm for computing pi. This is the first quadratically convergent algorithm for pi. It was published earlier in [28], and independently by Salamin [Math. Comp. 30 (1976), 565-570]. In a certain sense the algorithm was already known to Gauss in 1809, see Brent [252] for comments and page 99 of Arndt and Haenel for a reproduction of Gauss's unpublished notebook entry of May 1809.

A related paper is [ 32].

Go to next publication

Return to Richard Brent's index page