Re: remarks on significance arithmetic implementation [Was: Re: Numerical accuracy/precision - this is a bug or a feature?]

*To*: mathgroup at smc.vnet.net*Subject*: [mg120369] Re: remarks on significance arithmetic implementation [Was: Re: Numerical accuracy/precision - this is a bug or a feature?]*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Wed, 20 Jul 2011 06:33:07 -0400 (EDT)

As before, I think much of this discussion is useless. But this example DOES give me pause: > Consider the two expressions > f[x_]:= (x-1)*(x+1) and g[x_]:=(x^2-1) > > which are analytically the same function. > > given the value v=Interval[{-1/2,1/2}] f[v] returns an interval with > width 2. g[v] returns an interval with width 1/4. I don't see why we'd want significance tracking to act this way. Bobby On Tue, 19 Jul 2011 05:58:03 -0500, Richard Fateman <fateman at eecs.berkeley.edu> wrote: > On 7/18/2011 11:54 AM, Daniel Lichtblau wrote: >> >> [Caution: This may increase the entropy of the thread, and almost >> certainly will increase the ennui.] > Yep >> >> > ... snip ... a bunch of things I think we agree upon. >> To expand on "properly rounded floats" I will mention that >> Mathematica's significance arithmetic, in certain settings, is as >> conservative as interval arithmetic. Specifically this works out when >> the operations used are addition, multiplication, integer powering, or >> division with both operands approximate. Also required is that they >> have more significant digits than can be represented by the error >> recorder (that is to say, more than 16 or so digits when error is >> recorded as a 53-bit-mantissa float). The gist is that precision is >> altered downward in a way that will even account for second order >> error (and the higher order error terms that exist in computing x/y >> where x and y are both approximate bignums). > I am unclear on this zeroth, first, second order error categorization. > It seems to me that the critical problem, and one that is not addressed > by Mathematica, in interval arithmetic, is addressing dependence of > operands. Consider the two expressions > f[x_]:= (x-1)*(x+1) and g[x_]:=(x^2-1) > > which are analytically the same function. > > given the value v=Interval[{-1/2,1/2}] f[v] returns an interval with > width 2. g[v] returns an interval with width 1/4. > > The function g is obviously a lot better than f. > Same thing happens for v=0.1`2. f[v] is -0.99`269.. but g[v] is > -0.99`3.69... So according to Mathematica, g evaluates > to a full decimal digit higher accuracy. > > A true devotee of interval arithmetic (or of significance arithmetic) > would take the function body for f and rearrange it as g, > and also would require for comparisons such concepts as possibly-equal, > certainly-greater-than etc. And would need > to resolve meanings for empty intervals and other such things. Some of > these may in fact be in Mathematica's interval > arithmetic suite. They seem to be absent in the significance arithmetic > world, though there is a transition from one to the > other possible. > Note that Interval[0.1`2] returns the fairly nonsensical > Interval[{0.1,0.10}] but InputForm[%] shows > Interval[{0.098046875`1.9914337561691884, > 0.101953125`2.008400542026431}], maybe overkill. > Interval[{0.98,0.102}] might be OK. > > > There are ways of reducing semi-automatically, the number of repeat > occurrences of operands in such expressions, thereby improving the > interval widths. This (that is, computing "single use expressions") is > the kind of thing that would, I think, be useful and for which computer > algebra systems are especially appropriate. That, in combination with > some other tricks of interval "reliable" arithmetic would be helpful > (and for which I have written some programs, not in Mathematica > though). So the real contribution to interval arithmetic (or > significance arithmetic) of Mathematica would be if it were able to > reformulate some subset of expressions so that they were automatically > computed faster and more accurately. > > (One could argue that boosting the software precision will get the > answer accurately, especially if one ignores exponentially longer > run-times.) > > > For some discussion in the context of a (different) programming language > that is not much like Mathematica, see > > http://developers.sun.com/sunstudio/products/archive/whitepapers/tech-interval-final.pdf > > There are other, more expensive techniques. E.g. if p(x) is a > polynomial, what is p[Interval[{a,b}]] ? > Instead of just interval-alizing the + and * and ^, find the extrema of > p between a and b. > What is Sin[Interval[...]], etc. > >> >> It would not be hard to extend this to the taking of reciprocals and >> hence division of integer by float e.g. x --> 1/x. But as best I can >> tell from looking at the code, Mathematica does not do this, so error >> tracking in that case is purely first order. > > Maybe I'm not following here, but computing an interval for 1/x does not > seem difficult. >> >> >>> [...] >>> My point remains: >>> WRI could have a much more direct notion of number, and equality, >>> that >>> would make it easy to implement my choice of arithmetic or theirs or >>> yours. >>> They didn't. The default is not completely reliable. People write to >>> this newsgroup, periodically, saying Huh? what's going on? I found a >>> bug! >> >> This is, I am afraid, nonsense. Nothing would make it "easy" to >> implement significance arithmetic across the spectrum of Mathematica's >> numerical engine. To do so efficiently, reliably, maintainably, etc. >> is, well, a significant task. Jerry Keiper could do it. Mark Sofroniou >> could do it. I do not think I could do it, at least not very well. >> And, as the saying goes, "I have me doubts about thee". > > OK, I did not mean it would be easy to reproduce what Jerry Keiper did, > but after all, he did do it using ordinary arithmetic at its base. > What I did mean is that programs to do arithmetic "the machine way" > would run at machine speed (= easy); the programs to do software > bigfloats without significance tracking would run faster (=easier) than > including significance tracking. And that if one wished to patch-up > such code with built-in tracking ,after the fact by re-stating the > precision after each operation, that would be slower (= not as easy) > than avoiding it in the first place. > So, easy= easy for the computer. > > I do think that people write to the newsgroup reporting what they think > of as bugs, but are actually the deliberate consequences of the design > of arithmetic. >> >> >>> As for the experimental and computational notions of (im)precision, I >>> think there is an issue of using the same words with different >>> meanings. >>> Similar but unfortunately different. Precision of a floating point >>> number F is simply the number of bits in the fraction. If you impute >>> some uncertainty to F, you can store that in another piece of data D in >>> the computer. If you want to assert that F and D together represent a >>> distribution of a certain kind you can also compute with that. >>> >>> RJF >>> [...] >> >> Related to the above (I think), you stated earlier in this thread that >> the differences in terminology usage can be troublesome. I agree that >> the meaning of Mathematica's Precision and, to a lesser extent, >> Accuracy, might cause initial confusion to one unfamiliar with the >> software but well versed in Numerical Analysis. I would expect such >> people to catch on after being bitten once or twice, and either get >> used to the distinctions, or use different software. > yes, but there are not too many well versed in numerical analysis. >> >> This strikes me as similar to the situation wherein Append and Prepend >> are O(n) rather than O(1) complexity operations, since they rewrite >> their List arguements in full. A CS person new to Mathematica might >> well assume List is akin to the CS notion of a (singly or doubly) >> linked list. After learning otherwise they'd probably not be too >> flustered, other than perhaps to mutter that the naming of "List" was >> problematic. Even that would perhaps abate once they get accustomed to >> the very general Mathematica notion of a List. After all, a linked >> list is a modestly arcane structure to those outside CS, and most >> general software users are not from inside CS, and most CS people will >> understand that. > Similar, yes. Dissimilar in the sense that the List operations return > expected results, just slower. But arithmetic returns (on occasion) > unexpected results. > > RJF > > -- DrMajorBob at yahoo.com

**Re: sorting a nested list of 4-tuples**

**ExampleData[{"Geometry3D", "Torus"}]**

**Re: remarks on significance arithmetic implementation [Was: Re: Numerical accuracy/precision - this is a bug or a feature?]**

**Total plot width**