You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Gilles Sadowski <gi...@harfang.homelinux.org> on 2011/11/16 14:28:38 UTC
[Math] x + h - x != h
Hi.
As per an advice in a well-known book (that one should not cite): In order
to compute a numerical approximation to the derivative:
f'(x) ~ [ f(x + h) - f(x) ] / h
the "h" should be a number representable in the set of floating point
numbers being used (e.g. "double").
It seems that a code like
---CUT---
final double delta = x + h - x;
final double deriv = (f.value(x + delta) - f.value(x)) / delta;
---CUT---
would be the simplest thing to do.
Besides
x + delta - x
being strange-looking and running the risk of being manually (and
incorrectly) changed to just
delta
the reference (not) cited above suggests to use a two- or three-steps
procedure to ensure that some optimizing compiler will not do the same:
---CUT---
double sum = x + delta;
dummy(sum); // function "dummy" does nothing.
delta = sum - x;
---CUT---
Thus, I initially intended to add a utility method in "MathPrecision":
---CUT---
public static double representableDelta(double x,
double originalDelta) {
final long sum = Double.doubleToLongBits(x + originalDelta);
final double delta = Double.longBitsToDouble(sum) - x;
return delta;
}
---CUT---
assuming that it is sufficiently "complicated" to evade the "smartest" JIT
compiler.
Then, I also implemented the simple thing:
---CUT---
public static double representableDelta2(double x,
double originalDelta) {
return x + originalDelta - x;
}
---CUT---
Remarkably (or not), a trivial unit test (10^8 random delta values) did not
find an occurrence where the returned values from one or the other method
would differ.
I think that the utility would be a useful addition to CM, if just to draw
attention to the issue of accuracy in numerical derivatives[1], but I wonder
whether the simple implementation is ensured to always work: I.e. does a rule
exist that states that no optimization may ever be perfomed to simplify
"x + delta - x" into "delta"?
Any thoughts? (even if only for a better name...)
Gilles
[1] A better way would have been to have the numerical derivatives framework
that someone had promised to contribute a few months ago...
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] x + h - x != h
Posted by Sébastien Brisard <se...@m4x.org>.
> Try -XX:+PrintOptoAssembly
>
> See here:
>
> http://stackoverflow.com/questions/1551781/how-can-i-see-the-code-that-hotspot-generates-after-optimizing
>
> and here:
> http://weblogs.java.net/blog/kohsuke/archive/2008/03/deep_dive_into.html
>
>
> Thanks for these links, they are quite interesting. Will give it a go!
Re: [Math] x + h - x != h
Posted by Ted Dunning <te...@gmail.com>.
Try -XX:+PrintOptoAssembly
See here:
http://stackoverflow.com/questions/1551781/how-can-i-see-the-code-that-hotspot-generates-after-optimizing
and here:
http://weblogs.java.net/blog/kohsuke/archive/2008/03/deep_dive_into.html
2011/11/17 Sébastien Brisard <se...@m4x.org>
> Hi,
>
> Also, it is clear that (x+delta) - x != delta for
> > some values of delta so I doubt that the optimization happens.
> >
> >
> Is there a specification where this is clearly stated ? I am actually
> strugggling to find what kind of optimizations are performed by --say--
> Oracle's JVM. One reason for this would be this issue, another would be: is
> it possible to write the code in a way that would "help" the JIT (for
> example to remove array bounds checks, and so on). If anyone could share
> any hint about this, I would be grateful.
>
> Regarding Gilles's issue. If we were to define a private *class variable*
> called dummy, then I think the JIT would *have to compute* dummy
> {code}
> dummy = x + h;
> h = dummy - x;
> {code}
>
> Now, this is not a perfect solution, because for the proposed (static)
> method representableDelta, the class variable dummy woud need to be static
> as well, which I think raises thread-safety issues? Do you think a solution
> can be worked along those lines?
>
> Thank you beforehand,
> Sébastien
>
Re: [Math] x + h - x != h
Posted by Sébastien Brisard <se...@m4x.org>.
Hi,
Also, it is clear that (x+delta) - x != delta for
> some values of delta so I doubt that the optimization happens.
>
>
Is there a specification where this is clearly stated ? I am actually
strugggling to find what kind of optimizations are performed by --say--
Oracle's JVM. One reason for this would be this issue, another would be: is
it possible to write the code in a way that would "help" the JIT (for
example to remove array bounds checks, and so on). If anyone could share
any hint about this, I would be grateful.
Regarding Gilles's issue. If we were to define a private *class variable*
called dummy, then I think the JIT would *have to compute* dummy
{code}
dummy = x + h;
h = dummy - x;
{code}
Now, this is not a perfect solution, because for the proposed (static)
method representableDelta, the class variable dummy woud need to be static
as well, which I think raises thread-safety issues? Do you think a solution
can be worked along those lines?
Thank you beforehand,
Sébastien
Re: [Math] x + h - x != h
Posted by Ted Dunning <te...@gmail.com>.
On Wed, Nov 16, 2011 at 8:19 AM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> On Wed, Nov 16, 2011 at 07:52:27AM -0800, Ted Dunning wrote:
> > The JVM is likely to in-line dummy, realize it does nothing and then
> > coalesce your other code.
> >
> > It isn't any wonder that this produces the same results.
>
> I'm not sure I understand what you mean: Does "coalesce" means that
> x + delta - x
> will be equal to
> delta
> ?
>
No. Just that the in-lined code will disappear.
I don't think that the JIT is naive enough to simplify away the subtraction.
> The issue is whether an optimization could do that transformation.
>
If there are cases where IEEE FP arithmetic allows
x + delta - x != delta
then the optimization should not happen. Obviously, if x is NaN or
infinite, this holds. Also, it is clear that (x+delta) - x != delta for
some values of delta so I doubt that the optimization happens.
[Note that I did not implement any "dummy" function but rather called the
> quite non-dummy "doubleToLongBits" and "longBitsToDouble".]
>
If you didn't actually use the results, then it will disappear. If you
called the java.math routines to do this, then those may be known to be
inverses and disappear as well. If you called your own implementations and
actually use the bits, then it will probably survive.
Re: [Math] x + h - x != h
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Wed, Nov 16, 2011 at 07:52:27AM -0800, Ted Dunning wrote:
> The JVM is likely to in-line dummy, realize it does nothing and then
> coalesce your other code.
>
> It isn't any wonder that this produces the same results.
I'm not sure I understand what you mean: Does "coalesce" means that
x + delta - x
will be equal to
delta
?
The issue is whether an optimization could do that transformation.
[Note that I did not implement any "dummy" function but rather called the
quite non-dummy "doubleToLongBits" and "longBitsToDouble".]
Gilles
> On Wed, Nov 16, 2011 at 5:28 AM, Gilles Sadowski <
> gilles@harfang.homelinux.org> wrote:
>
> > Besides
> > x + delta - x
> > being strange-looking and running the risk of being manually (and
> > incorrectly) changed to just
> > delta
> > the reference (not) cited above suggests to use a two- or three-steps
> > procedure to ensure that some optimizing compiler will not do the same:
> > ---CUT---
> > double sum = x + delta;
> > dummy(sum); // function "dummy" does nothing.
> > delta = sum - x;
> > ---CUT---
> >
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] x + h - x != h
Posted by Ted Dunning <te...@gmail.com>.
The JVM is likely to in-line dummy, realize it does nothing and then
coalesce your other code.
It isn't any wonder that this produces the same results.
On Wed, Nov 16, 2011 at 5:28 AM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> Besides
> x + delta - x
> being strange-looking and running the risk of being manually (and
> incorrectly) changed to just
> delta
> the reference (not) cited above suggests to use a two- or three-steps
> procedure to ensure that some optimizing compiler will not do the same:
> ---CUT---
> double sum = x + delta;
> dummy(sum); // function "dummy" does nothing.
> delta = sum - x;
> ---CUT---
>