Re: accuracy when comparing doubles
On Jan 11, 12:55 pm, Jack Crenshaw <jcr...@earthlink.net> wrote:
James Kanze wrote:
On Jan 8, 12:29 am, Giuliano Bertoletti <gbe32...@libero.it> wrote:
James Kanze ha scritto:
However that's not the point. The point is:
- clearly floating point numbers can be viewed as an
independet algebraic structure with its own rules.
However they have been designed in that way with the
specific purpose of mimicking as close as possible the
behaviour of real numbers and operators. Therefore the
approximation view is preferable in most of the cases.
Except when it isn't. In fact, if you start thinking of
floating point values as an "approximation" of real
numbers, you'll quickly get into trouble. The issues are
more complicated, and if you want to write robust floating
point software, you have to understand floating point
arithmetic, and not just real arithmetic.
Your statements are simply contradictory.
You are after "robust floating point software", but at the
same time you consider exact the computations made with
floating point arithmetic.
They are exact, according to the definitions of floating point
arithmetic.
With respect, I think you are arguing semantics rather than
mathematics.
No. Mathematics knows many different kinds of numbers. My
point is precisely that floating point numbers are a type of
number; there are a certain number of operations defined on
them, and those operations are defined precisely.
Your statement seems to follow circular logic -- floating
point arithmetic is exact because it follows the rules of
floating point arithmetic.
And integer arithmetic is exact because it follows the rules of
integer arithmetic, and real arithmetic is exact because it
follows the rules of real arithmetic. Obviously. We're dealing
with definitions here.
That's like saying that a digital computer program should give
the same answer every time, given the same inputs.
And that that answer is deterministically known, according to a
strict set of rules. (Of course, programs don't always give the
same answers for the same input. C++ has undefined behavior,
and when threading kicks in...)
Well, of course it does, unless the computer is broken. Even
programs with simulated noise (i.e., a random number generated
buried inside), should give the same exact answer, if the RNG
seed isn't changed.
Reading /dev/random doesn't always give the same answer.
Counting the number of times you can loop between keyboard input
doesn't always give the same answer.
But with this logic whatever you do with fp is robust and
sound unless, and here's the contradiction, by robust you
actually mean that the final result approximates the better
it can the one you got from real arithmetics.
No. Floating point arithmetic obeys different rules than
real arithmetic, and you have to understand and obey those
rules if you want "useful" results.
So eventually you're after reals approximation.
Often (although not in my work). For the final results.
Whether the "exact" floating point result is an adequate
approximation of the real value you want depends on the laws
of floating point arithmetic, however, and not on the laws
of real arithmetic. And those laws are exact; there are no
approximations involved at that level.
Ok, let's clear the air here. We are really discussing AT
LEAST three different kinds of numbers here. "Real" numbers,
which I take to mean numbers in the mathematical sense
Let's clear the air here. There is no such thing as "numbers in
the mathematical sense". Mathematics knows many different types
of numbers, and they do follow different rules.
-- all rational plus irrational real numbers; the
APPROXIMATIONS of real numbers,
No. Rational numbers have their own laws, which aren't exactly
the same as real numbers. And integers have somewhat different
laws as well.
which are represented in computers using floating point (IEEE
or any other definition); and the practical case where we use
fp numbers to represent real-world values of some measurement
or computation.
Which may or may not work. Typically, we can represent
real-world values adequately with floating point numbers. The
problems come afterwards, because floating point numbers don't
obey the rules of real numbers. (They're not associative over
addition, for example)
I think part of the problems you and Guiliano are having are
that you tend to ping-pong from one of these entities to
another.
There are very few applications which can take errors of
several magnitude, and unless you design your algorithms
with the characteristics of floating point arithmetic (and
not real arithmetic) in mind, you can easily end up with
errors of several magnitude.
But nobody is saying that you should follow the real model
(i.e. making the same computations), I'm saying you're
after the real model final result. The better path to get
there is something fp knowledge has to tell you.
OK. There are exceptions, but that's usually the case. The
results are an approximation, but the analysis you do to
ensure that the approximation is adequate depend on the
exact behavior of floating point arithmetic.
- their algebraic structure is important because its
knowledge allows us to estimate (at least in simple
cases) the error we are making with this model. I say
simple cases because there are complex algorithm (i.e.
matrix inversion) where it can be difficult to estimate
the maximum error we're making.
There are some simple cases where you can pretty much
settle for using them as an "approximation"---I do so for
calculating percents, for example. But they don't go very
far.
Can you show us an example where you use floating point not
as an approximation of real numbers ? (note: fractional or
integer numbers are also real numbers).
Well, if you take the point of view expressed in the
parentheses, no.
That's right.
The problem is that that point of view doesn't lead us anywhere.
All floating point numbers do correspond to an exact real
number; in that sense, floating point numbers are a subset of
the real numbers. But addition is defined differently over
them; in that sense, they aren't related to floating point
numbers.
Regardless of some notion you have of theoretical behavior of
floating point numbers, they were invented for the specific
purpose of representing values of things in the physical world
-- voltages, currents, positions, velocities, and the like. Or
even non-physical things like sqrt(2) or sin(x).
Why they were invented is irrelevant. Trying to understand what
they really do is relevant. Since they've been invented, a lot
of research has been done on them, and the principles underlying
them are fairly well understood today.
I can't think of a single use of fp that doesn't involve doing
the best one can to approximate some other number that can't
be represented, exactly, in the computer.
I can. I regularly use them to represent monetary values, and
monetary values can always be represented exactly in a computer.
But that's not the point. It's clear that we can't implement
real numbers in a computer, since that would require infinite
memory. And it's clear that for many applications, floating
point is the best we can do. But that doesn't make them real
numbers, and they don't magically start obeying the rules of
real numbers just because we want them to.
You seem to be arguing that fp numbers have a domain all their
own, defined by the way they are implemented in a given
computer. Those rules are non-portable from computer to
computer, or even from, say, real and double.
And. It's not so much that I'm arguing it; I'm simply
constating a fact of life, that we have to deal with. It
doesn't make things simpler, but that's life.
Giuliano (and I) are saying that use of fp doesn't have much
value, or make much sense, except to APPROXIMATE the values of
real numbers in the mathematical sense.
The problem is that arithmetic over floating point numbers
behaves significantly differently than arithmetic over real
numbers.
But the most frequent use of floating point in my current
applications is monetary values, and the abstraction we use
isn't real, but decimal arithmetic (with five digits after
the decimal); we take pains to ensure that the results are
correctly rounded to these values before continuing
calculations.
Ah. There's the rub. IMHO you are using a fundamentally wrong
method to represent a whole 'nuther kind of real number. Use
of fp numbers to represent monetary values is fundamentally
flawed. You should define a new type entirely, called
something like MonetaryValue, which uses decimal arithmetic
throughout. I think you are deluding yourself that your
numbers are being "correctly" computed. The fact that you get
the same number every time doesn't mean it's the right one.
And comparing it to the same number, computed by the same
computer, using the same fp calculations, does _NOT_ prove
that they are "equal."
Certainly. It's now what I would have choosen. But in fact,
for what we're doing, it works fairly well, and it's certainly a
lot easier than defining all of the necessary operations over
some new numeric type. (We're often dealing with things like
compound interest and such, which require more or less
complicated functions.)
- you should never compare computed results against
fixed value constants with the equal operator.
Nonsense.
Quoting from Wikipedia (http://en.wikipedia.org/wiki/Floating-point)=
:
"The use of the equality test (if (x==y) ...) is usually
not recommended when expectations are based on results
from pure mathematics.
There's a significant difference betweeh "usually not
recommended when expectations are based on the results
from pure mathematics" and "never".
Well, yes never is a bit too strong. But that's really a
bad practice.
In some cases. In others, it's perfectly appropriate. (In
particular, comparing for equality with 0.0 is often
appropriate.)
No, it's not. Not even close. 1.0e-31, or even 1.0e-300, is
_NOT_ zero, nor will any == test claim it to be.
Exactly. And if you need 0.0, then you can't say that they are.
Furthermore, you seem to be ignoring the possibility that
computations lose precision. If you subtract two 15-digit
numbers, you can easily get a _ONE_ digit result.
You're the one who seems to be ignoring it. I'm the one saying
that it isn't a question of an approximation; that the results
aren't governed by the rules of real arithmetic.
The point is that you have to understand what you're doing,
and act in consequence. Never use == is as bad a rule as
always use ==.
Again IMO, it's _NOT_ a bad rule, and use of a == comparison
is _NEVER_ a good idea. That rule has not changed since 1960,
and for good reason.
That was never a rule among people who knew what they were
doing. It's some silly rule made up by people who didn't want
to go to the bother of learning what they were doing.
Even in the Wikipedia article, however, the expression
should be "mathematics with real numbers", and not "pure
mathematics"---floating point is also subject to some real
mathematics.
To me it simply means that when x or y are the result of
some computations (es. x = a + b), you should not relay on
the == operator because even a small error you carry along
can lead you completely off track.
It depends. If the small error is acceptable, fine. If
it's not, you should compare for equality. There are many
cases where such comparisons are reasonable.
This is different for example from settings some values to
-1.0 in a matrix and then checking back whether an element
is == -1.0.
Clearly this works if, for example, you're sure that no
computation on that matrix will set a negative value.
Sentinal values which you set are an obvious case. There
are also cases where a calculation must result in 0.0, and
doubtlessly some where it must result in some other exact
value (1.0, etc.).
Even that (use of sentinel numbers), I submit, is bad
practice.
But you can't give a reason for it.
If you want to know if a given number has ever been given a
value, you should initialize it to NaN, not -1.0 or any other
"real" number.
Not all floating point representations support NaN.
Better yet, find another way, using a boolean or some other
flag, to indicate that a number has been initialized.
Sure. There are other possible solutions. Whether they are
better or not depends on context.
Such tests are sometimes replaced with "fuzzy"
comparisons (if (abs(x-y) < epsilon) ...), where epsilon
is sufficiently small and tailored to the application,
such as 1.0E-13 - see machine epsilon). The wisdom of
doing this varies greatly. It is often better to organize
the code in such a way that such tests are unnecessary."
The important point is that you have to know what you're
doing. Just replacing all of your tests for equality with
tests for approximate equality isn't going to make broken
code correct.
That depends on why the code is broken.
If for example I'm trying to find a solution of:
x^2 = exp(-x)
replacing the equality test with a fabs( ... ) < epsilon
helps a lot. (searching for the minimum is even better).
Clearly the rest of the algorithm must be also clever
enough to hunt the root down properly, epsilon choosen
properly and so on, but that's another story.
It's that other story which always worries me. It's
possible, for example, for an algorithm to converge using
real numbers, but not with floating point arithmetic. Other
algorithms need serious rework---even something as simple as
finding the average of a large set of values.
I'll go even further than that. An iterative computation --
the only kind for which the notion of convergence makes sense
-- will almost _ALWAYS_ fail to converge,
Unless it was designed to converge, according to the rules of
floating point arithmetic.
if one sets the criterion for convergence too small. When
differences get down to the point of differences in the LSB,
it's common for them to ping-pong back and forth between two
numbers, neither of which is exactly equal to zero.
Please tell me you are not using iterative convergence
techniques on monetary values.
Not directly. But I suppose that some of the functions we use
do. How else do you calculate a square root or an exponant.
And sqrt(2.0) has an exact answer in floating point arithmetic
(which isn't exactly the same as in real arithmetic); a test
program for a sqrt function will use an exact comparison
(probably with an artificially constructed floating point) to
verify that it works.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34