COLLECTED BY
Organization:
National Library of Australia Crawls
Crawls performed by Internet Archive on behalf of the National Library of Australia. This data is currently not publicly accessible.
Domain harvest of the Australian web domain (.au) performed by Internet Archive on behalf of the National Library of Australia in 2008. This data is currently not publicly accessible.
The Wayback Machine - https://web.archive.org/web/20080723170157/http://wwwmaths.anu.edu.au/~brent/pub/pub028.html
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.
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].
Related papers (written earlier but published later) are Brent
[32,
34].
Go to next publication
Return to Richard Brent's index page
