Generalising the Fast Reciprocal Square Root Algorithm

Mike Day

AI summary · arXiv: 2307.15600v1 · math.NA

Generalising the Fast Reciprocal Square Root Algorithm

Mike Day

Original paper Submitted to arXiv on 28 Jul. 2023 19 pages, 8 figures License: CC BY 4.0

How to read this summary? Illustrated guide

The essentials

The Fast Reciprocal Square Root Algorithm is a well-established approximation technique
It was widely used before microprocessors had built-in hardware support for computing reciprocal square roots
The algorithm consists of two stages: coarse approximation and refinement through Newtonian iteration or improved expressions with numerical constants
Changing the numerical constants in the algorithm can reduce error without increasing execution cost
Modifying the constants can result in a threefold reduction in error
There was no mathematical framework developed to apply the same technique to approximate arbitrary powers of x or generate optimal coefficients for polynomials of arbitrary degree in the refinement steps
Hardware platforms often provide machine-level instructions to accelerate reciprocal square root calculations, but there may still be benefits to developing improved approximation techniques
This paper aims to generalize the Fast Reciprocal Square Root Algorithm for all rational powers and extend support for any polynomial degree(s) in the refinement step(s)
The paper provides a procedure that automatically constructs provably optimal constants for all cases under certain assumptions and unlimited floating-point precision
Using monic refinement polynomials yields better results compared to using general polynomials in terms of cost/accuracy tradeoff
The paper analyzes further extensions and presents several new best approximations

Key points written by AI: they may contain errors, check them against the paper.

AI-generated keywords: Fast Reciprocal Square Root Algorithm

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

The Fast Reciprocal Square Root Algorithm is a well-established approximation technique that has been widely used before microprocessors had built-in hardware support for computing reciprocal square roots. The algorithm consists of two stages: first, a coarse approximation is obtained by manipulating the bit pattern of the floating-point argument using integer instructions, and second, the coarse result is refined through one or more steps using Newtonian iteration or improved expressions with carefully chosen numerical constants. Subsequent work by various researchers has shown that changing the numerical constants in the algorithm can lead to a significant reduction in error without increasing execution cost. This work analyzed the code and found that modifying the constants could result in a threefold reduction in error. Despite these improvements, there was no mathematical framework developed to apply the same technique to approximate arbitrary powers of x or automatically generate optimal coefficients for polynomials of arbitrary degree in the refinement steps. This limitation hindered generalization of the algorithm for other fixed fractional powers. In present-day microprocessors, hardware platforms often provide machine-level instructions to accelerate reciprocal square root calculations. However, since library functions like pow() are usually more computationally expensive than calculating reciprocal square roots, there may still be benefits to developing improved approximation techniques. This paper aims to address these limitations and generalize the Fast Reciprocal Square Root Algorithm for all rational powers. It also extends support for any polynomial degree(s) in the refinement step(s). Under certain assumptions and unlimited floating-point precision, this paper provides a procedure that automatically constructs provably optimal constants for all these cases. Additionally, it is demonstrated that using monic refinement polynomials yields results that are better placed with respect to cost/accuracy tradeoff compared to using general polynomials. The paper also analyzes further extensions and presents several new best approximations. Overall, this research expands on existing Fast Reciprocal Square Root Algorithm by refining it with improved numerical constants and generalizing it to cater to all rational powers. The paper provides a mathematical framework for constructing optimal constants and demonstrates advantages of using monic refinement polynomials which have potential to enhance accuracy and efficiency of approximation techniques for computing reciprocal square roots and other fixed fractional powers.

Exploring the Fast Reciprocal Square Root Algorithm

The Fast Reciprocal Square Root Algorithm (FRSRA) is a well-established approximation technique that has been widely used before microprocessors had built-in hardware support for computing reciprocal square roots. This algorithm consists of two stages: first, a coarse approximation is obtained by manipulating the bit pattern of the floating-point argument using integer instructions, and second, the coarse result is refined through one or more steps using Newtonian iteration or improved expressions with carefully chosen numerical constants.

Previous Work on FRSRA

Subsequent work by various researchers has shown that changing the numerical constants in the algorithm can lead to a significant reduction in error without increasing execution cost. This work analyzed the code and found that modifying the constants could result in a threefold reduction in error. Despite these improvements, there was no mathematical framework developed to apply this same technique to approximate arbitrary powers of x or automatically generate optimal coefficients for polynomials of arbitrary degree in refinement steps. This limitation hindered generalization of FRSRA for other fixed fractional powers.

Modern Microprocessor Support

In present-day microprocessors, hardware platforms often provide machine-level instructions to accelerate reciprocal square root calculations. However, since library functions like pow() are usually more computationally expensive than calculating reciprocal square roots, there may still be benefits to developing improved approximation techniques.

Extending FRSRA

This paper aims to address these limitations and generalize FRSRA for all rational powers. It also extends support for any polynomial degree(s) in refinement step(s). Under certain assumptions and unlimited floating-point precision, this paper provides a procedure that automatically constructs provably optimal constants for all these cases. Additionally, it is demonstrated that using monic refinement polynomials yields results that are better placed with respect to cost/accuracy tradeoff compared to using general polynomials. The paper also analyzes further extensions and presents several new best approximations which have potential applications beyond computing reciprocal square roots such as calculating other fixed fractional powers like cube root etc..

Conclusion

Overall, this research expands on existing Fast Reciprocal Square Root Algorithm by refining it with improved numerical constants and generalizing it to cater to all rational powers while providing an automated procedure for constructing optimal coefficients based on certain assumptions about unlimited floating point precision available at runtime . The paper demonstrates advantages of using monic refinement polynomials which have potential applications beyond computing reciprocal square roots such as calculating other fixed fractional powers like cube root etc., thus enhancing accuracy and efficiency of approximation techniques used today across multiple platforms including modern microprocessors with built-in hardware support for accelerating calculations involving reciprocals or fractions thereof..

Created on 01 Aug. 2023

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

AI assistant instructions?

Tools for this paper

Explain it differently 3 free rewrites left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

Related
Fractional Newton-Raphson Method
A. Torres-Hernandez, F. Brambila-Paz · 2017 · Applied Mathematics and Sciences: An International Journal (MathSJ), 8:1-13, 2021 · Not summarized yet

Abstract
The Newton-Raphson (N-R) method is useful to find the roots of a polynomial of degree n. However, this method is limited since it diverges for the case in which polynomials only have complex roots if a real initial condition is taken. In the present work, we explain an iterative method that is created using the fractional calculus, which we will call the Fractional Newton-Raphson (F N-R) Method, which has the ability to enter the space of complex numbers given a real initial condition, which allows us to find both the real and complex roots of a polynomial unlike the classical Newton-Raphson method.
Related
Isomeric trees and the order of Runge--Kutta methods
John C. Butcher, Helmut Podhaisky · 2021 · Numerical Analysis · AI summary available

Abstract
The conditions for a Runge--Kutta method to be of order $p$ with $p\ge 5$ for a scalar non-autonomous problem are a proper subset of the order conditions for a vector problem. Nevertheless, Runge--Kutta methods that were derived historically only for scalar problems happened to be of the same order for vector problems. We relate the order conditions for scalar problems to factorisations of the Runge--Kutta trees into "atomic stumps" and enumerate those conditions up to $p=20$. Using a special search procedure over unsatisfied order conditions, new Runge--Kutta methods of "ambiguous orders" five and six are constructed. These are used to verify the validity of the results.
Related
Convergence Analysis for Nonlinear GMRES
Yunhui He · 2025 · Numerical Analysis · AI summary available

Abstract
In this work, we revisit nonlinear generalized minimal residual method (NGMRES) applied to nonlinear problems. NGMRES is used to accelerate the convergence of fixed-point iterations, which can substantially improve the performance of the underlying fixed-point iterations. We consider NGMRES with a finite window size $m$, denoted as NGMRES($m$). However, there is no convergence analysis for NGMRES($m$) applied to nonlinear systems. We prove that for general $m>0$, the residuals of NGMRES($m$) converge r-linearly under some conditions. For $m=0$, we prove that the residuals of NGMRES(0) converge q-linearly.
Related
An embedded corrector problem for homogenization. Part II: Algorithms and discretization
Eric Cancès, Virginie Ehrlacher, Frederic Legoll et al. · 2018 · Numerical Analysis · Not summarized yet

Abstract
This contribution is the numerically oriented companion article of the work [E. Canc\`es, V. Ehrlacher, F. Legoll, B. Stamm and S. Xiang, arxiv preprint 1807.05131]. We focus here on the numerical resolution of the embedded corrector problem introduced in [E. Canc\`es, V. Ehrlacher, F. Legoll and B. Stamm, CRAS 2015; E. Canc\`es, V. Ehrlacher, F. Legoll, B. Stamm and S. Xiang, arxiv preprint 1807.05131] in the context of homogenization of diffusion equations. Our approach consists in considering a corrector-type problem, posed on the whole space, but with a diffusion matrix which is constant outside some bounded domain. In [E. Canc\`es, V. Ehrlacher, F. Legoll, B. Stamm and S. Xiang, arxiv p…
Related
Tensor-Product Split-Simplex Summation-By-Parts Operators
Zelalem Arega Worku, Jason E. Hicken, David W. Zingg · 2024 · Numerical Analysis · AI summary available

Abstract
We present an approach to construct efficient sparse summation-by-parts (SBP) operators on triangles and tetrahedra with a tensor-product structure. The operators are constructed by splitting the simplices into quadrilateral or hexahedral subdomains, mapping tensor-product SBP operators onto the subdomains, and assembling back using a continuous-Galerkin-type procedure. These tensor-product split-simplex operators do not have repeated degrees of freedom at the interior interfaces between the split subdomains. Furthermore, they satisfy the SBP property by construction, leading to stable discretizations. The accuracy and sparsity of the operators substantially enhance the efficiency of SBP dis…
Related
DelayDiffEq: Generating Delay Differential Equation Solvers via Recursive Embedding of Ordinary Differential Equation Solvers
David Widmann, Chris Rackauckas · 2022 · Numerical Analysis · AI summary available

Abstract
Traditional solvers for delay differential equations (DDEs) are designed around only a single method and do not effectively use the infrastructure of their more-developed ordinary differential equation (ODE) counterparts. In this work we present DelayDiffEq, a Julia package for numerically solving delay differential equations (DDEs) which leverages the multitude of numerical algorithms in OrdinaryDiffEq for solving both stiff and non-stiff ODEs, and manages to solve challenging stiff DDEs. We describe how compiling the ODE integrator within itself, and accounting for discontinuity propagation, leads to a design that is effective for DDEs while using all of the ODE internals. We highlight som…
Related
A robust monolithic solver for phase-field fracture integrated with fracture energy based arc-length method and under-relaxation
Ritukesh Bharali, Somdatta Goswami, Cosmin Anitescu et al. · 2021 · Numerical Analysis · AI summary available

Abstract
The phase-field fracture free-energy functional is non-convex with respect to the displacement and the phase field. This results in a poor performance of the conventional monolithic solvers like the Newton-Raphson method. In order to circumvent this issue, researchers opt for the alternate minimization (staggered) solvers. Staggered solvers are robust for the phase-field based fracture simulations as the displacement and the phase-field sub-problems are convex in nature. Nevertheless, the staggered solver requires very large number of iterations (of the order of thousands) to converge. In this work, a robust monolithic solver is presented for the phase-field fracture problem. The solver adop…
Related
Thirty years of the finite volume method for solid mechanics
Philip Cardiff, Ismet Demirdžić · 2018 · Numerical Analysis · AI summary available

Abstract
Since early publications in the late 1980s and early 1990s, the finite volume method has been shown suitable for solid mechanics analyses. At present, there are several flavours of the method, which can be classified in a variety of ways, such as grid arrangement (cell-centred vs staggered vs vertex-centred), solution algorithm (implicit vs explicit), and stabilisation strategy (Rhie-Chow vs Jameson-Schmidt-Turkel vs Godunov upwinding). This article gives an overview, historical perspective, comparison and critical analysis of the different approaches where a close comparison with the de facto standard for computational solid mechanics, the finite element method, is given. The article finish…

Go further

How are these papers found?

We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.

For now only among the papers summarized on this site: search again to add the prior work, the follow-ups and Semantic Scholar’s recommendations.

The previous summary was created more than a year ago and can be re-run (if necessary) by clicking on the Run button below.

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.