Don't get your GI tract in a twist...

[Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx>]

> From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
> To: "Dan Zuras Intervals" <intervals08@xxxxxxxxxxxxxx>
> Subject: Dang namit...
> Date: Mon, 30 Jan 2012 22:45:50 -0600
> 
> Dan,
> 
> Argh. I *knew* we were missing something!
> 
> Nate

	Remain calm.  Its not what you think.

> 
> ----- Original Message ----- 
> From: "Dmitry Nadezhin" <dmitry.nadezhin@xxxxxxxxxx>
> To: <nh@xxxxxxxxxxxxxxxxx>
> Cc: <stds-1788@xxxxxxxxxxxxxxxxx>
> Sent: Monday, January 30, 2012 9:30 PM
> Subject: Re: Midpoint and unbounded intervals
> 
> 
> The property (22) doesn't always hold.
> Let us cosider two-digit floating-point decimal numbers.
> X = [1.0,1.1]
> midpoint(X) = roundNear((1.0 + 1.1)/2) = roundNear(1.05) = 1.0
> The definition (24) says
> radius(X) = roundUp((1.1 - 1.0)/2) = roundUp(0.05) = 0.05
> The interval [midpoint(X)-radius(X),midpoint(X)+radius(X)]=[0.95,1.05] 
> doesn't contain X.
> 
> There tightest radius(X) satisfing (22) is:
> radius([u,v]) = roundUp(max(midpoint([u,v]) - u, v - midpoint([u,v]))) .
> However, it is necessary to explore if it can be implemented efficiently.
> 
>   -Dima

	I have good news & good news & good news & good news.

	The good news is that Dmitry's example is invalid in that
	1.05 is not a 2 digit decimal number.

	However, the good news is that he has found an example
	even more extreme than I found in the no-subnormals case.
	He has found an example in which the midpoint is not
	merely NEAR one of the endpoints but is EXACTLY one of
	the endpoints.

	You see, up until now I have been amazed that our definitions,
	which report narrower enclosing intervals than Dmitry's does,
	always rounded in the correct direction to in fact enclose
	the interval in question when mapped onto representable
	numbers.  Even when it was only half an ULP.

	So the good news is that Dmitry has found an example that
	might round the wrong way, when using roundToNearest.

	That means that the good news is that we must be a bit more
	careful in our statement of property (22).  It must be

		X \subset [roundDown(midpoint(X) - radius(X)),
				roundUp(midpoint(X) + radius(X))].	(22)

	And now we have for X = [1.0,1.1] that midpoint(X) = 1.0 &
	that Dmitry's definition

		radius([u,v]) = roundUp(max(midpoint([u,v]) - u,
						v - midpoint([u,v])))

	finds for X that radius(X) = 0.1 whereas our definition

		radius([u,v]) = roundUp((v - u)/2)

	reports radius(X) = 0.05.

	With the now corrected property (22) we have for Dmitry's
	case

		X \subset [0.90,1.1]

	which is true.  However our definitions report

		X \subset [0.95,1.1]

	which is a narrower enclosure.

	If everyone is OK with that, Nate will you modify (22) to
	reflect Dmitry's discovery & roll the date to tomorrow.

	Thanks, Dmitry.  You found what we should have found but
	couldn't.

				Dan