Always false float comparisons

[Joakim via Digitalmars-d]

On Thursday, 19 May 2016 at 18:22:48 UTC, Timon Gehr wrote:
> On 19.05.2016 08:04, Joakim wrote:
>> On Wednesday, 18 May 2016 at 17:10:25 UTC, Timon Gehr wrote:
>>> It's not just slightly worse, it can cut the number of useful 
>>> bits in
>>> half or more! It is not unusual, I have actually run into 
>>> those
>>> problems in the past, and it can break an algorithm that is 
>>> in Phobos
>>> today!
>>
>> I wouldn't call that broken.  Looking at the hex output by 
>> replacing %f
>> with %A in writefln, it appears the only differences in all 
>> those
>> results is the last byte in the significand.
>
> Argh...
>
> // ...
>
> void main(){
>     //double[] data=[1e16,1,-9e15];
>     import std.range;
>     double[] data=1e16~repeat(1.0,100000000).array~(-9e15);
>     import std.stdio;
>     writefln("%f",sum(data)); // baseline
>     writefln("%f",kahan(data)); // kahan
>     writefln("%f",kahanBroken(data)); // broken kahan
> }
>
>
> dmd -run kahanDemo.d
> 1000000000000000.000000
> 1000000100000000.000000
> 1000000000000000.000000
>
> dmd -m32 -O -run kahanDemo.d
> 1000000000000000.000000
> 1000000000000000.000000
> 1000000000000000.000000
>
>
> Better?
>
> Obviously there is more structure in the data that I invent 
> manually than in a real test case where it would go wrong. The 
> problems carry over though.

I looked over your code a bit.  If I define sum and c as reals in 
"kahanBroken" at runtime, this problem goes away.  Since that's 
what the CTFE rule is actually doing, ie extending all 
floating-point to reals at compile-time, I don't see what you're 
complaining about.  Try it, run even your original naive 
summation algorithm through CTFE and it will produce the result 
you want:

enum double[] ctData=[1e16,1,-9e15];
enum ctSum = sum(ctData);
writefln("%f", ctSum);

>> As Don's talk pointed out,
>> all floating-point calculations will see loss of precision 
>> starting there.
>> ...
>
>
> This is implicitly assuming a development model where the 
> programmer first writes down the computation as it would be 
> correct in the real number system and then naively replaces 
> every operation by the rounding equivalent and hopes for the 
> best.

No, it is intrinsic to any floating-point calculation.

> It is a useful rule if that is what you're doing. One might be 
> doing something else. Consider the following paper for an 
> example where the last bit in the significant actually carries 
> useful information for many of the values used in the program.
>
> http://www.jaist.ac.jp/~s1410018/papers/qd.pdf

Did you link to the wrong paper? ;) I skimmed it and that paper 
explicitly talks about error bounds all over the place.  The only 
mention of "the last bit" is when they say they calculated their 
constants in arbitrary precision before rounding them for runtime 
use, which is ironically similar to what Walter suggested doing 
for D's CTFE also.

>> In this case, not increasing precision gets the more accurate 
>> result,
>> but other examples could be constructed that _heavily_ favor 
>> increasing
>> precision.
>
> Sure. In such cases, you should use higher precision. What is 
> the problem? This is already supported (the compiler is not 
> allowed to use lower precision than requested).

I'm not the one with the problem, you're the one complaining.

>> In fact, almost any real-world, non-toy calculation would
>> favor it.
>>
>> In any case, nobody should depend on the precision out that 
>> far being
>> accurate or "reliable."
>
>
> IEEE floating point has well-defined behaviour and there is 
> absolutely nothing wrong with code that delivers more accurate 
> results just because it is actually aware of the actual 
> semantics of the operations being carried out.

You just made the case for Walter doing what he did. :)