Menu
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.
805
To find the midpoint of any range, add the two numbers together and divide by 2. In this instance, 0 + 5 = 5, 5 / 2 = 2.5.
According to this standard, floating point numbers are represented with 32 bits (single precision) or 64 bits (double precision).
In floating point arithmetic, two extra bits are used to the far right of the significand, called the guard and round bits. At the end of the arithmetic calculation, these bits are rounded off. We always round towards the closer digit (i.e. 0.00-‐0.49 → 0 and 0.51-‐0.99 → 1).
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.
119
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
