##
``Computing by the Numbers: Algorithms, Precision, and Complexity''

##
Workshop in Celebration of Richard Brent's 60th Birthday

###
July 20-21, 2006

Weierstrass Institute for Applied Analysis and Stochastics, Berlin.

#### TALK TITLE:

Complexity of Real Approximation: Brent Revisited

Chee Yap, Courant Institute and KIAS

#### ABSTRACT

Multiprecision computation is of growing importance,
both theoretically as well as practically.
It is an integral part of the foundation of a
theory of numerical and scientific computation.
Over 30 years ago, Brent showed through
a series of papers the efficiency of multiprecision arithmetic
for a large class of fundamental numerical functions.
His complexity bounds have remain unsurpassed today.
These results were formulated in an abstract model
using three axioms.
We re-examine these axioms from
the viewpoint of a general model of numerical approximations.
This leads to a number of issues:
- (1) Local versus global versus uniform complexity
- (2) Turing machine versus Sch\"onhage's pointer machines
- (3) Weak Mode versus Strong Mode of multiprecision computation
- (4) Asymptotic versus non-asymptotic error analysis
- (5) Exact versus inexact operations
- (6) Zero problems

We illustrate these issues with several
recent results. Such results suggests
that much ground work remains to be done in building
a complexity theory of multiprecision computation.