Maths error

[Hendrik van Rooyen]

 "Tim Peters" <tim.one at comcast.net> wrote:


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

Thanks Tim, for taking the trouble. - really nice explanation.

My basic error of thinking ( ? - more like gut feel ) was that the
bigger bases somehow lose "more bits" at every round, 
forgetting that half a microvolt is still half a microvolt, whether
it is rounded in binary, decimal, or hex...

- Hendrik