TEN DIGIT ALGORITHMS
Lloyd N. Trefethen
1. INTRODUCTION
For twenty-five years I have been developing numerical
algorithms, teaching numerical analysis courses, and helping people solve
numerical problems at Stanford, NYU, MIT, Cornell, and
Over the years perhaps a thousand people have come to
me for numerical advice. On half of these
occasions, inevitably, I have little to contribute. As for the other half, however, it is
remarkable how often the customer and I end up sitting down at the computer
together and getting good numbers at surprisingly high speed. That experience motivates this essay. So does my experience in teaching. Since arriving at
A view has come into focus for me of a kind of
computing which I summarize by the notion of a “ten digit algorithm”. I believe that ten digit algorithms can be useful
for education, for communication, and for research. Many of the programs I’ve written in recent
years are in this mode, and if you spend your time computing with numbers, I
urge you too to make ten digit algorithms a part of your operating practice.
2. THE
DEFINITION
Ten digits,
Five seconds,
And just one page.
A ten digit algorithm is a little gem of a program to
compute something numerical. The jingle summarizes
the three defining conditions. The
program can be at most one page long, and it has to solve your problem to at
least ten digits of accuracy on your machine in less than five seconds.
For me, the programs are usually in MATLAB, but this
is not part of the definition. Maple and
Mathematica, for example, are impressive alternatives.
Strictly speaking, the term “ten digit program” might be
more correct. I chose “algorithm”
because it is more interesting and serves as a reminder that although all
aspects of a code are important, the preeminent one is the underlying numerical
method.
Of course, the three conditions are artificial, at
least in their precise formulation if not in their general idea. But I do not think this must count against
them. After all, the net in tennis is
artificial, as are the days of the week and the convention that a sonnet has 14
lines. Nevertheless, such constraints
can guide our activities in fruitful ways.
3. WHY FIVE SECONDS?
In computing with humans, response time is
everything. If a program runs in less
than five seconds, its author will effortlessly adjust, improve, and experiment. The process of scientific exploration becomes
interactive and pleasurable. If the program
runs for a minute or an hour, on the other hand, it is a very different
situation from the human point of view.
Of course, for some problems that’s unavoidable, but one’s likelihood of
getting the science right falls quickly as one loses the ability to steer the computation
on a human time scale. I’ve seen this
over and over again. Visitors to my
office who can’t run their programs fast often get numbers they aren’t sure of,
and numbers you aren’t sure of are often wrong.
Many people believe that only “toy” problems can be
solved in five seconds. Indeed, this is
the more or less universal objection I encounter when I first tell people about
ten digit algorithms. But I think it is
mistaken. Of course, there are many
large-scale computations that will eventually have to be carried out in
“production mode”, but the fact is, that is just a small part of the story of
how numerical programmers can and should spend their time. First of all, many computational problems can
be solved without any of that kind of computing. Secondly, even if production mode will be
needed for the final results, it does not follow that the programmer doing the
development should spend most of his or her development hours in this
mode. I’ve seen vast amounts of time
wasted in that fashion.
We can put it this way. Maybe 90% or even 99% of numerical machine
cycles are destined to be spent in big production runs. From the programmer’s point of view,
nevertheless, 90% of the jobs that get run should be quick ones.
Five seconds is not an absolute criterion; its
significance changes as machines advance.
This is intentional. Computing is
a human activity, and the point is to keep humans in the loop.
4. WHY ONE
PAGE?
Again it’s a matter of linking to people. A code less than a page long can be read and
studied. I am convinced that for a good fraction
of problems, studying the code is feasible and valuable. And of course, a code that you study is one
that you polish and perfect. Print out a
copy, step away from your computer, and grab a red pen! The moment the listing spills onto page 2,
the chance that you will look at it carefully cuts in half.
The matter of communication is overwhelmingly
important. It is often said that there
are three kinds of science: theory, experiment, and computation. Analogously, there are four kinds of scientific
communication: words, figures, mathematics, and programs. If you rely on the first three alone, you are
handicapped. For communicating algorithmic
ideas, nothing can touch a short program in its precision and conciseness. If you are like me, you have wasted
exasperating hours studying journal articles, trying to figure out exactly how
the author’s algorithm works and what parameter choices he or she prefers, when
a short code would have answered these questions immediately. Code segments appear in rather few journal
articles these days, and this is a trend that I hope we can persuade publishers
to reverse.
Like “five seconds”, “one page” is not an absolute
criterion; its significance varies with the programming language. The development of high-level languages like
MATLAB has enabled us to do more than was possible with Fortran or C. Thanks to these high-level languages, there
is not much need any more to communicate with the old tools of flow charts and
pseudocodes. We can use the executable
language directly.
5. WHY TEN
DIGITS?
The reasoning here is different. It’s a matter of linking not to humans, but
to the physical world.
To oversimplify a bit, there are two kinds of
accuracy. Engineering accuracy means two
or three digits. This is generally ample
for the end user like the designer of a bridge or an airplane or a medical
trial or an evaluation scheme for pricing financial options. Getting more than two or three digits for end-user
applications will typically be impossible, because the problem is too complex,
and meaningless, since it is not defined precisely enough.
Scientific accuracy, by contrast, means five or ten
digits. This is what one aims for in
solving fundamental problems upon which other ideas or computations will be
built. For example, the flow of air over
a Boeing 767 is an engineering application, but the flow through an infinite
idealized circular pipe is a scientific application. Computing the natural frequencies of a symphony
orchestra kettledrum is an engineering problem, but computing the eigenvalues of
an L-shaped region is scientific. One’s
expectations can and should be different.
In physics, almost nothing is known to more than 10
digits. We know the gravitational
constant to about 5 digits, Planck’s constant to about 7, the speed of light to
8 or 9. These precisions are not increasing
very fast. In twenty years our computers
will be a million times more powerful, but physics will still not know much to
more than 10 digits.
Ten digits is very different from three in the type of
thinking and algorithms it forces upon you.
To get ten digits of accuracy in five seconds of computing, you have to
have really “nailed” your problem, and in particular, to have worked around any
singularities it may have. It’s a
challenging and exciting type of computing.
6. CHALLENGE
AND ENJOYMENT
This brings me to a key feature of ten digit
algorithms. Ten digits, five seconds,
one page — this is a challenge! By
struggling to meet the challenge, we sharpen and improve our ideas and our
codes. This is the best possible route
to understanding a problem, and besides, it’s fun. Computing is one of the highest creative
activities that humans indulge in, and it should be fun. How else to induce people to engage their
imaginations at the highest level?
7. MUST A TEN
DIGIT ALGORITHM BE EASILY READABLE?
The one-page restriction is designed to encourage gems
of programming, and one would hope that a ten digit algorithm will be as clear
and easy to read as possible. Certainly
one hopes for attractive structure and for useful, well laid-out comments. Nevertheless, readability is not one of the
defining conditions of a ten digit algorithm, for in the end, power is more
important. Think of the analogy of
poetry. Poems are gems of verbal
expression. Some can be read and
appreciated instantly, and that is a wonderful thing. Nevertheless, nobody would say that immediate
accessibility is a requirement of a good poem.
On the contrary, what matters is that it repay repeated reading and
reflection.
8. SCRIPTS AND
SUBROUTINES
Ultimately your program may be turned into a software
tool or a production code. We are
concerned here not with that stage, but with the earlier phases of development
and exploration.
There’s a simple principle that makes a big difference
to your productivity, and it surprises me how many people don’t use it. The principle (expressed here in MATLAB
terminology) is, when developing a numerical code, always drive your
computation through a script. Give it a
short name like p49.m or stokes.m and keep a window on your screen with this file
open for editing. To run it, you just
type “p49” or “stokes”. Everything you
need, such as plotting commands, will be in this program, and any detail can be
quickly changed without the need for retyping the rest. Don’t work at the command line!
Of course your code will often be a ten digit algorithm,
so you can see most of it at once on the screen and run it over and over again
quickly, improving it at every step. And
you can test and test and vary and plot and test and test again. When things go wrong, you have immediate
access to all the variables in your workspace.
Functions and subroutines are powerful and
important. But these are for operations
you’ve finished debugging, black boxes, not for development work.
9. ACADEMIC
NUMERICAL ANALYSIS
Years ago, numerical analysts were the main people
trained to solve numerical problems on computers. Indeed, there was a time when anyone at
Imagine if the medical establishment had only
specialists, no general practitioners! I
don’t recommend the creation of a new class of GP numerical analysts, but it
would be a good thing for our field if each of us developed our “GP side” a
little further. If ten digit algorithms
become a familiar signpost, they will encourage that kind of breadth.
10. PROOFS AND
“ENGINEERING PROOFS”
Roughly speaking, numerical analysts like to establish
correctness of a computation by a theorem, whereas practitioners like to do it
by numerical tests such as varying parameters to confirm that the computed
answer doesn’t change. There is no doubt
that ten digit algorithms have a natural link to this second kind of
correctness test, thanks to the five-second condition. When a program runs fast, you will inevitably
run it in various modes and with various parameter choices. It would be a sloppy person indeed who did
not examine the performance of a ten digit algorithm from so many angles as to acquire
good confidence in its correctness. By
contrast, even a careful programmer will find it daunting to test a program
that runs for hours.
My view is that all people doing numerical computations,
including numerical analysts, should routinely perform this kind of
testing. In other words, though there is
a place for the theorist who doesn’t compute, there is no place for a computing
person who doesn’t check his or her results. This is a sine qua non. In addition, since numerical analysis is a
branch of mathematics, we can also have recourse to theorems, and the best
algorithms will be developed in the light of both practice and theory.
Most ten digit algorithms will contain parameters that
have been tuned. One might decide to use
a grid spacing of 1/150 since 1/100 is not good enough, or 60 terms in a series
expansion because 50 will not do. The testing that leads to such parameter
choices will have been done by the programmer in the course of developing the
program, and that is fine. By the time
you show anybody your t.d.a., you will have run it a hundred times in various
forms. Thus there is no requirement that
the final ten digit algorithm must explore dependence on parameters or
demonstrate that ten digits have been achieved, though in many cases, where
time and space permit, you may choose to include such features.
11. NUMERICAL
ANALYSIS AND APPLIED MATHEMATICS
One of the core methodologies of applied mathematics
is asymptotic analysis, a tool that springs from the observation that in many
scientific problems, the important phenomena are dominated by a nearby
singularity. By understanding the
singular behaviour, one may solve the problem to sufficient accuracy, and even
more important, one may understand the scientific essence of the matter.
Much of numerical analysis has taken more or less the opposite
line: singularities and asymptotics are fine in their place, but it is our
business to design general tools that do not depend on special features of the
problem at hand.
I think ten digit algorithms can help to build a bridge
between these two outstandingly successful traditions. Very often, a certain kind of method proves effective
for ten digit algorithms. This is:
eliminate the singularities, then do something relatively simple for the rest
of the problem, e.g. involving a least-squares fit with some free expansion
parameters. For conformally mapping a
polygon, for example, you don’t always need the Schwarz-Christoffel formula;
sometimes you can “roll your own” elementary solution that’s equally effective
(see trapmap). Other
t.d.a.’s in this booklet that fit this pattern include two_disks, many_disks, and jaisson.
12. IN
CONCLUSION
Ten digit algorithms can
· Improve our publications
· Speed up program development
· Make our numerical methods faster
· Make our scientific results more
reliable
· Facilitate comparisons of ideas and
results
· Add focus to the classroom
· Add zest to our field
The challenge of designing these codes raises our
standards and raises our expectations. It’s
good for the academics, and it opens the doors wider to non-academics. And it’s fun!
The attached examples, 32 M-files from various areas I
have been interested in, range from little demonstrators of routine ideas to advanced
programs that can compete with any others in their particular domains. They can be downloaded from my web page at