www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - float comparison gives wrong result in loop?

reply Bradley Smith <digitalmars-com baysmith.com> writes:
With the following code, why does the assert fail?

import std.stdio;

void main() {
	const float STEP_SIZE = 0.2f;
	
	float j = 0.0f;
	while (j <= ( 1.0f / STEP_SIZE)) {
		j += 1.0f;
		writefln(j <= ( 1.0f / STEP_SIZE));
	}
	assert(!(j <= ( 1.0f / STEP_SIZE)));
}

The loop exits early, but it should not. The result of
"j <= ( 1.0f / STEP_SIZE)" is somehow different in the while statement 
versus in the call to writefln.

Interestingly, if the code is optimized, the assert passes.

Is this a bug?

Thanks,
   Bradley
Sep 19 2006
next sibling parent reply Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Tue, 19 Sep 2006 01:42:51 -0700, Bradley Smith
<digitalmars-com baysmith.com> wrote:


With the following code, why does the assert fail?

import std.stdio;

void main() {
	const float STEP_SIZE = 0.2f;
	
	float j = 0.0f;
	while (j <= ( 1.0f / STEP_SIZE)) {
		j += 1.0f;
		writefln(j <= ( 1.0f / STEP_SIZE));
	}
	assert(!(j <= ( 1.0f / STEP_SIZE)));
}

The loop exits early, but it should not. The result of
"j <= ( 1.0f / STEP_SIZE)" is somehow different in the while statement 
versus in the call to writefln.

Interestingly, if the code is optimized, the assert passes.


There's a good chance that this is just an approximate arithmetic
issue.

1.0f / 0.2f is approximately 5.0f. It's approximate because this is
floating point arithmetic, and because 0.2 in particular cannot be
represented exactly in binary floating point.

The adding of 1.0f should be exact, since all whole numbers (up to
some rather large limit) can be represented precisely as binary
floats. So the incrementing will reach precisely 5.0.

Therefore, the comparison for <= may fail when writefln showns 5.0
(because it tends to round off for printing). You are comparing
exactly 5.0 with approximately 5.0, and the result depends on whether
'approximately 5.0' is slightly higher or lower.

All floating point arithmetic must be considered approximate. That's a
feature of floating point, irrespective of what programming language
you use. All comparisons of floating point results need to take this
into account. How you deal with it depends on what you are doing, but
a common approach is simply to allow the value to go over slightly.

For instance, start with j a very little bit below zero...

	float j = -0.00001f;

When the comparison is made against approximately 5.0, j will be
slightly lower than zero so the <= should still return true even if
'approximately 5.0' actually means 4.99999999999999.

Oh, and D does all floating point work at 80 bit precision, but saving
a result to a float variable cuts it down to 32 bit precision.
Optimising will affect how often this is done, and can cause slightly
different values to be seen at different points in the code.

-- 
Remove 'wants' and 'nospam' from e-mail.
Sep 20 2006
parent reply Bradley Smith <digitalmars-com baysmith.com> writes:
Steve Horne wrote:

 On Tue, 19 Sep 2006 01:42:51 -0700, Bradley Smith
 <digitalmars-com baysmith.com> wrote:
 

 With the following code, why does the assert fail?

 import std.stdio;

 void main() {
 	const float STEP_SIZE = 0.2f;
 	
 	float j = 0.0f;
 	while (j <= ( 1.0f / STEP_SIZE)) {
 		j += 1.0f;
 		writefln(j <= ( 1.0f / STEP_SIZE));
 	}
 	assert(!(j <= ( 1.0f / STEP_SIZE)));
 }

 The loop exits early, but it should not. The result of
 "j <= ( 1.0f / STEP_SIZE)" is somehow different in the while statement 
 versus in the call to writefln.

 Interestingly, if the code is optimized, the assert passes.


 
 There's a good chance that this is just an approximate arithmetic
 issue.


I understand that floating point arithmetic is approximate, but why is 
the result of the <= comparison different between the while statement 
and the writefln statement?

That they are different would imply that the comparison is not only 
approximate, but it is also non-deterministic. In other words, shouldn't 
"exactly 5.0 <= approx 5.0" always give the same result?

Thanks,
   Bradley
Sep 21 2006
parent Steve Horne <stephenwantshornenospam100 aol.com> writes:
On Thu, 21 Sep 2006 12:38:23 -0700, Bradley Smith
<digitalmars-com baysmith.com> wrote:


I understand that floating point arithmetic is approximate, but why is 
the result of the <= comparison different between the while statement 
and the writefln statement?


Actually, that's a good question. I didn't look at your example that
closely - thought you were printing the division result, not the
comparison result.

Could still be a wierd optimiser artifact. Consider...


 	while (j <= ( 1.0f / STEP_SIZE)) {
 		j += 1.0f;
 		writefln(j <= ( 1.0f / STEP_SIZE));




The use of j in writefln may be optimised - kept at full 80 bit
precision - where the reference in the while needs to get it back from
the variable.

Seems wrong, though - all-integer calculations should be exact even if
you do them in float variables.

Maybe the compiler spots the repeated ( 1.0f / STEP_SIZE) and
generates a float temporary, but doesn't use it on the return back to
the top of the loop, so the first use is 80 bit precision but the
second only 32 bit - spotting the sequential re-use but not pulling it
out of the loop for some reason.

But then, D is supposed to always use 80 bit precision temporaries, so
that seems wrong too.

Dunno. Maybe you'd need to look at the generated code for a full
explanation. But TBH, it's just the rule that you can't depend on
these things. Optimisation artifacts can create surprises. Things
should be deterministic, of course, but they may not be determined
quite the way that you'd expect.

-- 
Remove 'wants' and 'nospam' from e-mail.
Sep 21 2006
prev sibling parent reply Don Clugston <dac nospam.com.au> writes:
Bradley Smith wrote:

 With the following code, why does the assert fail?


[snip]


 The loop exits early, but it should not. The result of
 "j <= ( 1.0f / STEP_SIZE)" is somehow different in the while statement 
 versus in the call to writefln.
 Interestingly, if the code is optimized, the assert passes.


Are you sure? Haven't you just removed the assert?


 Is this a bug?


I'd say so. Inside while(), STEP_SIZE is a float constant.
In assert(), it's a real precision constant. The code below proves this.

In fact, given D's behaviour with floating-point constants, I don't even 
know why this line is legal:
     const float STEP_SIZE = 0.2f;
because it's not a float at all, it's a real.

-----

import std.stdio;

void main() {
     const float STEP_SIZE = 0.2f;

     float j = 0.0f;
     real q;
     while (j <=  ( 1.0f / STEP_SIZE)) {
         j += 1.0f;
         q = j;
         writefln("%a %a %a", q, j, ( 1.0f / STEP_SIZE));
         writefln(j <= ( 1.0f / STEP_SIZE));
     }
     float step2 = STEP_SIZE;

     assert(!(j <= ( 1.0f / step2))); // passes
     assert(!(j <= ( 1.0f / STEP_SIZE))); // fails!
}
Sep 21 2006
next sibling parent Bradley Smith <digitalmars-com baysmith.com> writes:
Don Clugston wrote:

 Bradley Smith wrote:

 With the following code, why does the assert fail?


 [snip]
 

 The loop exits early, but it should not. The result of
 "j <= ( 1.0f / STEP_SIZE)" is somehow different in the while statement 
 versus in the call to writefln.


  > Interestingly, if the code is optimized, the assert passes.
 
 Are you sure? Haven't you just removed the assert?


I don't think optimization removes asserts. Does it? If I'm wrong, that 
is an import fact to be aware of. However, if I insert "assert(false);", 
optimization doesn't remove it; so I assume asserts are not removed.



 import std.stdio;
 
 void main() {
     const float STEP_SIZE = 0.2f;
 
     float j = 0.0f;
     real q;
     while (j <=  ( 1.0f / STEP_SIZE)) {
         j += 1.0f;
         q = j;
         writefln("%a %a %a", q, j, ( 1.0f / STEP_SIZE));
         writefln(j <= ( 1.0f / STEP_SIZE));
     }
     float step2 = STEP_SIZE;
 
     assert(!(j <= ( 1.0f / step2))); // passes
     assert(!(j <= ( 1.0f / STEP_SIZE))); // fails!
 }


That is a very interesting twist. I wouldn't expect that using a 
variable would be different than a constant. Can someone explain this?

Thanks,
   Bradley
Sep 21 2006
prev sibling parent Bradley Smith <digitalmars-com baysmith.com> writes:
 import std.stdio;
 
 void main() {
     const float STEP_SIZE = 0.2f;
 
     float j = 0.0f;
     real q;
     while (j <=  ( 1.0f / STEP_SIZE)) {
         j += 1.0f;
         q = j;
         writefln("%a %a %a", q, j, ( 1.0f / STEP_SIZE));
         writefln(j <= ( 1.0f / STEP_SIZE));
     }
     float step2 = STEP_SIZE;
 
     assert(!(j <= ( 1.0f / step2))); // passes
     assert(!(j <= ( 1.0f / STEP_SIZE))); // fails!
 }


After some research, I can now explain this last part. Because of 
compile-type evaluation of const values, the second statement is effectively
   cast(real) j <= cast(real)(1.0f / STEP_SIZE)

However the first is effectively
   cast(real) j <= (cast(real) 1.0f / cast(real) step2)

which when printed with
   writefln("%a <= %a", cast(real)j, cast(real)1.0f / cast(real)step2);
gives
   0x1.4p+2 <= 0x1.3fffffb0000014p+2

Unfortunately, this still does not explain why the loop doesn't print 
"false" before exiting.
Sep 21 2006