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