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.
