Always false float comparisons

Timon Gehr via Digitalmars-d digitalmars-d at puremagic.com
Sat May 21 07:38:20 PDT 2016


On 20.05.2016 13:32, Joakim wrote:
> 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.
> ...

High precision is usually good (use high precision, up to arbitrary 
precision or even symbolic arithmetic whenever it improves your results 
and you can afford it). *Implicitly* increasing precision during CTFE is 
bad. *Explicitly* using higher precision during CTFE than at running 
time /may or may not/ be good. In case it is good, there is often no 
reason to stop at 80 bits.

>>> 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?

Because that's the most direct way to go from that example to one where 
implicit precision enhancement during CTFE only is bad.

> 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?
> ...

Walter's request wasn't specifically about that, and it's the first 
thing I came up with:

 > On 17.05.2016 23:07, Walter Bright wrote:
>> I'd like to see an example of double rounding "completely defeating" an
>> algorithm,

I don't have infinite amounts of time. The (significant) time spent 
writing up all of this competes with time spent doing things that are 
guaranteed to yield (often immediate) tangible benefits.


> 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,

What's "right" about them? That the compiler will not implicitly 
transform some of them to even higher precision in order to break the 
algorithm again? (I don't think that is even guaranteed.)

> you don't seem to have a point at all.
> ...

Be assured that I have a point. If you spend some time reading, or ask 
some constructive questions, I might be able to get it across to you. 
Otherwise, we might as well stop arguing.

>>>>> 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.
> ...

If I may ask, how much mathematics have you been exposed to?


>>>> 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 I argue in the abstract, people request examples. If I provide 
examples, people complain that they are too specific.

> If you're going to all that
> trouble, you should know not to blindly run the same code at compile-time.
> ...

The point of CTFE is to be able to run any code at compile-time that 
adheres to a well-defined set of restrictions. Not using floating point 
is not one of them.

>>> 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?
>

I don't think further explanations are required here. Maybe be more 
careful next time.

>>> 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.

Thanks!

> But as long as the way CTFE extending precision is
> consistently done and clearly communicated,

It never will be clearly communicated to everyone and it will also hit 
people by accident who would have been aware of it.

What is so incredibly awesome about /implicit/ 80 bit precision as to 
justify the loss of control? If I want to use high precision for certain 
constants precomputed at compile time, I can do it just as well, 
possibly even at more than 80 bits such as to actually obtain accuracy 
up to the last bit.

Also, maybe I will need to move the computation to startup at runtime 
some time in the future because of some CTFE limitation, and then the 
additional implicit gain from 80 bit precision will be lost and cause a 
regression. The compiler just has no way to guess what precision is 
actually needed for each operation.

> those people can always opt out and do it some other way.
> ...

Sure, but now they need to _carefully_ maintain different 
implementations for CTFE and runtime, for an ugly misfeature. It's a 
silly magic trick that is not actually very useful and prone to errors.




More information about the Digitalmars-d mailing list