Re: How do I bisect unbounded intervals?
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.
(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.
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.
Michel, it looks like a Level 2 concept to me. It's only your proposed implementation that is Level 4.
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"?
(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.
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.
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.)
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.
(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