Float comparison

[James Kuyper]

Close, but ...

Yep, sorry for the typo.

 

[Flash Gordon]

Last I checked PI was irrational and therefore not something that it was claimed
to be able to compute exactly.

Pi may be irrational, but any algorithm in C will be calculating
rational approximations. At some point your rational approximation of Pi
will not be representable in the finite amount of memory available for
it to run.

 

[Flash Gordon]

Flash Gordon wrote:
.... snip ...

The critical point here is what does sin(11) return.

No, the critical point is YOU DO NOT KNOW based on the value stored in x
what the correct range is.

If it returns
a double, then you can safely assume that x holds the value that
sin(11) will return in future (assuming sin is a single valued
function).

I suggest you look sin up in the standard.

If you assert that sin(11) returns the sin of an angle
of 11 degrees, there are two accuracies involved. One is the
accuracy of the sin function. It is pointless arranging an
algorithm that could return values more accurate than that of the
double (assuming it is returning a double).

Again, look up the standard.

I think the C restrictions are such that we can assume sin returns
a single valued function representing the sine of an angle TO SOME
ACCURACY.

Now, based on the value in x and NOTHING more, how do you determine what
the possible range is for its correct value?

Also, this was an illustration of what I was explaining. You have
snipped without marking the main points. Now try READING them and
CONSIDERING them. They explain why, based on your arguments, you have to
assume that integer types also contain only approximations.

I'll quote the material you snipped to save you having to look it up:

| CBFalconer wrote:
|> Flash Gordon wrote:
|> .... snip ...
|>> I know of code which carefully uses doubles to do integer
|>> arithmetic, staying within the range where integers can be
|>> represented exactly, in order to use the greater range of exact
|>> integral values that a double can represent on that specific
|>> implementation than an int. In this case the stored doubles
|>> always have an exact number of pennies in them (well, it also
|>> uses exact numbers of other things).
|>
|> But now you are using extraneous information, beyond that held in
|> the FP value. You are using the fact that you know than only
|> integers have ever been stored. This is not intrinsic to the FP
|> value.
|
| Variables do NOT exist in isolation, not do values. They exist within
programs.
|
| You have snipped without addressing the following points:
|
| 1) By EXACTLY the same argument all integer types represent a range of
values (I gave examples of real situations where this applies)
|
| 2) The only way to determine the range of values represented, whether
it is stored as an integer or floating point, IS to use the additional
information and do an error analysis.
|
| I.e. WITHOUT performing an error analysis all you can do is say that a
variable may or may not represent a number somewhere on the complex
plain and the error may be infinite.
|
| I.e. the definition of the floating point model in C tels you NOTHING
about the range of numbers that any variable might represent.
|
| Another example
|
| double x = sin(11);
|
| Does the foating point model tell you what value x will contain?
| Given the value of x without knowing that it is the result of the sin
function, can you use the floating point model (and NOTHING else) to
derive a range that includes the mathematical value of sin(11) ?
|
| Just to give you a clue, the answer to BOTH questions is NO. If you
claims were true the answer to both questions would be yes.

You have also completely ignored the fact that I have presented
situations where the integer types *are* used as approximations.

So, is int just an approximation?

 

[Keith Thompson]

You do know the problem you were attempting to solve ...

And I know that not all real values can be stored in a floating-point
object. If the problem I'm trying to solve depends on doing so, that
it's not a problem I can solve using floating-point.

If I write:
double x = 1.0;
the value that's *supposed* to be stored in x is the value that *is*
stored in x, 1.0.

If I write:
double y = 1.0/3.0;
the value that's *supposed* to be stored in y is a close approximation
to the mathematical value one-third. My expectations are not always
entirely realistic, but they usually bear some resemblance to what's
actually possible.

 

[CBFalconer]

(s/konw/know/


Once again what gets stored (domain of representable values) has
little if any relation to what should have been stored (domain of
real numbers).

Perhap, but (a) how do you know what *should* have been stored* and
(b) we were discussing what actually *is* stored.

[snip]

Every new programmer should be taught this until it sinks in, then
they can take a class in numeric analysis and realize that any
floating point number in base 2 is always just one possibility out
of a range, that being from that number to the upper error bound
down to the number less the lower error bound. Then they will
understand one of the truths of the universe that if a floating
point number turns out to be correct it is a miracle and the counter
example to Murphy's law.

Or it's a result of careful programming and analysis.

double x = 1.0;

x contains exactly what I want it to. In this particular case, there
is no error.

Because you have examined the code, which includes that
initialization. I assume you have also investigated all function
calls between that initialization and the moment of interest to
ensure nothing has modified it. I am talking ONLY about what is
guaranteed by the value stored.

 

[CBFalconer]

.... snip ...

If I write:
double y = 1.0/3.0;
the value that's *supposed* to be stored in y is a close approximation
to the mathematical value one-third. My expectations are not always
entirely realistic, but they usually bear some resemblance to what's
actually possible.

That's fine. However I am willing to go further, and say that the
value range represented in y includes the exact value 1.0/3.0
(barring something foolish in the arithmetic system). I will even
say that that value is as close to 1.0/3.0 as it can ever become.

 

[Keith Thompson]

Pi may be irrational, but any algorithm in C will be calculating
rational approximations. At some point your rational approximation of
Pi will not be representable in the finite amount of memory available
for it to run.

Agreed -- assuming, of course, that you let the algorithm run
indefinitely.

It's also possible to have a representation for real numbers that can
represent pi exactly. A trivial and probably not very useful example
is:

struct Real {
_Bool this_is_pi
double value; /* ignored if this_is_pi is true */
};

but more sophisticated representations are possible. If you can
describe it, you can devise a way to represent it in C. (Manipulating
such values is another question.)

But any such representation can represent only finitely many real
values, even if some of them are transcendental (or at most countably
infinitely many if you're willing to accept arbitrarily long
sequences).

 

[Keith Thompson]

Keith Thompson wrote: [...]

You konw exactly what value was stored. (You don't necessarily know
how that value was computed.)

Once again, C99 6.2.4p2:

An object exists, has a constant address, and retains its
last-stored value throughout its lifetime.

And again, that last-stored 'value' is a range.

No, it is not a range, it is a single value.

If it were intended to be a range, surely the standard would say so in
5.2.4.2.2, "Characteristics of floating types <float.h>". That
section, particularly the first two paragraphs, defines C's model for
floating-point numbers. It uses the word "range" several times, but
never in reference to a stored value. The model in paragraph 2
defines a single value, not a range.

Have you read C99 5.2.4.2.2 paragraphs 1 and 2?

A followup question: Why not?

[snip]

 

[Ben Bacarisse]

Eric Sosman said:

[...] In particular rationals, reals,
integers can all be put in one to one correspondence with the set
of integers. [...]

Nonsense. The integers are 1-1 with the integers, and
the integers are 1-1 with the rationals. But the integers
are *not* 1-1 with the reals. Look up "diagonal argument,"
and try to refrain from posting about what you wot not.

Briefly, Cantor's diagonal argument runs as follows (although this
explanation is obviously subject to corrections by real
mathematicians!).

1) We assume that the reals are countable. That is, there may be
infinitely many of them, but they can be placed into one-to-one
correspondence with the integers. That is, we assume that CBF is
right. (This is known as reductio ad absurdum.)

2) We imagine a COMPLETE list L of the reals (an infinitely long
list, obviously, but it is complete in the sense that it contains
one entry for every integer - i.e. is in one-to-one correspondence
with the integers), in numerical order (actually any order will do,
but it may help to think of them as being ordered). Each list entry
corresponds to an integer - its position on the list. They are
lined up such that the first decimal place of each is in one
column, the next decimal place is in the next column, etc. We can
address the i'th entry as L, and the j'th decimal place of the
i'th number as L[j].

3) It is now easy to demonstrate that a real number exists that is
not on this (infinitely long) list:

for(i = 0; i < infinity; i++)
{
new = 9 - L;
}

This loop constructs a new real number that must be different from
each of the numbers in the list. When it eventually completes
(don't hold your breath), the number it has constructed is bound to
differ from every other number in the list by at least one position
(position i for the i'th real number on the list). We have
therefore demonstrated that the list is not complete. (And if we
add it to the list, we just run the loop again and come up with
another such number.) This contradicts our original assumption,
which is true if the reals are countable. Therefore, they are not.

There are some details missing (for example I think you are listing
the reals in [0,1] or there would be no left-most digit) but the main
one is why this argument does not apply to, say, the rationals.

The diagonal argument is subtle. It relies on the definition of the
reals to remove the possibility of such a list. If you don't say what
part of the argument is specific to the reals (and why) I think some
readers may get confused.

(It is that the reals are, almost by definition, closed under the
operation defined in step 3 but the rationals are not. Why they are
not is also not exactly obvious to most people.)

Incidentally, this is even more obvious in binary, with the slight
mod to the loop:

for(i = 0; i < infinity; i++)
{
new = 1 - L;
}

Actually it is harder to get the argument to work for binary
fractions. If you correct your construct in step 3 so that 0.9999
recurring is not a possibility[1], you will see that it is harder to pull
off the same trick in binary.

[1] One way is just to make the construct something like:

new = L == 2 ? 1 : 2;

but this trick won't wash in binary.

 

[CBFalconer]

Keith Thompson wrote: [...]

You konw exactly what value was stored. (You don't necessarily
know how that value was computed.)

Once again, C99 6.2.4p2:

An object exists, has a constant address, and retains its
last-stored value throughout its lifetime.

And again, that last-stored 'value' is a range.

No, it is not a range, it is a single value.

If it were intended to be a range, surely the standard would say
so in 5.2.4.2.2, "Characteristics of floating types <float.h>".
That section, particularly the first two paragraphs, defines C's
model for floating-point numbers. It uses the word "range"
several times, but never in reference to a stored value. The
model in paragraph 2 defines a single value, not a range.

Have you read C99 5.2.4.2.2 paragraphs 1 and 2?

Because they don't affect the argument. All stored FP values are
ranges. Note p.3:

[#3] Floating types may include values that are not
normalized floating-point numbers, for example subnormal
floating-point numbers (x!=0,e=emin,f1=0), infinities, and
NaNs.15) A NaN is an encoding signifying Not-a-Number. A
quiet NaN propagates through almost every arithmetic
operation without raising an exception; a signaling NaN
generally raises an exception when occurring as an
arithmetic operand.16)

which does not limit the anomalies to the given examples.

/--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

 

[CBFalconer]

.... snip ...

You have also completely ignored the fact that I have presented
situations where the integer types *are* used as approximations.

So, is int just an approximation?

No, although it may be so used. It is intended to handle integers,
and, except for division, the set of integers is closed under
elementary arithmetic. People are quite familiar with the idea
that a division results in a quotient and a remainder, under which
condition the integer set remains closed.

You can't make these statements about FP values.

 

[Keith Thompson]

Keith Thompson wrote: [...]

Have you read C99 5.2.4.2.2 paragraphs 1 and 2?

Because they don't affect the argument. All stored FP values are
ranges. Note p.3:

[#3] Floating types may include values that are not
normalized floating-point numbers, for example subnormal
floating-point numbers (x!=0,e=emin,f1=0), infinities, and
NaNs.15) A NaN is an encoding signifying Not-a-Number. A
quiet NaN propagates through almost every arithmetic
operation without raising an exception; a signaling NaN
generally raises an exception when occurring as an
arithmetic operand.16)

which does not limit the anomalies to the given examples.

So what? I don't see the word "range" in that paragraph, or anything
even vaguely implying that a stored floating-point value represents a
range.

 

[Dik T. Winter]

>
> Did you deliberately ignore the algebra I posted? It had - ex -
> ey, but recommended ignoring the term in ex*ey.

Did you deliberately ignore what I wrote? I wrote: "the bounds of the
range are *not* eps(x * y), but eps(x + y)". Sheesh.

 

[Guest]

Once again what gets stored (domain of representable values) has little if any
relation to what should have been stored (domain of real numbers).

who says real numbers "should" be stored? I can't afford an infinite
number of bits for each real number in my computation so I think
floating
point approximations of real numbers *should* be stored.

At least chuck seems to have a supporter now...

The standard permits an infinite amount of error.
bollocks

 For instance it permits zero
to be stored for the real number 1^-10^100,

that isn't infinity

however there are an infinite number
of real values between that number and zero hence infinite error!

a stupid way to define error. Error is usully defined as a range or a
distribution. In your world all physical meaurements of continuous
quantities have infinite error.

Things like distance, temperature, weight, volume, time...

Note that my
representation of the number is exact and uses 9 bytes.  C using base 2 in 16
bytes of a long double gets it infinitely wrong.  A slightly longer exact human
readable form is 1/googolplex or 12 bytes.

Every new programmer should be taught this until it sinks in,

then they can take a class in numeric analysis

perhaps you should. If you *have* taken one it was very strange one.

and realize that any floating point number in base 2
is always just one possibility out of a range, that being from that number to
the upper error bound down to the number less the lower error bound.  Then they
will understand one of the truths of the universe that if a floating point
number turns out to be correct it is a miracle and the counter example to
Murphy's law.

you are following the way of the chuck. Turn from this path.

 

[Doug Miller]

No, although it may be so used. It is intended to handle integers,
and, except for division, the set of integers is closed under
elementary arithmetic. People are quite familiar with the idea
that a division results in a quotient and a remainder, under which
condition the integer set remains closed.

You can't make these statements about FP values.

Please provide an example showing that the set of FP values is *not* closed
under elementary arithmetic.

 

[Eric Sosman]

Please provide an example showing that the set of FP values is *not* closed
under elementary arithmetic.

#include <float.h>
double x = 1.0;
double y = FLT_RADIX + 1.0;
double z = x / y;

... which is not to say the FP numbers aren't closed under
"FP arithmetic," but "FP arithmetic" is far from "elementary."

 

[user923005]

Please provide an example showing that the set of FP values is *not* closed
under elementary arithmetic.

#include <stdio.h>
#include <float.h>

int main(void)
{
double big0 = DBL_MAX;
const double big1 = DBL_MAX;
big0 += big1;
big0 -= big1;
printf("big0 = %f\n", big0);
return 0;
}
/*

big0 = 1.#INF00

Infinities and NANs are not floating point numbers:

"WG14/N1256 Committee Draft — Septermber 7, 2007 ISO/IEC 9899:TC3

3 In addition to normalized floating-point numbers ( f1 > 0 if x !=
0),
floating types may be able to contain other kinds of floating-point
numbers,
such as subnormal floating-point numbers (x != 0, e = emin, f1 = 0)
and
unnormalized floating-point numbers (x != 0, e > emin, f1 = 0), and
values
that are not floating-point numbers, such as infinities and NaNs. A
NaN is
an encoding signifying Not-a-Number. A quiet NaN propagates through
almost
every arithmetic operation without raising a floating-point
exception;
a signaling NaN generally raises a floating-point exception when
occurring
as an arithmetic operand.17)

Footnote 17) IEC 60559:1989 specifies quiet and signaling NaNs.
For implementations that do not support IEC 60559:1989, the terms
quiet
NaN and signaling NaN are intended to apply to encodings with similar
behavior."
*/

 

[CBFalconer]

Did you deliberately ignore what I wrote? I wrote: "the bounds of the
range are *not* eps(x * y), but eps(x + y)". Sheesh.

I don't know why you are changing the nomenclature, and ignoring
the statement. It has an error factor of "(1 - ex - ey - ex*ey)".
Note the sum and the product. The product is neglible. That is
not centered on xmy, but is the range on one side. Change the -
signs to + signs to get the opposite side.

Are we speaking the same language?

 

[CBFalconer]

:
.... snip ...


I'm sorry, but it seems to me that you are castigating cbf (in
itself quite the rage these days) quite unfairly. I know what he
is doing; he is deriving the extent of the bounds of the range of
x*y and showing that it is the same as the extent of the bounds
of x+y.

I didn't even do that. I just showed that the range bounds of x*y
could ignore the product of the individual range errors, and that
the sum of those errors was the important value.

 

[CBFalconer]

Keith Thompson wrote: [...]

Have you read C99 5.2.4.2.2 paragraphs 1 and 2?

Because they don't affect the argument. All stored FP values are
ranges. Note p.3:

[#3] Floating types may include values that are not
normalized floating-point numbers, for example subnormal
floating-point numbers (x!=0,e=emin,f1=0), infinities, and
NaNs.15) A NaN is an encoding signifying Not-a-Number. A
quiet NaN propagates through almost every arithmetic
operation without raising an exception; a signaling NaN
generally raises an exception when occurring as an
arithmetic operand.16)

which does not limit the anomalies to the given examples.

So what? I don't see the word "range" in that paragraph, or anything
even vaguely implying that a stored floating-point value represents a
range.

Values that have built in errors from the nominal means values that
are not normalized fp numbers. A number plus or minus an error
factor is a range. The built-in error factor is measured by the
appropriate epsilon.