The Classical Relative Error Bounds for Computing Sqrt(a^2 + b^2) and c / sqrt(a^2 + b^2) in Binary Floating-Point Arithmetic are Asymptotically Optimal

摘要

We study the accuracy of classical algorithms for evaluating expressions of the form √ (a + b) and c/√ (a + b)in radix-2, precision-p floating-point arithmetic, assuming that the elementary arithmetic operations ±, x, /, '/ are rounded to nearest, and assuming an unbounded exponent range. Classical analyses show that the relative error is bounded by 2u+O(u) for √ (a + b), and by 3u+O(u) for c/√ (a + b), where u = 2 is the unit roundoff. Recently, it was observed that for √ (a + b) the O(u) term is in fact not needed [1]. We show here that it is not needed either for c√ (a + b). Furthermore, we show that these error bounds are asymptotically optimal. Finally, we show that both the bounds and their asymptotic optimality remain valid when an FMA instruction is used to evaluate a + b.