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)log
2n,
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