views:

207

answers:

7

I'm working on an application that does a lot of floating-point calculations. We use VC++ on Intel x86 with double precision floating-point values. We make claims that our calculations are accurate to n decimal digits (right now 7, but trying to claim 15).

We go to a lot of effort of validating our results against other sources when our results change slightly (due to code refactoring, cleanup, etc.). I know that many many factors play in to the overall precision, such as the FPU control state, the compiler/optimizer, floating-point model, and the overall order of operations themselves (i.e., the algorithm itself), but given the inherent uncertainty in FP calculations (e.g., 0.1 cannot be represented), it seems invalid to claim any specific degree of precision for all calulations.

My question is this: is it valid to make any claims about the accuracy of FP calculations in general without doing any sort of analysis (such as interval analysis)? If so, what claims can be made and why?

EDIT:

So given that the input data is accurate to, say, n decimal places, can any guarantee be made about the result of any arbitrary calculations, given that double precision is being used? E.g., if the input data has 8 significant decimal digits, the output will have at least 5 significant decimal digits... ?

We are using math libraries and are unaware of any guarantees they may or may not make. The algorithms we use are not necessarily analyzed for precision in any way. But even given a specific algorithm, the implementation will affect the results (just changing the order of two addition operations, for example). Is there any inherent guarantee whatsoever when using, say, double precision?

ANOTHER EDIT:

We do empirically validate our results against other sources. So are we just getting lucky when we achieve, say, 10-digit accuracy?

+7  A: 

As with all such questions, I have to just simply answer with the article What Every Computer Scientist Should Know About Floating-Point Arithmetic. It's absolutely indispensable for the type of work you are talking about.

Jim Buck
Read it slowly. Don't skim. That article is targeted at *programmers*, not FPU implementors, and it's a classic.
Stephen Canon
+6  A: 

Short answer: No.

Reason: Have you proved (yes proved) that you aren't losing any precision as you go along? Are you sure? Do you understand the intrinsic precision of any library functions you're using for transcendental functions? Have you computed the limits of additive errors? If you are using an iterative algorithm, do you know how well it has converged when you quit? This stuff is hard.

dmckee
+4  A: 

Unless your code uses only the basic operations specified in IEEE 754 (+, -, *, / and square root), you do not even know how much precision loss each call to library functions outside your control (trigonometric functions, exp/log, ...) introduce. Functions outside the basic 5 are not guaranteed to be, and are usually not, precise at 1ULP.

You can do empirical checks, but that's what they remain... empirical. Don't forget the part about there being no warranty in the EULA of your software!

If your software was safety-critical, and did not call library-implemented mathematical functions, you could consider http://www-list.cea.fr/labos/gb/LSL/fluctuat/index.html . But only critical software is worth the effort and has a chance to fit in the analysis constraints of this tool.

You seem, after your edit, mostly concerned about your compiler doing things in your back. It is a natural fear to have (because like for the mathematical functions, you are not in control). But it's rather unlikely to be the problem. Your compiler may compute with a higher precision than you asked for (80-bit extendeds when you asked for 64-bit doubles or 64-bit doubles when you asked for 32-bit floats). This is allowed by the C99 standard. In round-to-nearest, this may introduce double-rounding errors. But it's only 1ULP you are losing, and so infrequently that you needn't worry. This can cause puzzling behaviors, as in:

float x=1.0;
float y=7.0;
float z=x/y;
if (z == x/y) 
...
else
... /* the else branch is taken */

but you were looking for trouble when you used == between floating-point numbers.

When you have code that does cancelations on purpose, such as in Kahan's summation algorithm:

d = (a+b)-a-b;

and the compiler optimizes that into d=0;, you have a problem. And yes, this optimization "as if floats operation were associative" has been seen in general compilers. It is not allowed by C99. But the situation has gotten better, I think. Compiler authors have become more aware of the dangers of floating-point and no longer try to optimize so aggressively. Plus, if you were doing this in your code you would not be asking this question.

Pascal Cuoq
That FLUCTUAT link looks very interesting.
j_random_hacker
(Mitpicking) most functions in a good math library are accurate to substantially better than 1 ulp. What they often are not is *correctly rounded*, which is 0.5 ulp accuracy in the default rounding mode.
Stephen Canon
+2  A: 

Given that your vendors of machines, compilers, run-time libraries, and operation systems don't make any such claim about floating point accuracy, you should take that to be a warning that your group should be leery of making claims that could come under harsh scrutiny if clients ever took you to court.

Without doing formal verification of the entire system, I would avoid such claims. I work on scientific software that has indirect human safety implications, so we have consider such things in the past, and we do not make these sort of claims.

You could make useless claims about precision of double (length) floating point calculations, but it would be basically worthless.

Ref: The pitfalls of verifying floating-point computations from ACM Transactions on Programming Languages and Systems 30, 3 (2008) 12

mctylr
Thanks for saving me the trouble to dig up the link (my excuse was that the "pitfalls..." report is from the point of view of the analyzer author, but that really was laziness). If the software you are working on is worth trying to verify formally, there are several groups in my near vicinity who work on providing tools for that. In addition to Fluctuat (link in my answer), there is http://hisseo.saclay.inria.fr/documents.html
Pascal Cuoq
A: 

A double precision number on an Intel CPU has slightly better than 15 significant digits (decimal).

The potrntial error for a simple computation is in the ballparl of n/1.0e15, where n is the order of magnitude of the number(s) you are working with. I suspect that Intel has specs for the accuracy of CPU-based FP computations.

The potential error for library functions (like cos and log) is usually documented. If not, you can look at the source code (e.g. thr GNU source) and calculate it.

You would calculate error bars for your calculations just as you would for manual calculations.

Once you do that, you may be able to reduce the error by judicious ordering of the computations.

Michael J
+1  A: 

No, you cannot make any such claim. If you wanted to do so, you would need to do the following:

  • Hire an expert in numerical computing to analyze your algorithms.
  • Either get your library and compiler vendors to open their sources to said expert for analysis, or get them to sign off on hard semantics and error bounds.

Double-precision floating-point typically carries about 15 digits of decimal accuracy, but there are far too many ways for some or all of that accuracy to be lost, that are far too subtle for a non-expert to diagnose, to make any claim like what you would like to claim.

There are relatively simpler ways to keep running error bounds that would let you make accuracy claims about any specific computation, but making claims about the accuracy of all computations performed with your software is a much taller order.

Stephen Canon
A: 

Since you seem to be concerned about accuracy of arbitrary calculations, here is an approach you can try: run your code with different rounding modes for floating-point calculations. If the results are pretty close to each other, you are probably okay. If the results are not close, you need to start worrying.

The maximum difference in the results will give you a lower bound on the accuracy of the calculations.

Alok
Comparing the differences of different rounding modes would compare the rounding modes, and the stability of the affected computations, not the accuracy.
mctylr
It will give you a lower limit on the accuracy of the floating-point calculations.
Alok