remarks on significance arithmetic implementation [Was: Re: Numerical accuracy/precision - this is a bug or a feature?]
- To: mathgroup at smc.vnet.net
- Subject: [mg120333] remarks on significance arithmetic implementation [Was: Re: Numerical accuracy/precision - this is a bug or a feature?]
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 19 Jul 2011 06:56:47 -0400 (EDT)
[Caution: This may increase the entropy of the thread, and almost certainly will increase the ennui.] On 07/16/2011 04:40 AM, Richard Fateman wrote: > On 7/14/2011 11:55 PM, Andrzej Kozlowski wrote: > [...] > I view significant digit arithmetic, if by digit you allow binary digit > or "bit", to be a crude version of interval arithmetic where the > endpoints of the interval are not numbers of (essentially) arbitrary > precision, but where the endpoints must be represented by the central > point plus or minus some power of two. It is an approximation to > interval arithmetic. I am no longer sure of the intricacies but I think "significant digit" arithmetic is the very most granular form of "significance arithmetic". That is to say, significance is regarded as a discrete integer-valued entity. In significance arithmetic, as you observe, it need not be so coarse (and need not/cannot/should not be infinitely fine). The terms "zero order approximation" and "first order approximation" have also been used in this thread. The first describes fixed precision arithmetic wherein no attempt is made to track error. The second could be used to describe significant digit, or significance arithmetic, or affine arithmetic, or "uncertain calculus", or other such methods of error propagation, provided error is estimated from a first derivative or approximation thereof. Any of these arithmetic models could in principle also use higher order error approximation, I would suppose. In practice they do not (but see caveat below). > I think it is a reasonable idea to restrict the > number of digits carried in the value of the interval endpoints (making > them "cruder" than you might really know) in the interests of efficiency > in time and space. Above you are, I believe, describing significance arithmetic. The restricting in the Mathematica implementation is via using a machine double to record the precision (you probably knew this, but wanted it stated for the general readership). > Thus using properly rounded machine floats is > appropriate, at least when the range is suitable and the difference > between upper and lower bounds is large. Using just one bit makes the > width of the interval grow faster than using more bits... 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). 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. > [...] > 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". > 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. 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. Daniel Lichtblau Wolfram Research