Next Article in Journal
Improved Stability Criteria on Linear Systems with Distributed Interval Time-Varying Delays and Nonlinear Perturbations
Previous Article in Journal
Deep Learning for Fake News Detection in a Pairwise Textual Input Schema
Article

Modified Fast Inverse Square Root and Square Root Approximation Algorithms: The Method of Switching Magic Constants

1
Information Technologies Security Department, Lviv Polytechnic National University, 79013 Lviv, Ukraine
2
Automation and Information Technologies Department, Cracow University of Technology, 31155 Cracow, Poland
3
Information Security Management Department, Lviv State University of Life Safety, 79007 Lviv, Ukraine
*
Author to whom correspondence should be addressed.
Academic Editor: Demos T. Tsahalis
Received: 24 December 2020 / Revised: 26 January 2021 / Accepted: 10 February 2021 / Published: 17 February 2021
(This article belongs to the Section Computational Engineering)
Many low-cost platforms that support floating-point arithmetic, such as microcontrollers and field-programmable gate arrays, do not include fast hardware or software methods for calculating the square root and/or reciprocal square root. Typically, such functions are implemented using direct lookup tables or polynomial approximations, with a subsequent application of the Newton–Raphson method. Other, more complex solutions include high-radix digit-recurrence and bipartite or multipartite table-based methods. In contrast, this article proposes a simple modification of the fast inverse square root method that has high accuracy and relatively low latency. Algorithms are given in C/C++ for single- and double-precision numbers in the IEEE 754 format for both square root and reciprocal square root functions. These are based on the switching of magic constants in the initial approximation, depending on the input interval of the normalized floating-point numbers, in order to minimize the maximum relative error on each subinterval after the first iteration—giving 13 correct bits of the result. Our experimental results show that the proposed algorithms provide a fairly good trade-off between accuracy and latency after two iterations for numbers of type float, and after three iterations for numbers of type double when using fused multiply–add instructions—giving almost complete accuracy. View Full-Text
Keywords: elementary function approximation; fast inverse square root algorithm; IEEE 754 standard; Newton–Raphson method; fused multiply–add; algorithm design and analysis; maximum relative error; optimization; performance evaluation; processors and microprocessors elementary function approximation; fast inverse square root algorithm; IEEE 754 standard; Newton–Raphson method; fused multiply–add; algorithm design and analysis; maximum relative error; optimization; performance evaluation; processors and microprocessors
Show Figures

Figure 1

MDPI and ACS Style

Moroz, L.V.; Samotyy, V.V.; Horyachyy, O.Y. Modified Fast Inverse Square Root and Square Root Approximation Algorithms: The Method of Switching Magic Constants. Computation 2021, 9, 21. https://0-doi-org.brum.beds.ac.uk/10.3390/computation9020021

AMA Style

Moroz LV, Samotyy VV, Horyachyy OY. Modified Fast Inverse Square Root and Square Root Approximation Algorithms: The Method of Switching Magic Constants. Computation. 2021; 9(2):21. https://0-doi-org.brum.beds.ac.uk/10.3390/computation9020021

Chicago/Turabian Style

Moroz, Leonid V., Volodymyr V. Samotyy, and Oleh Y. Horyachyy 2021. "Modified Fast Inverse Square Root and Square Root Approximation Algorithms: The Method of Switching Magic Constants" Computation 9, no. 2: 21. https://0-doi-org.brum.beds.ac.uk/10.3390/computation9020021

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Back to TopTop