Re: General pow(xx,yy) function in Motion 10
Corliss, George wrote:
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?
I don't think its an issue of proper interpretation, e.g., I would also
agree with the idea that "all intervals are thick" for the reasons you
mention.
I also have been and continue to be impressed with Dan's mathematical
prowess on this topic! :-)
My concern is purely practical.
Interval branch-and-bound algorithms depend on the idea that any bisection
in the domain (xx,yy) of a function pow(xx,yy)=zz will cause the interval
range zz to become more narrow. Theoretically, if xx and yy are bisected
down to a point, then pow(xx,yy)=zz is also a point (nested intervals
theorem) or, perhaps undefined.
Strictly speaking, the general interval power function satisfies this
property (which is a good thing). So please don't confuse that I am
concerned about or criticizing that.
The trouble is that even as the width of xx and yy decreases, the range zz
will not decrease nearly as fast. This is because general power function
must contain both the positive and negative manifolds when xx is negative;
and for large negative values of x the distance between the two manifolds is
quite big. So the width of zz will always be at least this distance.
So very little progress is made narrowing zz for extraordinary amounts of
effort bisecting xx and yy. As Dan mentions, it will not be until yy is
bisected to a singleton value that any significant progress narrowing zz can
occur, since only after yy becomes a singleton do we know which manifold
does the solution belong to. Hence, the width of zz will suddenly shrink by
many, many, many orders of magnitude because it no longer must contain false
solution values from the other manifold.
BUT THE PROBLEM is that in finite precision, it will never be possible to
bisect yy into a singleton. At the very best, BOTH xx and yy will always be
an interval of at least 1 ULP (assuming the user input non-singleton
values). This means the width of zz will still be many, many, many orders of
magnitude larger than 1 ULP because it must contain possible solutions on
both manifolds.
Compare this to the other required library routines in motion 10 when the
input intervals are only 1 ULP wide: the interval range will usually be only
a few ULPS, too.
Now, it is usually not the case that an interval branch-and-bound algorithm
should ever need to bisect the input domain down to 1 ULP intervals. This is
because, as George mentions, "intervals are thick." In other words, users
typically only need to contain a few decimal digits in the tolerance of
their answers.
With all the library functions in motion 10 *except* general power, a
plain-vanilla branch-and-bound algorithm (the kind I suspect a student would
write in an introductory interval course) will easily terminate long before
bisecting the interval domains down to 1 ULP.
With the general power function, however, the width of the interval range zz
will always be at least the distance between the two manifolds for any
negative xx. This distance is quite large and will most likely be much
larger than the user's tolerance criteria for the branch and bound
algorithm. If there is no exception handling, the branch-and-bound algorithm
will get stuck in an infinite loop and crash. If exception handling is used
to prevent the stack-overflow, there still is no way for the user (or
machine) to know what the solution is.
So this is what I'm trying to understand about the general interval power
function: if no finite amount of bisection effort in the input domain will
identify which manifold the solution belongs to, what use is it?
I hope I am adding clarity to the discussion, not confusion.
Sincerely,
Nate