Multiple-precision zero-finding methods and the complexity
of elementary function evaluation
28. R. P. Brent,
Multiple-precision zero-finding methods and the complexity
of elementary function evaluation,
in Analytic Computational Complexity
(edited by J. F. Traub),
Academic Press, New York, 1975, 151-176.
MR 52#15938, 54#11843.
Retyped and postscript added 1999.
arXiv:1004.3412v2
Abstract:
dvi (4K),
pdf (87K),
ps (30K),
Paper:
dvi (28K),
pdf (208K),
ps (93K).
Abstract
We consider methods for finding high-precision approximations to
simple zeros of smooth functions. As an application, we give fast
methods for evaluating the elementary functions
log(x), exp(x),
sin(x) etc. to high precision.
For example, if x is a positive
floating-point number with an n-bit fraction, then (under rather
weak assumptions) an n-bit approximation to
log(x) or exp(x)
may be computed
in time
asymptotically equal to 13M(n)log2n,
where M(n) is the time required to multiply
floating-point numbers with n-bit fractions.
Similar results are
given for the other elementary functions.
Some analogies with operations on formal power series (over a field
of characteristic zero) are discussed.
In particular, it is possible to compute the first n terms in
log(1 + a1x + ...)
or exp(a1x + ...)
in time O(M(n)),
where M(n) is the time required to multiply two
polynomials of degree n - 1.
It follows that the first n terms in
a q-th power
(1 + a1x +
...)q
can be computed in time O(M(n)), independent of
q.
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 also published in
[34], 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.
Related papers (written earlier but published later) are Brent
[32,
34].
Go to next publication
Return to Richard Brent's index page