Re: General pow(xx,yy) function in Motion 10
> From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
> To: "stds-1788" <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: Re: General pow(xx,yy) function in Motion 10
> Date: Sun, 6 Dec 2009 09:18:37 -0600
>
> Dan Zuras Intervals wrote:
> > On the contrary, the interval returned for pow(xx,yy)
> > WILL CONTRACT for each contraction of xx & yy.
> >
> > And no crash will occur on a correctly written program.
> >
> > It is just that it will not snap to any particular
> > manifold (positive or negative) until yy becomes a
> > singleton.
> >
> > Then there are two possibilities: Either the solution
> > you seek is contained within the remaining manifold
> > when the exponent becomes a singleton or it does not.
> >
> > If it does you will be able to identify it quite
> > narrowly in xx as well. If it does not then the
> > singleton is outside the desired solution space.
> >
>
> Dan, Michel,
>
> Thanks for the clarifications.
>
> Theoretically, I agree an infinite number of bisections in the domain will
> contract the range to a point. However, the best that can be done in a
> machine is to bisect the domain to a tiny interval with the width of exactly
> one ULP. If the endpoints of this tiny interval are large negative numbers,
> then the interval range will still be very, very large. In this case, the
> branch-and-bound algorithm will request the interval domain should be
> further bisected in order to contract the interval range. But this is no
> longer possible. So how does the user (or the machine) know which manifold
> the solution belongs to?
>
> Nate
Folks,
To answer Nate's question I will have to drift well
out of the topic of voting the merits of motion 10.
I apologise in advance & invite you to ignore my
remarks.
Nate,
Infinitely many bisections are not called for.
Indeed, you quote me but then edit out that portion
which contains the answer you seek.
Let me quote it back to you.
>
> But your point is well taken.
>
> If you know in advance that you seek a solution on a
> particular manifold, then it should be possible to
> track it down by an algorithm that contracts on that
> manifold alone.
>
> This is why I suggested two auxiliary functions should
> be added to the library. One for each manifold.
> Such functions would be able to narrowly contract on
> a solution on the desired manifold if it is known
> which manifold you seek.
>
> As it is too late to amend this motion to include
> those functions, perhaps you can propose them at
> a later date.
>
> Or I will propose them for you if you like.
>
> But they do not form a issue as to the merits of this
> motion except in so far as they would make things
> easier to do.
>
>
> Dan
>
>
> P.S. - BTW, if you CANNOT identify which manifold
> contains the solution you seek than the only pow
> that is guaranteed to contain the desired solution
> is the generalized pow. In this case, it is a lack
> of information in the problem statement that limits
> your knowledge of the solution, not a lack of skill
> in your technique for finding it.
There is a third alternative that might work for you.
Even if you don't know on which manifold the solution
lies, as soon as you know that negative xx is involved
you can bifurcate the search along the manifolds rather
than xx or yy.
Thus you will be able to find a narrow solution on the
positive manifold (if it exists) separately from a
distinct narrow solution on the negative manifold (if
it exists). The final solution will be the union of
the two.
I suggest that combined solution will be as wide as the
solution you would have found had you searched through
the combined space.
But neither of these things is the problem, really.
The problem is you are describing a search method that
seems to rely on roughly bifurcating the range space
when you bifurcate the domain space. Further, that
bifurcation is the preferred method of narrowing the
search space.
Neither are always true so a correctly written search
must not rely on them.
Indeed, a search method that relies on them will fail
under far more benign circumstances than those that
concern us here.
Take the simplest possible search conditions: I am
searching for a solution to f(xx) = cc. The width of
cc is rather narrow (or a singleton). In the relevant
domain of xx = [a,b], I know that f' is large, positive,
& fairly constant.
I think you will agree that these are remarkably benign
conditions.
Now, suppose I split xx into two disjoint pieces, xx1,
& xx2, such that xx = xx1 \union xx2 & xx1 \intersect
xx2 = [empty].
Even under these circumstances, I cannot count on f(xx1)
\intersect f(xx2) = [empty] being true.
And if cc \intersect f(xx1) \intersect f(xx2) is also
not empty, I cannot bisect xx in this manner as both
pieces contain part of the solution space.
And that's under benign conditions.
Now imagine things are subtly less benign. Suppose
eps is the smallest positive number you can represent.
Let c = eps^(1/3) (a relative large number). Suppose
f(x) = cubeRoot(x). And that we with to solve the
problem f(xx) = [-c/2,-c/3].
The problem statement is no where near any of the
boundaries of our numerical system. It is continuous.
It is monotonic. Indeed, in the neighborhood of our
desired solution f' is VERY large & positive. But it
is not constant.
Still, 754 arithmetic is such that, for a correctly
written cubeRoot, even for a large initial xx = [-1,1],
you will be able to narrow the domain right down to the
narrowest possible interval which is [-eps,0]. (This
is much larger than the actual solution but as narrow
a solution as can be represented.)
But in anything more complicated to evaluate than our
cubeRoot, you can't count on that being true. Given
that f' is nearly unbounded in this region, roundoff
error alone will expand the range of an interval such
that the boundaries of adjacent intervals will greatly
overlap when passed through such an f(xx).
In such a case, bifurcation will fail to narrow the
solution space as much as is expected & perhaps not
at all. Indeed, it might be true that one part of the
bifurcated interval will map to the same interval as
the whole, say f(xx2) = f(xx). Clearly, one cannot
bifurcate in this case.
A contractive map might still work well in this case, if
one exists. Indeed, it should be able to narrow the width
of a solution as much as possible (which might not be
very much). But it might take much more time, depending
on the nature of the contractive map.
In any event, this is a long winded way of saying that:
(1) the two auxiliary functions I suggested should also
be part of our library, (2) the problem you are
describing is shared by many much more benign functions
& is a problem of the solution method not the library
function, & (3) neither of them go to the merits of
motion 10.
Well, point (1) touches on it but that is easily repaired
at a later date.
Is all this reasonable?
Yours,
Dan