accuracy when comparing doubles

[James Kanze]

Lionel, can you give me an example of the latter, in an
application more serious than Freecell?

Generating session keys. In general, non-reproducibility is a
requirement for many cryptographic uses.

I doubt that people playing on line poker would like the idea of
a deterministic sequence either. (Given the money involved, I
guess you'd have to consider that "serious".)

For games and such (not really serious), I use it as the default
seed for the random number generator (logging it so that I can
duplicate the sequence if there turns out to be a bug).

[...]

The problem is that arithmetic over floating point numbers
behaves significantly differently than arithmetic over
real numbers.
Yes, indeed they do. Which is why testing them for
equality is a Bad Idea.

I find that a bit of a non-sequitur. Why should it be a Bad
Idea to test for equality of floating point numbers if that
is what you want; ie. you truly wish to test for equality in
the (unambiguously defined) sense of floating point - not
real number - arithmetic.
Sentinel values are a case in point. You do, of course, have
to be aware of potential pitfalls, such as the possibility
that you end up comparing the result of a fp computation
that "accidently" happens to compute your sentinel value.

That's it exactly. Certainly testing a number for equality,
when you're the one who gave it its value, is perfectly valid
and safe. The last time I did that was yesterday. But, as you
say, there is always the possibility, however improbable, that
the result of an fp computation also yields that exact number.
That's why it's not a good practice.

I generally prefer a separate boolean to sentinal values, but
depending on the use, I wouldn't go so far as to call using a
sentinal value "bad practice"---using an out of band value is a
well established idiom for a lot of things. (Why do you think
we have null pointers?) Obviously, it only applies when there
are values which cannot occur otherwise.

Testing floating point numbers for equality is often a bad
idea because there are many potential pitfalls associated with
doing so.

You can say that about just about anything: using virtual
functions, templates... In this case, I'd say the problem isn't
testing floating point numbers for equality---it's using them to
begin with. Just avoiding tests for equality won't avoid the
pitfalls---unless you understand what you're doing, you
shouldn't be using floating point, period.

 

[James Kanze]

I beg to differ and agree with Jack.

Machine floats (as a set) and the operations +,-,*,/ defined
on this set don't form a field. But a field is one of the
algebraic structures mathematicians like to deal with. That's
why numerical error analysis of algorithms is much easier via
the "approximation-of- real-numbers model".

Let's see if I understand what you're saying correctly.
Arithmetic operators over floating point don't form a field.
But the only theories I understand concern fields. So I'll just
pretend that floating point numbers do form a field if I ignore
some epsilon, and let it go at that. Of course, even just
ignoring some epsilon, they're still not a field. Regardless of
the epsilon, (a+b)+c != a+(b+c), for example.

So basically, what you're recommending is to ignore reality,
because it's inconvenient.

Every operation is assumed to be exact in terms of real
arithmetic but is then followed by a distortion that is below
a certain fraction (epsilon) of the exact* result.

The problem is that this point of view leads to false results.
Consider a=1E100, b=-1E100 and c=1.0. (a+b)+c gives 1.0, which
is the correct answer, even over the reals. a+(b+c) gives
0.0. In the first case, testing for exact equality is
guaranteed to work, and in the second, you can use any epsilon
you want, the test will fail.

 

[James Kanze]

James Kanze wrote:

[...]

Please give an example of a program which needs such. Then please
explain your test plan.

I've already given several. If you're interested in the least
in cryptology or computer security, you need them.

And while the test plan for my program would be simple (use
something different than /dev/random for the tests), testing
something like /dev/random is pretty awkward. You can do
statistical tests on the output, of course, but in the end, the
correctness of the code is established by code review, more than
by tests.

We seem to be working in different worlds. Mine is the world
of programming software for real-time embedded systems, for
customers like NASA and the military. NASA and the military
are rather picky: They insist that the software we put in
their aircraft, missiles, and spacecraft should not just work
most of the time; they should work _ALL_ the time. Not only
that, they should be proven to work before they are certified.
You cannot present that proof if you can't perform tests that
show that the system doesn't fail for any possible combination
of inputs.

On the embedded systems I've worked on, we simply didn't use
floating point. Beyond that, you can't perform tests for all
possible inputs on anything but the simplest system. For
critical systems, you prove the program is correct (and also use
extensive tests to validate your proofs, of course).

It's easy to say that one has to be careful. That's a given.
But these agency demand a lot more than "careful." They demand
that the stability of the system not depend on careful and
knowledgeable users.

Who's talking about users here? We're talking about programs.

I also develop software for scientific/engineering
applications, especially simulations of real-world systems. As
you have pointed out, real-world systems are by their nature
unpredictable, because they depend on imprecise measurements
and asynchronous events.

But the simulation of those systems must ABSOLUTELY be
predictable, in the sense that equal inputs yield equal
outputs.

We have this rather well-established process called
Validation. It means that every single line of code must do
what is expected of it, over the entire range of its possible
inputs. To validate, we must test the software, using unit
tests, module tests, end-to-end tests, etc., to be certain
that the program performs as its requirement spec said it
should.

You mean that you create a test harness for every single line of
code, independently?

I've worked on critical systems in the past, but we never went
that far. We used a combination of methods, including formal
proofs, code review (and review of the proofs), extensive and
comprehensive testing at all levels (with review to ensure that
the tests were extensive and comprehensive).

You simply cannot satisfy these conditions if the results of
one run don't match those of another, given the same inputs.

In other words, you test for equality, even if the values are
floating point.

Seriously (and I don't know the answer): how do you validate
software whose requirement is that an external observer cannot
determine a value (a session key, for example) based on data he
can see (the encrypted data passing on the line)? I don't know
how to write a test case for that, and I'm not too sure what I'd
have to look for in a code review.

[...]

Precisely. Which is why one shouldn't depend on that test.

No. Precisely why we should know what we are doing. Just
replacing the test for equality with one for an approximate
equality won't change anything (since the error can be
infinitely big). Rearranging the calculations so that the case
where the results are wrong doesn't occur is the only answer.
And that requires understanding floating point arithmetic, not
applying some simplistic rules.

[...]

Sigh. It should be abundantly obvious that using fp arithmetic
to represent fp arithmetic is exact and predictable. It's a
tautology, so please stop repeating it.

Well, you and others seem to argue against it.

Using fp arithmetic to represent measurements in the real
world is, by necessity, an APPROXIMATION. And while there may
be times -- adding 1.0 and 2.0, for example -- where the
results of the two computations are the same, one cannot count
on this unless one knows in advance that every possible input
will be of the kind that yields exact results.

If your input is an approximation, then the results will be an
approximation. But with what error factor.

I keep coming back to the problem of (a+b)+c != a+(b+c).
Starting with a==1E100, b==-1E100 and c==1.0, it doesn't matter
whether your initial values are exact, or an approximation
+/-10%. The second equation will result in a value that is
completely wrong, period. You have to understand floating point
arithmetic in order to use it safely. And if you understand it,
you know when using equality is appropriate, and when it isn't.

You claim that you do know this, for your application, and I
have no reason to doubt that. But whenever I try to probe a
little deeper, you wander off into discussions of iterations,
and transcendental functions, and similar stuff where you
absolutely cannot know it.

I know what my results represent, and I know how to use them.
At at times, we use exact comparisons. Without any problems.
(In my particular case, after calculating a value, we ensure
that it is the closest possible representation of a multiple of
10^-5.)

 

[James Kanze]

James Kanze ha scritto:

[I'm cutting a lot, because I agree with much of what you
are saying]

You're making confusion with floats being a subset of reals and
operators not matching it's real counterpart.

Actually, it was Jack who was making that confusion. I'm
arguing the you shouldn't make that confusion.

We should speak of an "algebraic structure" which means the
set of elements (not necessarily numbers) along with the
operators which work on them.

If seen under this views, fp, reals, complexes, integers,
fractions, polynomials, matrices, points over elliptic curves,
etc. have all they're algebraic structure and operations are
well defined (and exact) over them.

We'll also assume that we do perfectly know how they works.

Now, what you we mean by "robust" fp application ? Why do you
use fp and not points over elliptic curves in your application?

Because you're trying to use the model which best matches your
requirements, and since your requirements are to perform
computations with real numbers you use fp and not elliptic
curves.

Just a nit, but you're trying to use the model which gives you
the best results, for some specific definition of "best". Most
of the the time, floating point is chosen as best because it's
there, implemented in the hardware. And is adequate, provided
you know what you're doing.

[...]

The problem is that you're refusing to see that fp algebraic
structure is an approximation of reals algebraic structure.

Sort of. In many ways, it's not a very good approximation.

My point of view is simple:

1) I need to model a program using reals
2) I have to perform some computations on real numbers.
3) I cannot use reals on a computer
4) I use fp instead of reals and take into account all the
deviations involved (including taking the best path for fp
among all available on reals).
5) I use the fp result as an approximation of the result I was
looking for after having computed (manually) an upperbound of
the deviation involved.

That's also probably what you're doing. But still you refuse
to see it as an approximation of real results.

The results are often interpreted as an approximation of the
real results. What you seem not to be seeing is that I'm
talking about the intermediate steps.

Take something simple like finding the average. If I could deal
with reals, I'd simply write:

real total = 0.0 ;
for ( iter = v.begin() ; iter != v.end() ; ++ iter ) {
total += *iter ;
}
return total / v.size() ;

If I replace real with double, however, the return value might
not be a very good approximation of the real results. Depending
on the size of the vector and the possible values, I'll probably
write the code differently. I'll design my floating point
arithmetic using the laws of floating point arithmetic.
Otherwise, my results won't necessarily be close to the real
results.

That's why it's better to use a range comparison after having
carefully estimated the epsilon according to the computation
you've done.

No. That's simply wrong. There is no "universal" answer---you
have to understand what the algorithm is doing, and why it needs
zero.

There are many cases, when floating point is being used as an
approximation for reals, you will use a range comparison. For
that matter, most of the time, when working with real numbers to
begin with, you'd use a range comparison. Because you're
dealing with approximations to begin with. And you'll analyse
your floating point code to ensure that it doesn't increase the
error, so you can test exactly as you would with reals.

In other cases, however...

In my current application (the part I'm personally responsible
for---which is mainly transactional integrity and persistence of
market trades, along with the routing of change notifications),
we use exact comparison of floating points in two cases: we
compare the quanity traded against 0.0--- realistically, no
trades will be anywhere close to 0.0, and the value can only
increase, never decrease. In the other case, we compare a new
value with an old, to decide whether to generate a change
notification or not---again, realistically, no changes will be
anywhere near the epsilon of a double.

I see no reason not to use exact comparison in either of these
cases.