fractions and floating point

[Steffen]

Hi,

is it possible to have two fractions, which (mathematically) have the
order a/b < c/d (a,b,c,d integers), but when (correctly) converted into
floating point representation just have the opposite order?

The idea is that the two fractions are almost identical and that the
error introduced by going to floating point representation is bigger
than the exact difference, but different for the two fractions such that
it somehow turns them around.

I tried some numbers, but so far it always was ok.

I know that this depends on the way floating points are represented, so
the more precise question would be: is there a standard that would
ensure that this never happens? Does somebody have a concrete example
for a specific platform?

Thanks
Steffen

[Allan Bruce]

"Steffen" <s.*********@gmx.de> wrote in message
news:3j************@news.dfncis.de...

Hi,

is it possible to have two fractions, which (mathematically) have the
order a/b < c/d (a,b,c,d integers), but when (correctly) converted into
floating point representation just have the opposite order?

The idea is that the two fractions are almost identical and that the error
introduced by going to floating point representation is bigger than the
exact difference, but different for the two fractions such that it somehow
turns them around.

I tried some numbers, but so far it always was ok.

I know that this depends on the way floating points are represented, so
the more precise question would be: is there a standard that would ensure
that this never happens? Does somebody have a concrete example for a
specific platform?

Thanks
Steffen

It can't happen, if you think about it, the worst that can come out of this
is that the numbers come out equal but if you have x=a/b, and y=c/d, and
mathematically x<y then you cannot get x>y but you may get x==y.

Allan

[Dik T. Winter]

In article <3j************@news.dfncis.de> Steffen <s.*********@gmx.de> writes:

Hi,

is it possible to have two fractions, which (mathematically) have the
order a/b < c/d (a,b,c,d integers), but when (correctly) converted into
floating point representation just have the opposite order? .... I know that this depends on the way floating points are represented, so
the more precise question would be: is there a standard that would
ensure that this never happens? Does somebody have a concrete example
for a specific platform?

The IEEE floating point standard guarantees it. Both a/b and c/d should
be represented as the nearest floating point number, with determined
logic when there is a tie. So while you can have a/b == c/d in
floating point you will not get that a/b > c/d.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Lawrence Kirby]

On Thu, 14 Jul 2005 11:32:22 +0200, Steffen wrote:

Hi,

is it possible to have two fractions, which (mathematically) have the
order a/b < c/d (a,b,c,d integers), but when (correctly) converted into
floating point representation just have the opposite order?
They don't have to be integers, but we'll need to assume that we are
talking about values that are exactly representable in the floating point
type (i.e. there is no approximation step before the division takes
place). This isn't the case for all integers in the range of representable
values of a floating point type.
The idea is that the two fractions are almost identical and that the
error introduced by going to floating point representation is bigger
than the exact difference, but different for the two fractions such that
it somehow turns them around.
The property you want isn't guaranteed by C, but it may well be guaranteed
by IEEE 754 floating point arithmetic. It does follow when inexact
results are always rounded to the nearest representable floating point
value ***when using a consistent precision***. However C allows
intermediate results to be evaluated at a higher precision than the
underlying type represents, and this doesn't have to be consistent. So a/b
could in theory be evaluated at a different precision to c/d, and the
differing rounding that results could cause the ordering to be broken.
I tried some numbers, but so far it always was ok.

I know that this depends on the way floating points are represented, so
the more precise question would be: is there a standard that would
ensure that this never happens? Does somebody have a concrete example
for a specific platform?

The trouble is that this is VERY dependent on the architecture and the
specific code that the compiler generates. For example on x86 systems
FPU registers are 80 bits (although this is settable) and float and double
values tend to be calcuated and held at a higher precision in registers
than when they are stored in memory. So if the compiler decides to store
one intermediate result in memory but not the other the problem can occur.

Lawrence

[websnarf]

Steffen wrote:

is it possible to have two fractions, which (mathematically) have the
order a/b < c/d (a,b,c,d integers), but when (correctly) converted into
floating point representation just have the opposite order?
Well, a/b > c/d could not be the calculated result (since rounding is
consistent). However, obviously massive underflow can cause a/b == c/d
(==0). Also if one of your calculations becomes a NaN or both become
inf, then this may change the sense of the comparison in ways you
didn't intend.
The idea is that the two fractions are almost identical and that the
error introduced by going to floating point representation is bigger
than the exact difference, but different for the two fractions such that
it somehow turns them around.

I tried some numbers, but so far it always was ok.

I know that this depends on the way floating points are represented, so
the more precise question would be: is there a standard that would
ensure that this never happens? Does somebody have a concrete example
for a specific platform?

IEEE 754 is the only seriously recognized floating point specification.
More that likely your system uses and supports it.

--
Paul Hsieh
http://www.pobox.com/~qed
http://bstring.sf.net/

[Christian Bau]

In article <3j************@news.dfncis.de>,
Steffen <s.*********@gmx.de> wrote:

Hi,

is it possible to have two fractions, which (mathematically) have the
order a/b < c/d (a,b,c,d integers), but when (correctly) converted into
floating point representation just have the opposite order?

It depends on the quality of your arithmetic.

Using IEEE754 arithmetic, the result of an operation is the
mathematically exact result, correctly rounded. So if a/b < c/d
mathematically, and a, b, c, d can be converted to double without
rounding error (no 64 bit numbers), then (double) a / (double) b <=
(double) c / (double) d.

BUT it is allowed that an implementation sometimes uses more precision
than required. And then things go wrong. For example, many Intel
processors can use 64 bit and 80 bit floating point numbers. It can
happen that a/b is rounded to 64 bits, and c/d is rounded to 80 bits. In
that case a/b might be rounded up, while c/d is rounded down, so the
result of a/b might be greater than the result of c/d.