[Nick Maclaren]
>> ...
>> Yes, but that wasn't their point. It was that in (say) iterative
>> algorithms, the error builds up by a factor of the base at every
>> step. If it wasn't for the fact that errors build up, almost all
>> programs could ignore numerical analysis and still get reliable
>> answers!
>>
>> Actually, my (limited) investigations indicated that such an error
>> build-up was extremely rare - I could achieve it only in VERY
>> artificial programs. But I did find that the errors built up faster
>> for higher bases, so that a reasonable rule of thumb is that 28
>> digits with a decimal base was comparable to (say) 80 bits with a
>> binary base.
[Hendrik van Rooyen]
> I would have thought that this sort of thing was a natural consequence
> of rounding errors - if I round (or worse truncate) a binary, I can be
> off by at most one, with an expectation of a half of a least
> significant digit, while if I use hex digits, my expectation is around
> eight, and for decimal around five...
Which, in all cases, is a half ULP at worst (when rounding -- as
everyone does now).
> So it would seem natural that errors would propagate
> faster on big base systems, AOTBE, but this may be
> a naive view..
I don't know of any current support for this view. It the bad old days,
such things were often confused by architectures that mixed non-binary
bases with "creative" rounding rules (like truncation indeed), and it
could be hard to know where to "pin the blame".
What you will still see stated is variations on Kahan's telegraphic
"binary is better than any other radix for error analysis (but not very
much)", listed as one of two techincal advantages for binary fp in:
http://www.cs.berkeley.edu/~wkahan/MktgMath.pdf
It's important to note that he says "error analysis", not "error
propagation" -- regardless of base in use, rounding is good to <= 1/2
ULP. A fuller elementary explanation of this can be found in David
Goldberg's widely available "What Every Computer Scientist Should Know
About Floating-Point", in its "Relative Error and Ulps" section. The
short course is that rigorous forward error analysis of fp algorithms is
usually framed in terms of relative error: given a computed
approximation x' to the mathematically exact result x, what's the
largest possible absolute value of the mathematical
r = (x'-x)/x
(the relative error of x')? This framework gets used because it's more-
or-less tractable, starting by assuming inputs are exact (or not, in
which case you start by bounding the inputs' relative errors), then
successively computing relative errors for each step of the algorithm.
Goldberg's paper, and Knuth volume 2, contain many introductory examples
of rigorous analysis using this approach.
Analysis of relative error generally goes along independent of FP base.
It's at the end, when you want to transform a statement about relative
error into a statement about error as measured by ULPs (units in the
last place), where the base comes in strongly. As Goldberg explains,
the larger the fp base the sloppier the relative-error-converted-to-ULPs
bound is -- but this is by a constant factor independent of the
algorithm being analyzed, hence Kahan's "... better ... but not very
much". In more words from Goldberg:
Since epsilon [a measure of relative error] can overestimate the
effect of rounding to the nearest floating-point number by the
wobble factor of B [the FP base, like 2 for binary or 10 for
decimal], error estimates of formulas will be tighter on machines
with a small B.
When only the order of magnitude of rounding error is of interest,
ulps and epsilon may be used interchangeably, since they differ by
at most a factor of B.
So that factor of B is irrelevant to most apps most of the time. For a
combination of an fp algorithm + set of inputs near the edge of giving
gibberish results, of course it can be important. Someone using
Python's decimal implementation has an often very effective workaround
then, short of writing a more robust fp algorithm: just boost the
precision.
--
http://mail.python.org/mailman/listinfo/python-list
