About Standard Numerics (was Re: 4 hundred quadrillonth?)
Lawrence D'Oliveiro
ldo at geek-central.gen.new_zealand
Mon May 25 03:39:02 CEST 2009
In message <9MWdnTfMPPrjQoTXnZ2dnUVZ_vadnZ2d at giganews.com>, Erik Max Francis
wrote:
> Lawrence D'Oliveiro wrote:
>
>> In message <mailman.525.1242941777.8015.python-list at python.org>,
>> Christian Heimes wrote:
>>
>>> Welcome to IEEE 754 floating point land! :)
>>
>> It used to be worse in the days before IEEE 754 became widespread.
>> Anybody remember a certain Prof William Kahan from Berkeley, and the
>> foreword he wrote to the Apple Numerics Manual, 2nd Edition, published in
>> 1988? It's such a classic piece that I think it should be posted
>> somewhere...
>
> I only see used versions of it available for purchase. Care to hum a
> few bars?
Part I of this book is mainly for people who perform scientific,
statistical, or engineering computations on Apple® computers. The rest is
mainly for producers of software, especially of language processors, that
people will use on Apple computers to perform computations in those fields
and in finance and business too. Moreover, if the first edition was any
indication, people who have nothing to do with Apple computers may well buy
this book just to learn a little about an arcane subject, floating-point
arithmetic on computers, and will wish they had an Apple.
Computer arithmetic has two properties that add to its mystery:
* What you see is often not what you get, and
* What you get is sometimes not what you wanted.
Floating-point arithmetic, the kind computers use for protracted work with
approximate data, is intrinsically approximate because the alternative,
exact arithmetic, could take longer than most people are willing to wait--
perhaps forever. Approximate results are customarily displayed or printed to
show only as many of their leading digits as matter instead of all digits;
what you see need not be exactly what you've got. To complicate matters,
whatever digits you see are /decimal/ digits, the kind you saw first in
school and the kind used in hand-held calculators. Nowadays almost no
computers perform their arithmetic with decimal digits; most of them use
/binary/, which is mathematically better than decimal where they differ, but
different nonetheless. So, unless you have a small integer, what you see is
rarely just what you have.
In the mid 1960's, computer architects discovered shortcuts that made
arithmetic run faster at the cost of what they reckoned to be a slight
increase in the level of rounding error; they thought you could not object
to slight alterations in the rightmost digits of numbers since you could not
see those digits anyway. They had the best intentions, but they accomplished
the opposite of what they intended. Computer throughputs were not improved
perceptibly by those shortcuts, but a few programs that had previously been
trusted unreservedly turned treacherous, failing in mysterious ways on
extremely rare occasions.
For instance, a very Important Bunch of Machines launched in 1964 were found
to have two anomalies in their double-precision arithmetic (though not in
single): First, multiplying a number /Z/ by 1.0 would lop off /Z/'s last
digit. Second, the difference between two nearly equal numbers, whose digits
mostly canceled, could be computed wrong by a factor almost as big as 16
instead of being computed exactly as is normal. The anomalies introduced a
kind of noise in the feedback loops by which some programs had compensated
for their own rounding errors, so those programs lost their high accuracies.
These anomalies were not "bugs"; they were "features" designed into the
arithmetic by designers who thought nobody would care. Customers did care;
the arithmetic was redesigned and repairs were retrofitted in 1967.
Not all Capriciously Designed Computer arithmetics have been repaired. One
family of computers has enjoyed notoriety for two decades by allowing
programs to generate tiny "partially underflowed" numbers. When one of these
creatures turns up as the value of /T/ in an otherwise innocuous statement
like
if T = 0.0 then Q := 0.0 else Q := 702345.6 / (T + 0.00189 / T);
it causes the computer to stop execution and emit a message alleging
"Division by Zero". The machine's schizophrenic attitude toward zero comes
about because the test for T = 0.0 is carried out by the adder, which
examines at least 13 of /T/'s leading digits, whereas the divider and
multiplier examine only 12 to recognize zero. Doing so saved less than a
dollar's worth of transistors and maybe a picosecond of time, but at the
cost of some disagreement about whether a very tiny number /T/ is zero or
not. Fortunately, the divider agrees with the multiplier about whether /T/
is zero, so programmers could prevent spurious divisions by zero by slightly
altering the foregoing statement as follows:
if 1.0 * T = 0.0 then Q := 0.0 else Q := 702345.6 / (T + 0.00189 / T);
Unfortunately, the Same Computer designer responsible for "partial
underflow" designed another machine that can generate "partially
underflowed" numbers /T/ for which this statement malfunctions. On that
machine, /Q/ would be computed unexceptionably except that the product 1.0 *
T causes the machine to stop and emit a message alleging "Overflow". How
should a programmer rewrite that innocuous statement so that it will work
correctly on both machines? We should be thankful that such a task is not
encountered every day.
Anomalies related to roundoff are extremely difficult to diagnose. For
instance, the machine on which 1.0 * T can overflow also divides in a
peculiar way that causes quotients like 240.0 / 80.0, which ought to produce
small integers, sometimes to produce nonintegers instead, sometimes slightly
too big, sometimes slightly too small. The same machine multiplies in a
peculiar way, and it subtracts in a peculiar way that can get the difference
wrong by almost a factor of 2 when it ought to be exact because of
cancellation.
Another peculiar kind of subtraction, but different, afflicts the machines
that are schizophrenic about zero. Sets of three values /X/, /Y/ and /Z/
abound for which the statement
if (X = Y) and ((X - Z) > (Y - Z)) then writeln('Strange!');
will print "Strange!" on those machines. And many machines will print
"Strange!" for unlucky values /X/ and /Y/ in the statement
if (X - Y = 0.0) and (X > Y) then writeln('Strange!');
because of underflow.
/These strange things cannot happen on current Apple computers./
I do not wish to suggest that all but Apple computers have had quirky
arithmetics. A few other computer companies, some Highly Prestigious, have
Demonstrated Exemplary Concern for arithmetic integrity over many years. Had
their concern been shared more widely, numerical computation would now be
easier to understand. Instead, because so many computers in the 1960's and
1970's possessed so many different arithmetic anomalies, computational lore
has become encumbered with a vast body of superstition purporting to cope
with them. One such superstitious rule is "/Never/ ask whether floating-
point numbers are exactly equal".
Presumably the reasonable thing to do instead is to ask whether the numbers
differ by less than some tolerance; and this /is/ truly reasonable provided
you know what tolerance to choose. But the word /never/ is what turns the
rule from reasonable into mere superstition. Even if every floating-point
comparison in your program involved a tolerance, you would wish to predict
which path execution would follow from various input data, and whether the
different comparisons were mutually consistent. For instance, the predicates
X < Y - TOL and Y - TOL > X seem equivalent to the naked eye, but computers
exist (/not/ made by Apple!) on which one can be true and the other false
for certain values of the variables. To ask "Which?" violates the
superstitious rule.
There have been several attempts to avoid superstition by devising
mathematical rules called /axioms/ that would be valid for all commercially
significant computers and from which a programmer might hope to be able to
deduce whether his program will function correctly on all those computers.
Unfortunately, such attempts cannot succeed without failing! The paradox
arises because any such rules, to be valid universally, have to encompass so
wide a range of anomalies as to constitute the specifications for a
hypothetical computer far worse arithmetically than any ever actually built.
In consequence, many computations provably impossible on that hypothetical
computer would be quite feasible on almost every actual computer. For
instance, the axioms must imply limits to the accuracy with which
differential equations can be solved, integrals evaluated, infinite series
summed, and areas of triangles calculated; but these limits are routinely
surpassed nowadays by programs that run on most commercially significant
computers, although some computers may require programs that are so special
that they would be useless on any other machine.
Arithmetic anarchy is where we seemed headed until a decade ago when work
began upon IEEE Standard 754 for binary floating-point arithmetic. Apple's
mathematicians and engineers helped from the very beginning. The resulting
family of coherent designs for computer arithmetic has been adopted more
widely, and by more computer manufacturers, than any other single design.
Besides the undoubted benefits that flow from any standard, the principal
benefit derived from the IEEE standard in particular is this:
/Program importability:/ Almost any application of floating-point
arithmetic, designed to work on a few different families of computers in
existence before the IEEE Standard and programmed in a higher-level
language, will, after recompilation, work at least about as well on an Apple
computer or on any other machine that conforms to IEEE Standard 754 as on
any nonconforming computer with comparable capacity (memory, speed, and word
size).
The Standard Apple Numerics Environment (SANE) is the most thorough
implementation of IEEE Standard 754 to date. The fanatical attention to
detail that permeates SANE's implementation largely relieves Apple computer
users from having to know any more about those details than they like. If
you come to an Apple computer from some other computer that you were fond
of, you will find the Apple computer's arithmetic at least about as good,
and quite likely rather better. An Apple computer can be set up to mimic the
worthwhile characteristics of almost any reasonable past computer
arithmetic, so existing libraries of numerical software do not have to be
discarded if they can be recompiled. SANE also offers features that are
unique to the IEEE Standard, new capabilities that previous generations of
computer users could only yearn for; but to learn what they are, you will
have to read this book.
As one of the designers of IEEE Standard 754, I can only stand in awe of the
efforts that Apple has expended to implement that standard faithfully both
in hardware and in software, including language processors, so that users of
Apple computers will actually reap tangible benefits from the Standard. And
I thank Apple for letting me explain in this foreword why we needed that
standard.
Professor W. Kahan
Mathematics Department and
Electrical Engineering and
Computer Science Department
University of California at Berkeley
December 16, 1987
More information about the Python-list
mailing list