Fast compensated algorithms for the reciprocal square root, the reciprocal hypotenuse, and givens rotations

Abstract

The reciprocal square root is an important computation for which many very sophisticated algorithms exist (see for example [8, 3, 4] and the references therein). In this paper we develop a simple differential compensation (similar to those developed in [2]) that can be used to improve the accuracy of a naive calculation. The approach relies on the use of the fused multiply-add (FMA) which is widely available in hardware on a variety of modern computer architectures. We first show how compensate by computing an exact Newton step and investigate the properties of this approach. We then show how to leverage the exact Newton step to get a modified compensation which requires one additional FMA and one additional multiplication. This modified method appears to give correctly rounded results experimentally and we show that it can be combined with a square root free method for estimating the reciprocal square root to get a method that is both very fast (in computing environments with a slow square root) and, experimentally, highly accurate. Finally, we show how these approaches can be extended to the reciprocal hypotenuse calculation and the construction of Givens rotations.