## 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_{2}*n*,
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 + *a*_{1}*x* + ...)
or exp(*a*_{1}*x* + ...)
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 + *a*_{1}*x* +
...)^{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