## 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).

## Abstract

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

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