[Date Index] [Thread Index] [Author Index]

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