| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
P1788,
Motion 10 Elementary Functions PASSES
Yes - 43; No - 1; Needed for quorum: 36
The motion is listed in the attachment to this message.
George Corliss, P1788 Voting Tabulator
Here are comments received. I gather them all here for ease of reference,
especially by the Technical Editor, in case these comments can assist
further progress.
------ Forwarded Message
From: Michel Hack <hack@xxxxxxxxxxxxxx>
Date: Wed, 2 Dec 2009 08:30:26 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Motion P1788/M0010.22:ElementaryFunctions: YES
I vote YES on Motion 10 version 2.2 -- including the general "pow"
function as amended by Stefan. (I assume "\exists 0<y \in yy" means
that the exponent yy contains strictly positive points, as "there
exists a 0 less than y \in yy" makes no sense.)
------ Forwarded Message
From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Reply-To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 12:10:54 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Motion P1788/M0010.22: ElementaryFunctions: NO
NO
The value of a general power function for floating-point seems clear to me,
but I am a little skeptical of its value for interval computing. Mostly, the
idea it returns bounds not of a single function but of a family of functions
is a hard pill for me to swallow. If someone could provide practical
examples of why it is required, I would change my vote to YES. Otherwise I
think it should be removed and pow(x,y) given its traditional definition
exp(y*ln(x)); then I would change my vote to YES. I would also vote YES if
rootn(x,n) and powr(x,m,n) were required to complement pown(x,n).
On a separate topic, if there was enough interest in P1788 to require sign,
ceil, floor, nint, and trunc in a separate follow-up motion, I would vote
YES for that, too.
Sincerely,
Nate Hayes
------ Forwarded Message
From: Michel Hack <hack@xxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 12:34:31 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: General pow(xx,yy) function in Motion 10
Nate Hayes voted NO because of the inclusion of that function:
> The value of a general power function for floating-point seems clear
> to me, but I am a little skeptical of its value for interval computing.
> Mostly, the idea it returns bounds not of a single function but of a
> family of functions is a hard pill for me to swallow.
The general pow() function as proposed by Dan Zuras is not a conflation
of the family of rational-exponent functions -- though I agree that it
can be looked at this way, being defined by extending the concept of
completion-by-continuity to a set of values (in this case, two points
of equal magnitude but opposite signs). The real-positive function
with arbitrary-real exponent traditional pow() function then follows
naturally.
> If someone could provide practical examples of why it is required,
> I would change my vote to YES.
If the argument xx of pow(xx,yy) extends slightly into negative territory
due to earlier outward rounding, the result would also simply extend
slightly into negative territory, instead of having to raise an Undefined
decoration.
I do see an issue however in the case where yy is a singleton, because
that is now an exponent with an even denominator (in both decimal and
binary) if it has a non-zero fractional part. Dan's reasoning does not
apply to this case, and it would be necessary to raise "Undefined" if xx
contains negative points.
Whether that issue is a problem is a matter of perception.
Michel.
P.S. Perhaps we should push for a floating-point format with an odd base;
that would also eliminate all those annoying tie-break situations...
------ Forwarded Message
From: "Hossam A. H. Fahmy" <hfahmy@xxxxxxxxxxxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 14:26:26 -0600
To: Michel Hack <hack@xxxxxxxxxxxxxx>
Cc: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
While explaining the uses of the general pow(xx, yy) Michel Hack said:
> I do see an issue however in the case where yy is a singleton, because
> that is now an exponent with an even denominator (in both decimal and
> binary) if it has a non-zero fractional part. Dan's reasoning does not
> apply to this case, and it would be necessary to raise "Undefined" if xx
> contains negative points.
Decimal is not similar to binary in this respect. For decimal, if yy is a
singleton of the value 0.12 for example then it has indeed an odd
denominator since 0.12=12/100 = 3/25. The result in this case may be easily
defined for xx with negative points.
Since ten is a composite number, there are many cases where the fraction
given by a decimal significand reduces to one with an odd denominator. The
condition for that is that the numerator has enough powers of two to
eliminate the powers of two in the denominator.
--
Hossam A. H. Fahmy
Assistant Professor
Electronics and Communications Department
Cairo University
Egypt
------ Forwarded Message
From: Michel Hack <hack@xxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 15:36:16 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
Hossam Fahmy caught my blunder:
> > I do see an issue however in the case where yy is a singleton, because
> > that is now an exponent with an even denominator (in both decimal and
> > binary) if it has a non-zero fractional part.
>
> Decimal is not similar to binary in this respect.
Right; I just didn't think straight. Sorry.
Michel.
------ Forwarded Message
From: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 16:12:08 -0600
To: Michel Hack <hack@xxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
> Date: Sat, 05 Dec 2009 16:36:16 -0500
> To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> From: Michel Hack <hack@xxxxxxxxxxxxxx>
> Subject: Re: General pow(xx,yy) function in Motion 10
>
> Hossam Fahmy caught my blunder:
> > > I do see an issue however in the case where yy is a singleton, because
> > > that is now an exponent with an even denominator (in both decimal and
> > > binary) if it has a non-zero fractional part.
> >
> > Decimal is not similar to binary in this respect.
>
> Right; I just didn't think straight. Sorry.
>
> Michel.
> ---Sent: 2009-12-05 21:40:12 UTC
And, of course, this applies even to binary when yy is a
singleton integer for the denominator is 1 in that case. :-)
It is the odd integers that produce the negative results
in case of xx < 0, the even integers produce positive
results, & both cases will probably be sent to one of
the other pow's in any practical implementation.
But things like this & many others are kind of the idea
behind a generalized pow, no?
The pow that covers all cases & contains all solutions.
Dan
------ Forwarded Message
From: Michel Hack <hack@xxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 16:29:52 -0600
To: Dan Zuras <intervals08@xxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
> > Hossam Fahmy caught my blunder:
> And, of course, this applies even to binary when yy is a
> singleton integer for the denominator is 1 in that case. :-)
Dan, my blunder wasn't THAT gross -- I did say "non-zero fractional part"!
Michel.
------ Forwarded Message
From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 16:59:23 -0600
Subject: Re: General pow(xx,yy) function in Motion 10
Dan Zuras Intervals wrote:
>
> And, of course, this applies even to binary when yy is a
> singleton integer for the denominator is 1 in that case. :-)
>
> It is the odd integers that produce the negative results
> in case of xx < 0, the even integers produce positive
> results, & both cases will probably be sent to one of
> the other pow's in any practical implementation.
>
> But things like this & many others are kind of the idea
> behind a generalized pow, no?
>
> The pow that covers all cases & contains all solutions.
>
In principle, I follow that reasoning.
In practice, a particular scenario I have concern about is this:
If I understand correctly, in a branch-and-bound algorithm when xx is
negative the interval range will not contract even as the domain is
bisected... at least until the domain is bisected to a singleton value
(where it might be undefined). In either case, it is possible this could
lead to stack overflow and system crash.
With careful exception handling, I agree it should be possible to avoid such
an outcome. However, this also requires foresight and planning on behalf of
the unwary interval user. So is it really an improvement over requiring the
user to choose ahead of time between exp(y*ln(x)) vs. powr(x,m,n), etc.?
All else being equal, I suspect many interval users would choose general pow
because they see it as being easy to use. But then be surprised that their
branch-and-bound program crashed.
Nate
------ Forwarded Message
From: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
Date: Sat, 5 Dec 2009 17:36:17 -0600
To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Subject: 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: Sat, 5 Dec 2009 16:59:23 -0600
>
> In principle, I follow that reasoning.
>
> In practice, a particular scenario I have concern about is this:
>
> If I understand correctly, in a branch-and-bound algorithm when xx is
> negative the interval range will not contract even as the domain is
> bisected... at least until the domain is bisected to a singleton value
> (where it might be undefined). In either case, it is possible this could
> lead to stack overflow and system crash.
>
> With careful exception handling, I agree it should be possible to avoid such
> an outcome. However, this also requires foresight and planning on behalf of
> the unwary interval user. So is it really an improvement over requiring the
> user to choose ahead of time between exp(y*ln(x)) vs. powr(x,m,n), etc.?
>
> All else being equal, I suspect many interval users would choose general pow
> because they see it as being easy to use. But then be suprised that their
> branch-and-bound program crashed.
>
> Nate
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.
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.
------ Forwarded Message
From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Reply-To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Date: Sun, 6 Dec 2009 09:18:37 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
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
------ Forwarded Message
From: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
Date: Sun, 6 Dec 2009 14:50:03 -0600
To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Subject: 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
------ Forwarded Message
From: George Corliss <George.Corliss@xxxxxxxxxxxxx>
Date: Sun, 6 Dec 2009 20:05:13 -0600
To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>, Nate Hayes
<nh@xxxxxxxxxxxxxxxxx>
Subject: 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
------ Forwarded Message
From: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
Date: Sun, 6 Dec 2009 21:05:06 -0600
To: George Corliss <George.Corliss@xxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
> From: "Corliss, George" <george.corliss@xxxxxxxxxxxxx>
> Subject: 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
No, I believe that Nate's concern is more serious than that.
You see, when xx is negative & both xx & yy are singletons,
there are really two 'correct' answers, +/-e^(yy*ln(|xx|)).
The pow function returns the interval with those endpoints
in that case. But the interior contains no answers, just
the endpoints.
Now, if either xx or yy is of finite width, the set of
valid solutions extends inwards from the endpoints
towards the center of the interval. Probably still two
disjoint sets but they eventually do meet up.
Nate's concern is that any branch & bound method that
bifurcates one operand will leave one half with a smaller
interval (that part of the interior) & the other half
with the entire original interval or very nearly so.
He is correct, this IS a danger.
But the danger is in the search method rather than any
fault of the library function.
Back when I first proposed this sort of pow I said that
there should be auxiliary functions, say powPos & posNeg,
that map to one manifold of the full power function &
not the other. In the course of the discussion leading
up to this motion, those functions were lost.
Nate is exposing the need for them.
It is easily fixed with some later motion so I haven't
given it much thought for now.
I guess that was a mistake. :-)
So, a search method that decides to bifurcate along the
two manifolds of the pow function when it becomes
necessary is an easy fix.
There is a more serious problem in such search methods,
however. I briefly outlined that problem in my previous
posting.
But as it has nothing to do with the merits of motion 10,
I wanted to limit my discussion of it.
I see I have failed in that as well. :-)
Let me just say that, IMHO, none of this has anything to
do with the merits of motion 10 or pow as the only interval
function that assures containment. We should add the
single manifold functions at some later date but it need
not form part of our discussion today.
Well, no more than it has already, that is. :-)
Again, sorry for the digression, folks.
Dan
------ Forwarded Message
From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Date: Sun, 6 Dec 2009 21:18:32 -0600
Subject: 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
------ Forwarded Message
From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 07:49:00 -0600
Subject: Re: General pow(xx,yy) function in Motion 10
Arnold Neumaier wrote:
> Michel Hack wrote:
>> George Corliss wrote:
>>> In most applications, we are lucky to know 3 digits.
>>> By implication, all intervals are thick.
>>
>> ALL non-degenerate intervals are "thick" as far as pow(xx,yy)
>> is concerned, REGARDLESS of precision. Only singletons can
>> be rational (and, indeed, are). That is because (per Motion 3)
>> intervals are *real* intervals and are presumed to contain all
>> reals between the bounds, not just floating-point numbers.
>> Even a 1-ulp interval is "thick".
>>
>> That's why there really are only two choices for a pow(xx,yy)
>> with two interval arguments: exclude negative values from xx,
>> or compute the proper interval hull. What Dan observed was that
>> this hull can be defined unambiguously, because it is the union
>> of only two arbitrarily-narrow intervals for any narrow source
>> intervals where xx contains negative points.
>>
>> The other way around this quandary uses families of single-argument
>> pow_r(xx) interval functions, parameterized by a rational exponent 'r'
>> that is exact -- whether a floating-point number or, more transparently,
>> a pair of integers. For convenience we might also have pow_n() and
>> root_n() families, where the rational parameter has either a
>> denominator of 1 or a numerator of 1 (and 'n' is an integer).
>>
>> We may of course have both, giving the programmer a choice of approach.
>> Motion 10 makes pow(xx,yy) mandatory and recommends the parametrized
>> families.
>
> I think that efficiency in the applications requires both the integral
> powers and the nonnegative real powers, whereas the most general power
> (with exponent intervals allowed for negative arguments) will have
> very little use. The reason is that the user usually knows whether the
> exponent is an exact integer (or rational) or can range in some region,
> and the latter case usually makes sense only if the argument is
> nonnegative.
>
> The only exception is in nonlinear integer programming, where it is
> conceivable that one has intervals for integers acting as exponents.
>
>
> Thus I recommend making integral powers and nonnegative real powers
> mandatory, and the most general power and the rational power optional.
>
>
> Arnold Neumaier
------ Forwarded Message
From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 07:50:41 -0600
To: Michel Hack <hack@xxxxxxxxxxxxxx>, 1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
Michel Hack wrote:
>> The only exception is in nonlinear integer programming, where it is
>> conceivable that one has intervals for integers acting as exponents.
>
> Yes -- but such an exponent range is not an interval, because it is
> strictly a set of integers and does not include the real numbers in
> between. So using intervals to represent it during an exploratory
> part of an algorithm requires to programmer to keep this in mind, and
> correct for the consequences, as the usual Interval Theorems don't
> apply anymore.
This is always done in mixed integer nonlinear programming using branch
and bound techniques. One accounts for integrality by splitting at half
an integer and rounding the two new bounds to the next integer.
This is enough to make everything work correctly, as far as pruning
regions is concerned. Of course, existence statements beyond that (such
as Brouwer's fixed-point theorem) needed only for computer-assisted
proofs) need to fix integers when integrality constraints are present,
before they apply.
> Suppose for some reason the function 1/cospi(x) is involved over a
> range that only includes integers. It's "interval" hull would then
> be [-1,+1] (but would in fact only contain the endpoints), when the
> true interval hull would be Entire.
>
> This is why I'm also wary of interval functions like sign, ceil etc.,
> because their range is by definition a set of isolated integral points.
Lots of application optimization problems written by inexperienced
users into excel sheets have discontinuities.
Thus one really needs interval extensions of discontinuous functions.
Of course, we need them together with the exception information in
case a discontinuity is possibly inside the interval (to avoid
claiming existence when only covering information is valid).
This is one of the reason why the decoration for continuity is important.
------ Forwarded Message
From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
Reply-To: "rbk@xxxxxxxxxxxxx" <rbk@xxxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 08:58:22 -0600
To: George Corliss <George.Corliss@xxxxxxxxxxxxx>
Cc: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>, Nate Hayes
<nh@xxxxxxxxxxxxxxxxx>, "stds-1788@xxxxxxxxxxxxxxxxx"
<stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
I had been wondering the same thing. That is, under what
circumstances will someone actually want to compute a rational
power of a negative number?
Baker
------ Forwarded Message
From: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 09:22:52 -0600
Subject: Re: General pow(xx,yy) function in Motion 10
Michel Hack wrote:
> Nate Hayes wrote:
>> 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.
>
> What would be the meaning of an interval xx that includes relatively
> large negative values, when raised to an uncertain real exponent?
I don't really think it makes sense, either. It's another reason that I'm
skeptical of the general power function; and why I was hoping someone could
provide an example of why it is required.
Since it was listed as required in Motion 10, I was assuming some of our
experts in the forum saw this as being important. I was just looking at the
consequences of what happens when you put it into a branch-and-bound
algorithm. That's all.
Personally, I like Arnold's suggestions:
> Thus I recommend making integral powers and nonnegative real powers
> mandatory, and the most general power and the rational power optional.
Nate
------ Forwarded Message
From: George Corliss <George.Corliss@xxxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 09:48:36 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Motion P1788/M0010.22: ElementaryFunctions: YES
I vote YES on Motion 10.
Listening to the on-going discussion about pow(xx,yy), it is
clear that it (and related possibilities) need more detailed
Consideration. However, rather than voting NO, I choose to
vote YES and assume that the pow(xx,yy) questions will be
refined later.
Dr. George F. Corliss
------ Forwarded Message
From: Michel Hack <hack@xxxxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 10:38:24 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Re: General pow(xx,yy) function in Motion 10
George Corliss wrote:
> In most applications, we are lucky to know 3 digits.
> By implication, all intervals are thick.
ALL non-degenerate intervals are "thick" as far as pow(xx,yy)
is concerned, REGARDLESS of precision. Only singletons can
be rational (and, indeed, are). That is because (per Motion 3)
intervals are *real* intervals and are presumed to contain all
reals between the bounds, not just floating-point numbers.
Even a 1-ulp interval is "thick".
That's why there really are only two choices for a pow(xx,yy)
with two interval arguments: exclude negative values from xx,
or compute the proper interval hull. What Dan observed was that
this hull can be defined unambiguously, because it is the union
of only two arbitrarily-narrow intervals for any narrow source
intervals where xx contains negative points.
The other way around this quandary uses families of single-argument
pow_r(xx) interval functions, parameterized by a rational exponent 'r'
that is exact -- whether a floating-point number or, more transparently,
a pair of integers. For convenience we might also have pow_n() and
root_n() families, where the rational parameter has either a
denominator of 1 or a numerator of 1 (and 'n' is an integer).
We may of course have both, giving the programmer a choice of approach.
Motion 10 makes pow(xx,yy) mandatory and recommends the parametrized
families.
Michel.
------ Forwarded Message
From: Michel Hack <hack@xxxxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 12:02:20 -0600
Subject: Re: General pow(xx,yy) function in Motion 10
Nate Hayes wrote:
> 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.
What would be the meaning of an interval xx that includes relatively
large negative values, when raised to an uncertain real exponent?
It seems to me that the only sensible cases are those where xx is
essentially
positive, but may include *small* (close to zero) negative values because of
earlier outward rounding, and we want to be able to continue computing with
this. Dan's pow(xx,yy) is the right tool for those cases.
(By "small" I mean that abs(xx.lo) is of the order of a few ulps of xx.hi)
Michel.
------ Forwarded Message
From: Ralph Baker Kearfott <rbk@xxxxxxxxxxxx>
Date: Mon, 7 Dec 2009 15:42:10 -0600
Subject: Motion P1788/M0010.22: Elementary Functions: YES
My vote is also "yes," with the same reasoning as George.
If I strongly dislike the power function as it appears
in the draft standard, I can vote against that paragraph
when it comes up for a final vote.
Baker
------ Forwarded Message
From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
Date: Tue, 8 Dec 2009 08:53:08 -0600
To: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
Subject: Motion P1788/M0010.22: Elementary Functions: YES
P1788
I vote YES on this for the same reasons and with similar reservations as
George and Baker. That is, don't rock the boat now, but rock it later.
I agree with everything in Motion 10.22 except the general pow(xx,yy).
- I find Nate's criticisms of pow() pretty convincing.
- Also, I am wondering what is the use of a pow(xx,yy) that, as far as
singleton yy = [y,y] is concerned, understands only those rational y that
can be expressed exactly in either base 2 or base 10? This puzzled me some
weeks back when Prof Fahmy was arguning in favour of this function.
- But I have a more serious criticism of pow(), as it is presented by
Juergen. He says in the rationale "it is not an extension of any point
function" or similar words. But it has to (in standardese, "shall") be. The
reason is that P1788 believes in the Fundamental Theorem of Interval
Arithmetic (FTIA) at least we voted for it in Motion 6.
The FTIA relates the result of evaluating the interval version of an
expression E, to the range of the point function f defined by E. If any of
the interval library functions used in the interval version fails to be "an
extension of any point function", then f does not exist!
Actually, Juergen's assertion is false. Any interval mapping whatever is an
interval extension of a point function, namely the function that is
everywhere undefined, i.e. has empty domain. Of course that is useless
because if that occurs anywhere in the (point version of) E, then the
resulting f is also everywhere undefined.
So the question is whether interval_pow() as Juergen defines it is an
interval extension of some "useful" point_pow(). I haven't checked, but
suspect that it is an extension of
f(x,y) = {usual x^y for x>0, any y
{0 for x=0, y>0 (unique limiting value)
{0 for x=y=0 (arbitrary choice)
{rational power x^(p/q)
{ for those rational y = p/q for which this makes sense
{undefined otherwise, including for x=0, y<0.
Could someone check?
There is always a "maximal" (not necessarily unique) point function g of
which a given interval mapping gg is an extension, _provided_ gg is
isotonic. Namely, let
g(z) := ( an arbitrary point in gg([z,z]) ) whenever gg([z,z]) is
nonempty;
undefined elsewhere.
So I am guessing that for Juergen's pow(), this construction yields the
unique f I described above.
In any case, for the sake of the FTIA, ALL our elementary functions should
start from the definition of the point function, and then the interval
version, at least theoretically, should be the _sharp_ interval extension of
that. IMO.
That's my boat-rocking £0.02.
John
------ Forwarded Message
From: Van Snyder <Van.Snyder@xxxxxxxxxxxx>
Reply-To: "Van.Snyder@xxxxxxxxxxxx" <Van.Snyder@xxxxxxxxxxxx>
Date: Thu, 17 Dec 2009 14:41:54 -0600
To: George Corliss <George.Corliss@xxxxxxxxxxxxx>
Subject: Re: Motion P1788/M0010.20:ElementaryFunctions: PLEASE VOTE
George:
Register a "yes" ballot for me with the additional comment:
"The function exp(x^2) erfc(x) should be amongst the optional functions.
It appears frequently in statistical calculations. In single-precision
IEEE 754 arithmetic, erfc(x) underflows for x > ~9, while exp(x)
overflows at about the same value. exp(x^2) erfc(x) is asymptotic to
1/(x \sqrt\pi) so it doesn't overflow, and it doesn't underflow until x
> huge(x)/\sqrt\pi."
Van Snyder
------ Forwarded Message
From: Guillaume Melquiond <guillaume.melquiond@xxxxxxxx>
Date: Mon, 21 Dec 2009 08:36:15 -0600
To: "stds-1788@xxxxxxxx" <stds-1788@xxxxxxxx>
Subject: Motion P1788/M0010.22: ElementaryFunctions: YES
I vote YES for Motion 10.
Note: I'm unconvinced by the definitions of pow and atan2 though, but
this is better left for later.
Best regards,
Guillaume
Begin forwarded message:
From: Vincent Lefevre <vincent@xxxxxxxxxx>
Date: December 23, 2009 8:02:55 PM CST
To: "stds-1788@xxxxxxxx" <stds-1788@xxxxxxxx>
Subject: Motion P1788/M0010.22: ElementaryFunctions: YES
Motion P1788/M0010.22: ElementaryFunctions: My vote is YES
I haven't had the time to read the discussion yet, but here are
a few comments:
* General Power Function:
It is said: "If p is odd the result is negative otherwise positive."
but in the interval version, both the negative value and the positive
value are included. This is really strange (a simplification?), at
least in the case of a point interval, and I think that there should
be some comment about it.
2 missing closing parentheses in the case x < 0.
The non-standard notation "\exists 0 < y \in \mathbf{y}" is difficult
to parse and should be rewritten: \exists y \in \mathbf{y},\ y > 0
* Page 3, atanh
The rough domain is (-1,1), not [-1,1]. And II[-1,1] needs to be
changed into II(-1,1).
* Page 4, atanPi and atan2Pi
The range is incorrect. It should be (-1/2,1/2) for atanPi, and
AFAIK, (-1,1] for atan2Pi.
* Page 4, gamma and lgamma
The domain should exclude the non-positive integers.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)
Begin forwarded message:
From: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
Date: December 23, 2009 10:55:38 PM CST
Subject: Re: Motion P1788/M0010.22: ElementaryFunctions: YES
Date: Thu, 24 Dec 2009 03:02:55 +0100
From: Vincent Lefevre <vincent@xxxxxxxxxx>
Subject: Motion P1788/M0010.22: ElementaryFunctions: YES
Motion P1788/M0010.22: ElementaryFunctions: My vote is YES
I haven't had the time to read the discussion yet, but here are
a few comments:
. . .
* Page 4, gamma and lgamma
The domain should exclude the non-positive integers.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / Arénaire project (LIP, ENS-Lyon)
I believe Vincent only means to exclude
those integers from the domain of lgamma,
not gamma (where they are zero). - Dan
Attachment:
motion10-functionsv22.pdf
Description: motion10-functionsv22.pdf