A performance enhancement of the Payne-Hanek range reduction algorithm
Abstract
Range reduction plays a crucial role in the accuracy and performance of evaluating trigonometric functions, and is often the primary bottleneck for large floating-point inputs. While fast algorithms such as Cody--Waite work efficiently over narrow intervals, the Payne--Hanek algorithm remains the standard technique for accurate reduction across large floating-point inputs. However, many existing implementations of Payne--Hanek suffer from high latency due to heavy branching, conversion overheads, and the use of multi-word integer arithmetic, which hinders SIMD vectorization. In this paper, we analyze and present a branch-free variation of the Payne--Hanek algorithm using only floating-point arithmetic. Our method operates directly over large double-precision inputs (|x| ≥ 216) and is well suited to hardware with FMA instructions. We formulate the precision constraints in terms of a truncation error budget, construct a compact lookup table indexed by the input exponent, and prove that the scaled reduced argument has absolute error below 2−110 and relative error below 2−60 for every input, including worst cases. The same routine can serve both as the complete range reduction of a single-stage implementation and as the fast path of a correctly rounded one, achieving higher throughput than existing implementations and lower latency than those returning a double-double reduced argument. The algorithm is currently implemented in the LLVM libc project.
Related
- Kruskal-style algorithm for Boltzmann equation molecule reduction
- Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
- Dimension Reduction for the Trivariate Normal Product Distribution: An Efficient Numerical Algorithm via Conditional Expectation
- Measurement-dependent reduction of open dynamics in the quantum phase estimation algorithm: the visible subspace and the damped Fejér kernel
- A note on the failure of Payne's inequality on manifolds with boundary
BibTeX
@misc{ly2026performance,
title = {{A performance enhancement of the Payne-Hanek range reduction algorithm}},
author = {Tue Ly},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.35015},
eprint = {2609.35015},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35015},
}
RIS
TY - UNPB
TI - A performance enhancement of the Payne-Hanek range reduction algorithm
AU - Tue Ly
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.35015
UR - https://arxiv.org/abs/2609.35015
AB - Range reduction plays a crucial role in the accuracy and performance of evaluating trigonometric functions, and is often the primary bottleneck for large floating-point inputs. While fast algorithms such as Cody--Waite work efficiently over narrow intervals, the Payne--Hanek algorithm remains the standard technique for accurate reduction across large floating-point inputs. However, many existing implementations of Payne--Hanek suffer from high latency due to heavy branching, conversion overheads, and the use of multi-word integer arithmetic, which hinders SIMD vectorization. In this paper, we analyze and present a branch-free variation of the Payne--Hanek algorithm using only floating-point arithmetic. Our method operates directly over large double-precision inputs (|x| ≥ 2^16) and is well suited to hardware with FMA instructions. We formulate the precision constraints in terms of a truncation error budget, construct a compact lookup table indexed by the input exponent, and prove that the scaled reduced argument has absolute error below 2^−110 and relative error below 2^−60 for every input, including worst cases. The same routine can serve both as the complete range reduction of a single-stage implementation and as the fast path of a correctly rounded one, achieving higher throughput than existing implementations and lower latency than those returning a double-double reduced argument. The algorithm is currently implemented in the LLVM libc project.
ER -