Always false float comparisons

Fri May 20 04:32:53 PDT 2016

On Friday, 20 May 2016 at 11:02:45 UTC, Timon Gehr wrote:
> On 20.05.2016 11:14, Joakim wrote:
>> 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.
>
> Yes. That's absolutely obvious, and I have noted it before, but 
> thanks. Maybe try to understand why this problem occurs in the 
> first place.

Yet you're the one arguing against increasing precision 
everywhere in CTFE.

>> 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);
>> ...
>
> This example wasn't specifically about CTFE, but just imagine 
> that only part of the computation is done at CTFE, all local 
> variables are transferred to runtime and the computation is 
> completed there.

Why would I imagine that?  And this whole discussion is about 
what happens if you change the precision of all variables to real 
when doing CTFE, so what's the point of giving an example that 
isn't "specifically" about that?

And if any part of it is done at runtime using the algorithms you 
gave, which you yourself admit works fine if you use the right 
higher-precision types, you don't seem to have a point at all.

>>>> 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.
>> ...
>
> How do you even define accuracy if you don't specify an 
> infinitely precise reference result?

There is no such thing as an infinitely precise result.  All one 
can do is compute using even higher precision and compare it to 
lower precision.

>>> 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? ;)
>
> No. That paper uses multiple doubles per approximated real 
> value to implement arithmetic that is more precise than using 
> just plain doubles. If any bit in the first double is off, this 
> is no better than using a single double.
>
>> I skimmed it and that paper
>> explicitly talks about error bounds all over the place.
>
> It is enough to read the abstract to figure out what the 
> problem is. This demonstrates a non-contrived case where CTFE 
> using enhanced precision throughout can break your program. 
> Compute something as a double-double at compile-time, and when 
> it is transferred to runtime you lose all the nice extra 
> precision, because bits in the middle of the (conceptual) 
> mantissa are lost.

That is a very specific case where they're implementing 
higher-precision algorithms using lower-precision registers.  If 
you're going to all that trouble, you should know not to blindly 
run the same code at compile-time.

>> The only mention of "the last bit" is
>
> This part is actually funny. Thanks for the laugh. :-)
> I was going to say that your text search was too naive, but 
> then I double-checked your claim and there are actually two 
> mentions of "the last bit", and close by to the other mention, 
> the paper says that "the first double a_0 is a double-precision 
> approximation to the number a, accurate to almost half an ulp."

Is there a point to this paragraph?

>> 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.
>> ...
>
> Nothing "ironic" about that. It is sometimes a good idea and I 
> can do this explicitly and make sure the rounding is done 
> correctly, just like they did. Also, it is a lot more flexible 
> if I can specify the exact way the computation is done and the 
> result is rounded. 80 bits might not be enough anyway. There is 
> no reason for the language to apply potentially incorrect "hand 
> holding" here.
>
> Again, please understand that my point is not that lower 
> precision is better. My point is that doing the same thing in 
> every context and allowing the programmer to specify what 
> happens is better.

I understand your point that sometimes the programmer wants more 
control.  But as long as the way CTFE extending precision is 
consistently done and clearly communicated, those people can 
always opt out and do it some other way.

>>>> 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 used
>>> lower precision than requested).
>>
>> I'm not the one with the problem, you're the one complaining.
>> ...
>
> So you see no problem with my requested semantics for the 
> built-in floating point types?

I think it's an extreme minority use case that may not merit the 
work, though I don't know how much work it would require.  
However, I also feel that way about Walter's suggested move to 
128-bit CTFE, as dmd is x86-only anyway.