Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Table 4 proposal version 0.1...



> Date: Wed, 29 Feb 2012 17:35:24 +0100
> From: Arnold Neumaier <Arnold.Neumaier@xxxxxxxxxxxx>
> To: Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>
> CC: stds-1788@xxxxxxxxxxxxxxxxx
> Subject: Re: Table 4 proposal version 0.1...
> 
> On 02/29/2012 05:00 PM, Dan Zuras Intervals wrote:
> >> Date: Wed, 29 Feb 2012 15:47:49 +0100
> >> From: Arnold Neumaier<Arnold.Neumaier@xxxxxxxxxxxx>
> >> To: 1788<stds-1788@xxxxxxxxxxxxxxxxx>
> >> Subject: Re: Table 4 proposal version 0.1...
> >>
> >> On 02/29/2012 03:23 PM, Vincent Lefevre wrote:
> >>> On 2012-02-21 17:20:47 -0800, Dan Zuras Intervals wrote:
> >>>> 	I still have no good answer for midpoint(Empty) so that
> >>>> 	is still not part of this proposal.
> >>>
> >
> > 	As I keep saying, mid(Empty) is not part of this proposal.
> > 	We can continue this debate until someone HAS a proposal
> > 	that makes sense.  I do not have one yet.
> 
> I made a proposal which is mathematically sound and uniform (and is
> the only mathematically sound choice), but conflicts with your 
> definition on unbounded intervals, which _is_ in the proposal.
> 
> Taking infinity as the midpoint of [0,Inf] is against all common sense
> as it is as far from any point of the interval as is conceivable.
> No midpoint in any conceivable interpretation. There is no midpoint,
> and the result should reflect that. Labeling Inf as 'the' midpoint is 
> misleading,

	Ah, so this is something OTHER than midpoint(Empty).

	Very well.

	If you read the proposal very carefully, you will find
	that the level 2 midpoint returned for any semi-infinite
	interval is finite.  Thus the split of [0,inf] becomes
	[0,Fmax] \union [Fmax,inf].

	However, I agree that calling Fmax the midpoint is nearly
	as misleading as calling infinity the midpoint would be.

	I originally had something like (0+Fmax)/2 as the midpoint
	but Michel made an argument that Fmax was better.  I must
	admit I resisted that argument for a time but I believe
	his reasoning leads to a better (that is, simpler & more
	useful) split than I had in mind.

	It is a compromise.  Many choices are possible.  All of
	them have something arbitrary to their nature.  It is our
	job to pick one & stick with it.

	Do you have a better choice?

> 
> 
> >> On the other hand, a function split(X) [if provided by the standard]
> >> should return a sensible splitting point if one exist, and NaN
> >> otherwise, i.e., if X contains at most two machine numbers. What is
> >> most sensible would have to be discussed. I thought for some time that
> >> returning the median of the machine numbers is good but this would
> >> split the interval [0,1] at an extremely tiny number, which is not
> >> warranted. It seems that there is no ''natural'' such function, thus
> >> the standard should not provide one.
> >>
> >> Instead, I propose to provide a function flmedian(X) that provided the
> >> median, so that users can make their own split routine based on mid,
> >> flmedian, and scaling considerations.
> >
> > 	I have not written it down yet, but I have an algorithm in
> > 	mind for split(X) that would work at level 1 with only one
> > 	new piece of information: namely the radix (2 or 10) within
> > 	which your arithmetic is done.
> >
> > 	This split(X) would return a Real number that is nearest to
> > 	the median of representable numbers in any system of any
> > 	precision with that radix.  When converted to a level 2 F
> > 	of that radix, the intervals [inf(X),split(X)]&
> > 	[split(X),sup(X)] would have the same number of representable
> > 	elements +/- 1.
> >
> > 	But there is a fly in the ointment:  Unless I know the range
> > 	of the exponent, I do not know how to properly split either
> > 	semi-infinite intervals or intervals containing zero.  Where
> > 	"properly" is defined as +/-1 on each side.  The reason for
> > 	this is that numbers "bunch up" around zero in much the same
> > 	way as they bunch up near infinity.  And how much they bunch
> > 	up is a function of the exponent range&  whether or not your
> > 	arithmetic supports subnormals.
> 
> There is another fly, which makes this useless for branch and bound.

	Not so but useless for your following example.

> 
> Many problems have bounds [0,1], and your proposal would split this 
> interval somewhere close to the sqrt of the smallest normalizable 
> number. This produces a tiny interval (containing half the floats)
> and an interval essentially as wide as before (containing the other 
> half). For most functions people would apply b&b to, this is a totally 
> unproductive split.

	You are quite correct.  And such a split should not be used
	in this case.

	If it hurts, don't do that.

> 
> The split must be adapted to the problem, not to the number system. Thus 

	Of course.

> it cannot figure sensibly in a standard. Instead, the standard should 
> provide the building blocks needed to construct a variety of sensible, 
> problem-adapted splitting rules.
> 
> 
> > 	There are 2 general ways to go: (1) make Emax ALSO a parameter
> > 	to the split,&  (2) split off the infinities&  zero BEFORE you
> > 	start "proper" splitting.
> 
> Neither catches the second fly.
> 

	Not when you are seeking an answer to an arithmetic (i.e.
	scaled) problem which admits zero as a possibility.

	But there are many scale free problems where even the
	exponent of the answer is not known.  Various astronomical
	questions come to mind.  The Drake equation is a simple
	example.

	Non-astronomical applications include monte-carlo
	calculations which involve computing probablities that
	are logrithmically distributed with [0,1].  Answers tend
	to be small & a logrithmic split would take substantially
	fewer steps than an arithmetic one.

	And our friends in the high precision world often seek
	to know the most accurate answer they can get in the
	(admittedly large) precision within which they work.

	Therefore, any split of this kind has a more limited
	area of application than splitting along arithmetic
	midpoints.

	(BTW, as soon as you get within a power of the radix,
	split(X) = midpoint(X).)

	It is not a panecea.  It does not replace midpoint.
	And it is not intended that it should.

	But it should be an arrow in our quiver of useful things.

	So long as you don't point it at the wrong target.


				Dan