What's the best midpoint formula for floating point numbers?

user_6789693 0
Viewed 550

The first formula

m = (a + b) / 2

is simple, but has a great risk of overflow. Besides, Numerical Analysis, 9th Edition by Burden and Faires points out that

when b - a is near the maximum precision of the machine, it is possible for (a + b) / 2 to return a midpoint the is not even in the interval [a, b].

though no further explanation is provided.

The second one

m = a + (b - a) / 2

is also correct, with a smaller chance of overflow. But for floating numbers, nearly equal values of a and b may lead to a loss of significance.

So, which formula is better in practice? Also, an explanation for the quote statement will be appreciated.

numerical-analysis numerical
1 Answers

The simple (a+b)/2 is perhaps not as overflow-prone as you think—for IEEE 754 double precision, at least one of the operands has to be at least 8.988e307 (half the maximum finite value of 1.788e308) for a+b to overflow. Moreover, if it does not overflow it is correctly rounded (again, for 754) because at most one operation rounds (the division (potentially) rounds only for numbers smaller than 4.450e-308 (down to the absolute minimum of 5e-324), and no addition whose result is that close to 0 ever rounds). Since it is correctly rounded, it of course cannot be outside [a,b] since at least one of those would be closer to the true value.

If you might overflow, at least one of your values is very large, so you can just use a/2+b/2, which is then also correctly rounded (since each division is exact or else irrelevant). This is of course one more floating-point operation.

There is a caveat that the rounding mode can produce unexpected overflow or underflow with these formulae, but that’s not a common concern.

As for a+(b-a)/2, it’s just as bad for overflow if a and b might have different signs. It doesn’t, however, have “loss of significance” concerns: while the relative error in a small difference of large approximate values can of course be very large, such an operation is always exact in terms of the exact floating-point input values and thus does not contribute any numerical problems beyond those inherent in any such calculation.

user_85862270
Related