Re: How do I bisect unbounded intervals?
> Subject: Re: How do I bisect unbounded intervals?
> From: John Pryce <j.d.pryce@xxxxxxxxxxxx>
> Date: Tue, 17 Jan 2012 21:19:03 +0000
> Cc: stds-1788 <stds-1788@xxxxxxxxxxxxxxxxx>
> To: Nate Hayes <nh@xxxxxxxxxxxxxxxxx>,
> Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>,
> Michel Hack <hack@xxxxxxxxxxxxxx>
>
> Folks
>
> On 13 Jan 2012, at 14:35, Nate Hayes wrote:
> > Dan Zuras wrote:
> >> If we are to generalize this discussion into something
> >> more appropriately standardizable like a definition of
> >> midpoint, I think failing on too narrow [u,v] or even
> >> [u,u] would be unreasonable from the user's perspective.
> >>
> >> But Nate, as the B&B guy in the room, I'm sure you have
> >> working stopping criteria other than blowing up when an
> >> interval gets too narrow. What's wrong with using
> >> width(xx) > 0? Actually I suspect you actually use
> >> width(xx) > eps where eps > 0. Both work in the sense
> >> of preventing infinite recursions & both allow one to
> >> use a more reasonable definition of midpoint.
> >
> > Nothing's wrong with that. As I mentioned from the get-go, the ills =
> can be cured by tedious and defensive programming. I think others have =
> already attested to this, as well. But the learning curve for the =
> uninitiated has to come from somewhere, and its very easy to make =
> mistakes... and no one wants thier real-time radar-tracking B&B =
> algorithm of the future to crash once the missile leaves the launching =
> pad.
Please ignore my comment on Nate's stopping criteria. He
has since taught me a lot about it & my words no longer
apply. We have both since come to an understanding that
improves both worlds. Please give us a little time to
write it up.
>
> (A)
> This is good fun but I agree with the view that some of the =
> "midpoint-like" functions proposed go well beyond P1788's remit. In =
> particular, anything with "random" in it is NOT our job. (BTW: How come =
> none of the proposed random solutions specify the chosen probability =
> distribution, which is crucial?)
>
> Also, midpoint at Level 1 must mean exactly what it says: (a+b)/2. =
> Hence, at Level 2 it must be, by default, (a+b)/2 rounded to nearest. =
> There's no justification for a Level 2 redefinition with NaNs and stuff, =
> that will be meaningful to only a small fraction of the user population.
The midpoint() Nate & I have come up with is exactly
roundToNearest((a+b)/2) for finite [a,b]. The trick was
to come up with something reasonable for the semi-infinites.
We think we have done that but it is not obvious & requires
some background & explanation. It is coming. I promise.
>
> Maybe, however, we should provide a facility for a user-selected =
> rounding mode for this and perhaps some other functions?
>
> Views please!
>
> (B)
> However I do NOT have a problem with Dan's & Michel's (13 Jan) "convert =
> to sortable, take the average" idea. (BTW I found this is a neat way to =
> do interval division using the same [min of 4 values, max of 4 values] =
> method that works for multiplication.) This is a standard function that =
> can ONLY exist at Level 2, and only for inf-sup types -- but I see no =
> reason to disallow it for those reasons.
I must admit I had to go back through my mail to find
Dan & Michel's "convert to sortable & average" idea. :-)
But yes, this is a sort of geometric mean for level 2
floating-point numbers that has been used for similar
things in the past.
>
> Michel, it looks like a Level 2 concept to me. It's only your proposed =
> implementation that is Level 4.
Agreed. It can be described at level 2 as the median of
all floating-point numbers between lo & hi whatever
their values. But chances are the best way to implement
it would be at level 4 along the lines Michel describes.
>
> Since it is finding a value that has (roughly) as many floating point =
> datums above it as below it, might it be called the "median"?
I think this would be best. It does not confuse it with
the midpoint & other styles of split could have other
names.
But I must say that I don't believe this will be needed.
Perhaps others have a good application. Anyone?
>
> (C)
> Finding a floating-point "splitting place" c for an interval [a,b], as a =
> prelude to splitting it as ([a,c] union [c,b]) will ALWAYS be hazardous =
> for inexperienced programmers, as folk have noted. E.g., when a or b or =
> both are very large, or very small, or when they are adjacent FP =
> numbers.
>
> So IMO there's merit in the proposal of a "split" operation that goes =
> directly from [a,b] to ([a,c], [c,b]) and is written by professionals to =
> avoid the pitfalls.
This is part of what Nate & I have done. Still, I agree,
some instruction will be required so our users will know
the approved way to do it under 1788.
What I mentioned to Nate in passing was that it seems we
need an informative annex describing how one goes about
doing common interval things in 1788. This should be
written so the novice can follow it but even the expert
interval guy will have to learn how 1788 differs from
older interval packages.
But this is a topic for another day. Not today.
>
> In my view IT MUST BE PARAMETERIZED, if it's to be any use in a variety =
> of applications. E.g., the Zuras "arithmetic mean for small numbers, =
> geometric for big ones" principle needs to specify when a number ceases =
> to be "small". That is, it must specify one scale parameter, at least.=
I hesitate to go so far as calling that a principle.
And certainly not so far as to parameterize a function
which was just a suggestion & may never come to pass.
The notion comes from the fact that for intervals smaller
than [x,r*x] where r is the radix, the median is very
nearly the arithmetic mean. But for intervals larger
than [x,s*x] for s >> r, the median is close to the
geometric mean.
So you see, there is no parameter involved.
>
>
> The Hack-Zuras "convert to sortable ..." implementation of this _looks_ =
> scale-independent, but it isn't. My intuition says that its effective =
> scale is governed by MINREAL, the smallest positive normal number. If =
> used on a large interval surrounding zero, its result will be biased by =
> the vast set of very small FP numbers. (I will try to substantiate this =
> guess.)
Your intuition is correct. In the past, such things are
(at least nearly) scale independent only so long as the
scale get no where near either minReal or maxReal. And
it is also correct that for intervals that include zero,
the split is almost always very near zero because there
are so many numbers near zero.
Perhaps this is another good reason for not implementing
this function. Its merit is that it minimizes a binary
search for a particular floating-point number. But it
does so at the cost of a very hard to understand search.
>
> My suggestion therefore would be a function on the lines of (using =
> Matlab syntax)
> [uu, vv, status] = split(xx, scale)
> Input
> xx A nonempty interval.
> scale Strictly positive number. The threshold at which a number is =
> considered "large".
> Output
> uu,vv Left and right halves into which xx is split, on normal exit.
> status 0 indicates success. Other values indicate various failure =
> conditions.
> Algorithm
> Roughly equivalent to the steps
> - Divide xx by scale.
> - Apply a scale-independent method to the result, returning uu and vv.
> - Multiply uu and vv by scale.
> Made able to handle nasty cases (e.g. badly scaled) robustly, of =
> course.
>
> Cleverer versions of the algorithm might be parameterized by more than =
> just one real number, but this strikes me as about the level of =
> sophistication that could be appropriate for P1788. Comments welcomed.
I'd really rather not go this route unless you think there
is some great need for it. Even if you do, I think an
implicit definition of median at level 2 that is actually
implemented at level 4 like Michel says is as far as I
would go with it.
>
> (D)
> Yes, we can do our best to reduce the errors made by inexperienced =
> programmers. But I'm skeptical of Nate's general desire. The very =
> success of numerical analysts and software writers conspires to conceal =
> their massive achievement, just as the reliability of modern cars makes =
> us forget the miracles that go on under their hoods.
>
> Numerical computation was, is and will always be tricky and there is NO =
> way to protect the inexperienced from its risks. You Sunfish guys are =
> professional B&B algorithm writers, for a particular class of problems. =
> It's up to you to teach your newcomers the pitfalls and how to avoid =
> them. Otherwise, users will always suffer those unexpected infinite =
> recursions (or the odd space rocket falling on their heads).
>
> Regards
>
> John=
Nate's IP problems can be at odds with the desire to
publish the best work in this area. Still, he has to
find a way to sell Sunfish's stuff whilst still helping
us as best he can. Not an easy path to follow, I suspect.
At the moment, I don't think we run into any IP hassles
in our attempt to standardize the best way to handle B&B
problems as well as other things that need to find the
midpoint or split of intervals.
In any event, both Nate & I have something we would like
to show to all of you but for the fact that the rest of
our lives is getting in the way. Give us time & you can
judge the results for yourselves.
I promise to work as fast as I can.
Yours,
Dan