Fast and accurate approximation algorithms for computing floating point square root

被引:0
|
作者
Kokosinski, Zbigniew [1 ]
Gepner, Pawel [2 ]
Moroz, Leonid [2 ]
Samotyy, Volodymyr [1 ]
Wegrzyn, Mariusz [1 ]
Gavkalova, Nataliia [2 ]
机构
[1] Cracow Univ Technol, Dept Automat Control & Comp Engn, Warszawska 24, PL-31155 Krakow, Poland
[2] Warsaw Univ Technol, Fac Mech & Ind Engn, Narbutta 85, PL-02524 Warsaw, Poland
关键词
Numerical algorithm; Approximation algorithm; Function approximation; Square root; Newton-Raphson method; Heron formula; NEWTON-RAPHSON CALCULATION; STARTING VALUES;
D O I
10.1007/s11075-024-01932-7
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The square root is one of the most used functions in many different engineering and scientific applications. We propose new methods for calculating the square root function that are based on the Newton-Raphson method with Heron iteration. A modification of Heron's formula combined with an improved selection of the magic constants enables a significant reduction of the maximum relative error (MRE). Simple modifications to the Newton-Raphson formula and the magic number method enable implementation on platforms with limited hardware resources, such as microcontrollers and FPGAs, with variable accuracy. Implementations of new approximation algorithms in the C programming language were carefully tested and evaluated against their software and hardware counterparts on the most popular platforms, e.g., CPUs from Intel, AMD and ARM, GPU from Nvidia and IPU from Graphcore. The proposed numerical algorithms are shown to be superior in terms of computational time, the number of clock cycles, accuracy, MRE, and root mean square deviation.
引用
收藏
页数:24
相关论文
共 50 条
  • [1] Fast floating point square root
    Hain, TF
    Mercer, DB
    AMCS '05: Proceedings of the 2005 International Conference on Algorithmic Mathematics and Computer Science, 2005, : 33 - 39
  • [2] Efficient Floating-Point Square Root and Reciprocal Square Root Algorithms
    Moroz, Leonid
    Samotyy, Volodymyr
    Wegrzyn, Mariusz
    Dzelendzyak, Ulyana
    PROCEEDINGS OF THE THE 11TH IEEE INTERNATIONAL CONFERENCE ON INTELLIGENT DATA ACQUISITION AND ADVANCED COMPUTING SYSTEMS: TECHNOLOGY AND APPLICATIONS (IDAACS'2021), VOL 1, 2021, : 552 - 559
  • [3] A novel approximation scheme for floating-point square root and inverse square root for FPGAs
    Pennestri, Pietro
    Huang, Yanqiu
    Alachiotis, Nikolaos
    2022 11TH INTERNATIONAL CONFERENCE ON MODERN CIRCUITS AND SYSTEMS TECHNOLOGIES (MOCAST), 2022,
  • [4] Modified Fast Inverse Square Root and Square Root Approximation Algorithms: The Method of Switching Magic Constants
    Moroz, Leonid V.
    Samotyy, Volodymyr V.
    Horyachyy, Oleh Y.
    COMPUTATION, 2021, 9 (02) : 1 - 23
  • [5] FAST AND STABLE ALGORITHMS FOR COMPUTING THE PRINCIPAL SQUARE ROOT OF A COMPLEX MATRIX
    SHIEH, LS
    LIAN, SR
    MCINNIS, BC
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1987, 32 (09) : 820 - 822
  • [6] FAST AND STABLE ALGORITHMS FOR COMPUTING THE PRINCIPAL SQUARE ROOT OF A COMPLEX MATRIX.
    Shieh, Leang S.
    Lian, Sui R.
    McInnis, Bayliss C.
    IEEE Transactions on Automatic Control, 1987, AC-32 (09) : 820 - 822
  • [7] Floating point division and square root algorithms and implementation in the AMD-K7™ microprocessor
    Oberman, SF
    14TH IEEE SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 1999, : 106 - 115
  • [8] SIMPLIFIED FLOATING-POINT DIVISION AND SQUARE ROOT
    Viitanen, Timo
    Jaaskelainen, Pekka
    Esko, Otto
    Takala, Jarmo
    2013 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), 2013, : 2707 - 2711
  • [9] Floating Point Square Root under HUB Format
    Villalba-Moreno, Julio
    Hormigo, Javier
    2017 IEEE 35TH INTERNATIONAL CONFERENCE ON COMPUTER DESIGN (ICCD), 2017, : 447 - 454
  • [10] Fast VLSI algorithms for division and square root
    McQuillan, S.E.
    McCanny, J.V.
    Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, 1994, 8 (02): : 151 - 168