[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Algorithm 1014: An Improved Algorithm for hypot(x,y)

Published: 08 December 2020 Publication History

Abstract

We develop fast and accurate algorithms for evaluating √x2+y2 for two floating-point numbers x and y. Library functions that perform this computation are generally named hypot(x,y). We compare five approaches that we will develop in this article to the current resident library function that is delivered with Julia 1.1 and to the code that has been distributed with the C math library for decades. We will investigate the accuracy of our algorithms by simulation.

Supplementary Material

ZIP File (1014.zip)
Software for An Improved Algorithm for hypot(x,y)

References

[1]
G. Bohlender. 1977. Floating-point computation of functions with maximum accuracy. IEEE Trans. Computers 26 (1977), 621--632.
[2]
J. E. Bresenham. 1965. Algorithm for computer control of a digital plotter. IBM Syst. J. 4, 1 (1965), 25--30.
[3]
N. Brisebarre, M. Joldes, É. Martin-Dorel, J.-M. Muller, and P. Kornerup. 2011. Augmented precision square roots, 2-d norms, and discussion on correctly rounding . In Computer Arithmetic (ARITH-20). Tübingen, Germany.
[4]
T. J. Dekker. 1971. A floating-point technique for extending the available precision. Numer. Math. 18, 3 (1971), 224--242.
[5]
J. Demmel and Y. Hida. 2003. Accurate and efficient floating-point summation. SIAM J. Scientific Computing 25 (2003), 1214--1248.
[6]
D. Goldberg. 1991. What every computer scientist should know about floating-point arithmetic. ACM Comput. Surv. 23, 1 (1991), 5--48.
[7]
S. Graillat, C. Lauter, P. Tang, N. Yamanaka, and S. Oishi. 2015. Efficient calculations of faithfully rounded l2-norms of n-vectors. ACM Trans. Math. Softw. 41 (2015), 1--20.
[8]
R. J. Hanson and T. Hopkins. 2017. Remark on algorithm 539: A modern Fortran reference implementation for carefully computing the Euclidean norm. ACM Trans. Math. Softw. 44, 3 (2017), Article 24.
[9]
J. Harrison. 1999. A machine-checked theory of floating-point arithmetic. In Theorem Proving in the Higher Order Logics. Lecture Notes in Computer Science, Vol. 1690. Springer, 113--130.
[10]
N. J. Higham. 1993. The accuracy of floating-point summation. SIAM J. Sci. Comput. 14 (1993), 783--799.
[11]
C.-P. Jeannerod, N. Louvet, J.-M. Muller, and A. Panhaleux. 2011. Midpoints and exact points of some algebraic functions in floating-point arithmetic. IEEE Trans. Comput. 60, 2 (2011), 228--241.
[12]
W. Kahan. 1965. Pracniques: Further remarks on reducing truncation errors. Commun. ACM 8, 1 (1965), 40.
[13]
J.-M. Muller, N. Brunie, F. de Dinechin, C.-P. Jeannerod, M. Joldes, V. Lefèvre, G. Melquiond, N. Revol, and S. Torres. 2018. Handbook of Floating-Point Arithmetic. Birkhauser.
[14]
M. Pichat. 1972. Correction d’une somme en arithmetique a virgule flottante. Numer. Math. 19 (1972), 400--406.
[15]
A. Ziv. 1999. Sharp ULP rounding error bound for the hypotenuse function. Math. Comput. 68, 227 (1999), 1143--1148.

Cited By

View all
  • (2024)Accurate complex Jacobi rotationsJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116003450:COnline publication date: 1-Nov-2024
  • (2023)Accurate Calculation of Euclidean Norms Using Double-word ArithmeticACM Transactions on Mathematical Software10.1145/356867249:1(1-34)Online publication date: 21-Mar-2023

Index Terms

  1. Algorithm 1014: An Improved Algorithm for hypot(x,y)

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Mathematical Software
    ACM Transactions on Mathematical Software  Volume 47, Issue 1
    March 2021
    219 pages
    ISSN:0098-3500
    EISSN:1557-7295
    DOI:10.1145/3441641
    Issue’s Table of Contents
    This paper is authored by an employee(s) of the United States Government and is in the public domain. Non-exclusive copying or redistribution is allowed, provided that the article citation is given and the authors and agency are clearly identified as its source.

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 December 2020
    Accepted: 01 October 2020
    Revised: 01 September 2020
    Received: 01 June 2019
    Published in TOMS Volume 47, Issue 1

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. IEEE 754
    2. floating-point
    3. fused multiply-add
    4. hypot()

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)22
    • Downloads (Last 6 weeks)5
    Reflects downloads up to 16 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Accurate complex Jacobi rotationsJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116003450:COnline publication date: 1-Nov-2024
    • (2023)Accurate Calculation of Euclidean Norms Using Double-word ArithmeticACM Transactions on Mathematical Software10.1145/356867249:1(1-34)Online publication date: 21-Mar-2023

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    HTML Format

    View this article in HTML Format.

    HTML Format

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media