How do you compute the midpoint of an interval? (2014) [pdf] | Hacker News Reader

How do you compute the midpoint of an interval? (2014) [pdf]

hal.archives-ouvertes.fr

51 pointsColinWright5 comments

To summarize failure modes:

(a+b)/2 fails if |a+b| is too large to represent as a finite floating point number (overflow/underflow), also bad for a,b = +/- infinity.

(a/2 + b/2) can be inaccurate for a/2 and b/2 subnormal; also bad for a,b = +/- infinity

(a-a/2) + b/2 is good for most cases, but you should precede with checks for a=-b and a,b=+/-infinity to get best results in all cases

Also, this one:

  a + (b - a) / 2

has issues that if b is large and a is negative but "large" (in magnitude), then b - a can overflow.

I mention that one, since that was how I was taught to do it for binary search, to prevent overflow. (Binary search having the advantage that it can't overflow, b/c a and b represent indexes, and are thus non-negative, so this works there but breaks in the more general case discussed by the paper.)

Option 1 + Decide that you don't care about numbers bigger than 2 billion. Problem solved!

Tangential but it does irk me when these online streaming summary statistics algorithms come up in interviews. Most recently I had Welford's for online estimation of variance/std optimised for numerical stability. Great, fascinating stuff, there's FP representation issues but really is this necessary to quiz... mostly just the interviewer trying to show off how clever they are.

https://www.johndcook.com/blog/standard_deviation/

Very interesting. Something new for me. Thanks for the link.

Reply on news.ycombinator.com