Name
Title | ||
|---|---|---|
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 |
Abstract | ||
|---|---|---|
We study the accuracy of classical algorithms for evaluating expressions of the form √ (a
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
+ b
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
) and c/√ (a
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
+ b
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
)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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
) for √ (a
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
+ b
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
), and by 3u+O(u
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
) for c/√ (a
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
+ b
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
), where u = 2
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-p</sup>
is the unit roundoff. Recently, it was observed that for √ (a
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
+ b
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
) the O(u
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
) term is in fact not needed [1]. We show here that it is not needed either for c√ (a
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
+ b
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
). 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
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
+ b
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>
. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/ARITH.2017.40 | 2017 IEEE 24th Symposium on Computer Arithmetic (ARITH) |
Keywords | Field | DocType |
binary floating-point arithmetic,rounding error analysis,relative error,hypotenuse function | Discrete mathematics,Combinatorics,Exponent,Floating point,Elementary arithmetic,Asymptotically optimal algorithm,Mathematics,Approximation error,Bounded function,Binary number | Conference |
ISSN | ISBN | Citations |
1063-6889 | 978-1-5386-1966-7 | 0 |
PageRank | References | Authors |
0.34 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Claude-Pierre Jeannerod | 1 | 224 | 22.05 |
| Jean-Michel Muller | 2 | 466 | 66.61 |
| Antoine Plet | 3 | 0 | 0.34 |