Maths error

[Tim Peters]

[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.