"Tim Peters" <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
