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

https://hal.archives-ouvertes.fr/file/index/docid/576641/filename/computing-midpoint.pdf

by ColinWright • 9 years ago

51 5 9 years ago

hal.archives-ouvertes.fr

zaf• 9 years ago

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

dzdt• 9 years ago

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

deathanatos• 9 years ago

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.)

user5994461• 9 years ago

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

throwaway_374• 9 years ago

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/

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

Related Stories