CS Paper Radar

A performance enhancement of the Payne-Hanek range reduction algorithm

Tue Ly

cs.MS math.NA ·submitted 2026-09-28 12:16 UTC · v2

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| \ge 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.

Comment
Updated to include CORE-MATH newer Payne-Hanek range reduction implementation, and add CRLIBM to performance analysis. Updated the performance table after fixing the setup

Closest papers

Nearest neighbours by meaning across the whole index.

FIGFLEX: A Mixed-Precision FP-INT GEMM Accelerator Co-Designed with Low-Bit LLM Quantization

cs.AR cs.LG ·2026-10-21 ·Faraz Tahmasebi, Haocheng Xu, Andrew Trauger, Yomal Perera, Zhenyu Tang +2 more
similarity 0.67
Abstract · 15 pages, 12 Figures

Weight-only quantization keeps LLM activations in floating point and stores weights as low-bit integers, turning the dominant workload into floating-point-integer (FP-INT) general matrix multiplication. Recent quantizers reach a 2-3-bit average with mixed precision, but hardware has not kept pace: GPUs dequantize weights to FP16 before the tensor-core multiply-accumulate, and bit-parallel FP-INT accelerators run at a single weight precision, so fewer bits save memory but not computation. In this paper, we present FIGFLEX, an algorithm-hardware co-designed mixed-precision accelerator whose bit-parallel datapath scales throughput as precision falls. FIGFLEX contributes (1) a shift-add, radix-4 reformulation of FP-INT multiplication that fuses the multiply-accumulate into a unified, precision-flexible partial-product reduction and roughly halves the partial products, together with a novel INT3 optimization that reclaims the idle datapath radix-4 leaves at that precision; and (2) a mixed-precision quantizer that assigns each channel group its bit-width according to the error GPTQ cannot compensate, with a per-input-channel column scaling whose power-of-two normalization keeps the scaled activations out of the FP16 subnormal range, so that the quantized model maps directly onto FIGFLEX's datapath with the same accuracy as on a GPU. On LLaMA-2-7B, FIGFLEX attains 5.85 and 8.77 WikiText-2 perplexity at 3- and 2-bit average precision, lower than GPTQ, AWQ, SliM-LLM, AMQ, and QuIP# (without fine-tuning), while delivering 1.56x and 1.42x higher whole-chip throughput per area on the linear GEMMs of a 3-bit mixed-precision model than AxCore and FIGLUT, respectively.

0.13

FPScan: An Automated Constraint-Based Analyzer for Floating-Point Anomaly Detection

cs.SE math.NA ·2026-09-07 ·Julien Bortolussi, Dorra Ben Khalifa, Pierre-Loïc Garoche
benchmark similarity 0.64
Abstract · 12 pages , 7 Figures, 28th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

Writing error-free floating-point programs is a challenging task, especially for programmers who lack a strong background in numerical analysis and rounding-error propagation. State-of-the-art techniques typically aim to bound such errors using static or dynamic analysis. However, only a few tools explicitly address critical floating-point pitfalls such as absorption and catastrophic cancellation. These anomalies represent situations in which rounding errors are significantly amplified, causing the semantics of the finite-precision computation to deviate substantially from the real-number semantics. In this article, we present FPScan, a novel tool to formally define and detect both catastrophic cancellation and absorption in floating-point programs. Our approach starts with a custom static analyzer based on abstract interpretation to infer the order of magnitude of all program variables. This magnitude information is then used to build a set of first-order constraints that model error propagation and numerical precision within the program. Finally, we employ an off-the-shelf SMT solver to determine whether the program exhibits any of these critical numerical pitfalls. Experiments were conducted on FPBench, a well-known benchmark suite of floating-point programs, to evaluate the effectiveness of our tool. We also present a comparison with state-of-the-art tools regarding soundness and analysis time.

0.26

Lord of the Precision, the Two Floats: Double-Word Arithmetic for Complex Numbers

cs.MS ·2026-11-05 ·František Stloukal, Fabienne Jézéquel
code/data similarity 0.63
Abstract · 46 pages, 8 figures, 3 tables

Datacenter GPUs increasingly favour low-precision floating-point formats, offering higher throughput than FP64. Double-word (DW) arithmetic represents numbers as unevaluated sums of two floating-point values, providing higher accuracy. We present the first error analysis of complex DW multiplication and division. Both operations reduce to sums of two DW products, combined using one of three DW addition algorithms: accurate, sloppy, or Madd. Normalising DW products ensures nonoverlapping components, but omitting this step reduces the number of arithmetic operations. We bound the resulting overlap and prove that Madd retains a relative error bound of $3u^2+O(u^3)$ for overlapping inputs, where $u$ is the unit roundoff. For all variants, we establish relative error bounds of the form $(ακ+β)u^2+O(u^3)$, where $κ$ is the condition number of the sum of products. Our analysis shows that the less expensive sloppy addition suffices. We implement these variants in CompleXDW, an open-source C++ library for CPUs and GPUs. In the high-energy physics code MadGraph7, FP32-based DW arithmetic achieves up to 2.9x and 2.1x higher throughput than FP64 on NVIDIA L40S and AMD Radeon Pro W7900 GPUs, respectively, while losing approximately 1.4 correct significant digits.

0.39

TR-PTQ: High-Accuracy Integer-Only Transformer Post Training Quantization via Taylor Region Reformulation

cs.LG ·2026-10-07 ·Eliyahu Levy, Adam Teman, Yoni Pugachov
similarity 0.63
Abstract

Post-training quantization (PTQ) enables efficient deployment, yet transformer architectures remain challenging to quantize due to nonlinear layers. While existing methods attribute accuracy loss to insufficient numerical precision, often necessitating floating-point fallbacks, we demonstrate that degradation is actually driven by specific structural error sources. We find that learned scale parameters in normalization layers and compounded approximations in GELU are the primary error contributors, whereas SoftMax remains inherently robust to aggressive quantization. To address these bottlenecks, we introduce TR-PTQ, a unified integer-only formulation using shared Taylor Region (TR) exponential and logarithm primitives. This approach allows computationally expensive operations, including division and square roots, to be performed entirely in the log-domain via standard integer arithmetic. Combined with a calibration-free, outlier-aware optimization for LayerNorm parameters, our method eliminates the need for floating-point hardware units for nonlinearities, achieving less than 1.5\% absolute accuracy degradation across vision and language benchmarks.

0.23

The Rise of Low Precision Floating Point

cs.MS cs.ARcs.LGmath.NA ·2026-10-30 ·Guy Lemieux, Michael L. Overton
similarity 0.61
Abstract

Floating point computing has dominated scientific computations since the 1950s because of its versatile ability to approximate real numbers with both sufficiently high precision and sufficiently great range. Since 1985, two specific formats have become standard across the industry, one with 32 bits which is adequate for many purposes and one with 64 bits which allows numbers with both much higher precision and much greater range for applications where these are needed. However, during the past decade, deep learning has come to dominate computation, and narrower floating point formats with lower precision and reduced range have steadily become more common. In this article we discuss this phenomenon, why it is happening, how various 16-bit, 8-bit and even 4-bit floating point formats have been developed, and efforts to standardize these formats.

0.14

What Bloats Your Floats? Right-Sizing Numerical Precision for Scientific Computing

cs.DC ·2026-10-06 ·Pratyai Mazumder, Alexandru Calotoiu, Marcin Copik, Yakup Koray Budanaz, Shriram Chandran +1 more
published similarity 0.61
Abstract · Accepted at SC '26: The International Conference for High Performance Computing, Networking, Storage, and Analysis, November 15-20, 2026, Ch…

While FP64 (binary64) remains the standard representation of real numbers in scientific computing, hardware trends increasingly favor low-precision formats optimized for AI workloads. This shift prioritizes throughput and energy efficiency over full-precision capabilities. We challenge the necessity of high-precision arithmetic in PDE-governed simulations, where spatial and temporal discretization errors introduce a physical noise floor that masks the lower-order bits of the FP64 format, rendering them irrelevant. We propose a criterion based on the Signal-to-Noise Ratio (SNR) with respect to spatial and temporal refinements to evaluate the impact of safe precision reduction on scientific computations. Finally, we present an automated dataflow-centric workflow for targeted lowering within mixed-precision subgraphs in complex scientific applications. Large-scale evaluations of weather and climate applications show that strategic precision reduction on GPUs achieves up to 1.8x speedup without compromising physical fidelity.

0.36

TQIR: Trellis Quantization with Integer Reconstruction for Bandwidth-Efficient Edge LLM Acceleration

cs.AR ·2026-11-11 ·Kuang-Ting Huang, Tian-Sheuan Chang
similarity 0.61
Abstract · submitted to IEEE transactions on circuits and systems for AI

Autoregressive large language model (LLM) inference is often limited by external-memory bandwidth, while existing ultra-low-bit trellis quantization reconstructs floating-point weights and leaves runtime Hadamard-transform and decoder costs unresolved. This paper presents TQIR, an algorithm--hardware co-design that decouples storage precision ($S$) from decoded-weight ($W$) and activation ($A$) compute precisions, enabling a better accuracy--hardware trade-off. TQIR performs trellis matching with floating-point candidates offline while constraining each candidate to an INT8 or INT4 codeword that can be reproduced exactly for integer GEMM at runtime. To reduce transform cost while preserving the integer weight path, TQIR relocates the reverse Hadamard transform to the activation side and employs an $H_{128}$ Subspace Hadamard Transform, together with a subspace-aligned $128\times2$ trellis tile that preserves the original 256-weight sequence length. The configurable decoder, synthesized in a TSMC 16-nm process, delivers 307.2~Gweights/s in 0.0509~mm$^2$ and achieves 13.93$\times$ and 1.52$\times$ the normalized decoder-area efficiency of Ecco and Codeword Decomposition, respectively. These results show that fixed-rate trellis compression can reduce weight traffic while sustaining an integer-GEMM datapath matched to the evaluated memory and PE rates.

0.05

FloatLib: Verified Floating-Point Arithmetic in Lean

cs.LO cs.PL ·2026-09-16 ·Robert Joseph George, Will Adkisson, Anima Anandkumar
code/data similarity 0.61
Abstract · 30 pages, 7 figures, 6 tables. Software and evaluation artifacts available at https://github.com/lean-dojo/FloatLib

We present FloatLib, a verified arbitrary-precision floating-point arithmetic library in Lean 4 that combines broad format coverage, machine-checked correctness, and efficient certified execution. To our knowledge, FloatLib is the first Lean library to unify IEEE binary and decimal arithmetic, arbitrary-width posits, P3109, and user-defined formats and rounding rules behind interchangeable certified software backends. Every certified backend is proved equal to a complete encoded specification, preserving signed zeros and exceptional values, while numerical theorems connect execution to real rounding, error bounds, and exactness. FloatLib combines exhaustive certified tables for small formats with verified word and limb kernels based on guard-and-sticky invariants and independently checked quotient candidates. Its posit development additionally proves standard rounding thresholds and exact quire accumulation within capacity for arbitrary widths. Across matched workloads, FloatLib achieves speedups of up to 1.46x over FLoPS and 116x over Universal, while remaining slower in some regimes such as binary arithmetic against MPFR. Independent conformance testing includes more than 102 million TestFloat evaluations with zero differences under the tested relation. We release the library, proofs, benchmarks, evaluation data, and guide as open source.

0.38