Re: General pow(xx,yy) function in Motion 10
Dan, Nate, and all,
Do I understand the issue is, "If xx includes negative values, what is the
correct answer?" If yy is rational with an odd denominator, the answer is
fundamentally different from yy rational with an even denominator?
If I miss the point, please get me back on track.
If that is essentially the issue, I wonder whether it is a question worth
answering at all? Whenever my engineering colleagues want to irritate me,
they observe that, outside of pure mathematics (implying irrelevance), NO
number is accurate to single precision. In most applications, we are lucky
to know 3 digits. By implication, all intervals are thick.
If we accept their "all intervals are thick" assertion, all yy include both
odd and even denominators. What does that imply about the proper
interpretation? Of have you told me, but I did not get it?
Dr. George F. Corliss
Electrical & Computer Engineering
Haggerty Engineering #296
Marquette University
P.O. Box 1881
1515 W. Wisconsin Ave.
Milwaukee WI 53201-1881
George.Corliss@xxxxxxxxxxxxx
414-288-6599; -288-4400 (GasDay); -288-5579 (Fax)
Www.eng.mu.edu/corlissg
On 12/6/09 2:50 PM, "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx>
wrote:
>> 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