CS Paper Radar

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

František Stloukal, Fabienne Jézéquel

cs.MS ·submitted 2026-11-05 17:50 UTC · v1
code/data

Abstract

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.

Comment
46 pages, 8 figures, 3 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Providing Accuracy Guarantees for the Fixed-Point Emulation of Matrix Multiplication

cs.MS cs.DC ·2026-11-13 ·Cole Brower, Peter Caday, John Gunnels
theory similarity 0.66
Abstract · We plan to submit to TOMS, but have not done so

Fixed-point methods such as Ozaki-II emulate double-precision matrix multiplication (GEMM) on fast low-precision hardware. Software that chooses the mantissa bit count automatically is numerically safe when the emulated product keeps the error guarantee of the floating-point GEMM it replaces. We analyze the worst-case and average-case error of fixed-point and floating-point dot products, define exponent span capacities that determine the extra mantissa bits an input requires, and approximate them with a low-precision GEMM. We prove that 53 bits plus such a capacity and a small constant preserve the classical worst-case error bound for a floating-point dot product, and we demonstrate this guarantee in software on several test cases. In a developer build of cuBLAS on an NVIDIA B200, each implemented bit-count rule earns grade~A on Test~2c of ``Grading the BLAS'' at every size and exponent range tested, falling back to double precision at the widest ranges; in exact arithmetic, the bound holds on every adversarial and random input tested.

0.32

A performance enhancement of the Payne-Hanek range reduction algorithm

cs.MS math.NA ·2026-09-28 ·Tue Ly
similarity 0.63
Abstract · Updated to include CORE-MATH newer Payne-Hanek range reduction implementation, and add CRLIBM to performance analysis. Updated the performan…

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.

0.40

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.63
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

When Double Rounding is Correct

cs.PL ·2026-10-06 ·Brett Saiki, Bill Zorn, Cynthia Richey, Zachary Tatlock
similarity 0.62
Abstract

Number libraries, which implement number formats and their arithmetic in software, are used to simulate hardware, making hardware behavior reproducible and thus verifiable and easier to design. However, modern machine learning accelerators are difficult to simulate, as they increasingly use specialized number formats that existing number libraries do not support. It is costly to extend these libraries using traditional methods: each combination of operation, format, and rounding mode typically requires a bespoke implementation. An easier way is to double round - compute at higher precision, then re-round - so that one high-precision kernel serves many formats, but double rounding is only known to be correct in select cases. We give a precise, efficiently checkable characterization of when double rounding is correct across many formats and rounding modes. Our result rests on a novel abstract number format that unifies fixed- and floating-point representations, reducing the correctness of double rounding to format containment: whether every value of one format is representable in another. We mechanized these results in Lean 4. In addition, we introduce a format inference algorithm that, given a sequence of operations, bounds each expression by a number format guaranteed to contain its result. We apply these insights in two ways. First, we present MPFX, a correctly-rounded, multi-precision number library that exploits correct double rounding to efficiently simulate many number formats. MPFX's correctly-rounded operations are up to 11x (mean: 6.05x) faster than MPFR's, and competitive with SoftFloat's - between 0.46x and 1.63x as fast (mean: 0.94x) - at the same precision. Second, in a case study, we implement a software simulation of a hardware specification using both SoftFloat and MPFX's primitives; the MPFX version is up to 13.5x faster.

0.11

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.62
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

Long rational and Gaussian integer multiplication

cs.DS math.NT ·2026-11-13 ·Yuval Spiizer, Raphael S. Steiner
similarity 0.61
Abstract · 38 pages

Long integer multiplication is a fundamental operation in computational algebra, heavily relying on Toom--Cook and related evaluation-interpolation algorithms. Conventional wisdom dictates that multiplication on the Gaussian integers $\mathbb{Z}[i]$ is reduced to standard rational integer multiplication, since $\mathbb{Z}[i]$ is a ring extension of $\mathbb{Z}$. We show that this approach is far from optimal and moreover inverting this established paradigm, that is reducing rational to Gaussian multiplication, leads to faster rational integer multiplication algorithms. We introduce a novel Toom--Cook framework that reduces rational long integer multiplication to Gaussian integer multiplication, yielding a strictly more efficient computational pipeline. By taking advantage of the special properties of the rational integer domain inside the Gaussian integers, we achieve a more favourable algebraic structure that reduces the overall arithmetic cost in every metric. To validate this theoretical shift, we provide a complete implementation of our algorithm. Benchmarks demonstrate that our approach outperforms the highly optimised GNU Multiple Precision Arithmetic Library (GMP) by up to 29\%, bridging a fundamental theoretical insight with significant practical improvements in high-performance computer algebra.

0.20

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.60
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

Taming Bitwise Behavior in GPU Kernels with Tensor Core: Black-Box Reconstruction, Compiler Enforcement, and Static Verification

cs.DC cs.PFcs.PL ·2026-09-10 ·Ziteng Yang, Nicholas J. Riasanovsky, Warren Deng, Vivek Sarkar
hot direction similarity 0.60
Abstract

Determinism and numerical reproducibility are increasingly required of GPU kernels in machine learning systems, yet deterministic implementations of the same kernel can still differ bit for bit. Floating-point reduction order is the primary cause, alongside partial-sum precision, fused multiply-add operations, and rounding placement. These choices may be hand-coded, selected by a block-level language such as Triton, or hidden inside a closed-source library such as cuBLAS or rocBLAS. A tile shape chosen for performance therefore also determines the arithmetic, potentially breaking batch invariance. Preserving a fixed order can cost up to 20 percent, while an autotuner cannot identify which configurations are bitwise equivalent. We characterize the factors determining the bitwise behavior of reductions and general matrix multiplication (GEMM). First, we introduce a descriptor of GEMM reduction order, including the partitioning of K in split-K GEMM. Using it, we perform the first black-box reconstruction of a closed-source library's arithmetic for bit-level correctness. Our family of Triton GEMMs matches NVIDIA cuBLAS in all tested cases on Blackwell and Hopper. For realistic LLM shapes with fused epilogues, it matches or exceeds torch.compile performance. Second, we enforce balanced-tree reduction during Triton lowering and introduce a data-layout optimization that brings 19 of 27 kernels on GB300 and H100 within 10 percent of free-order performance. Third, we develop sound static checkers for bitwise equivalence between compiled GPU kernels, including the first checker spanning NVIDIA PTX and AMD GCN. Integrated into Triton's autotuner, the checker restricts search to a single bit-equivalence class.

0.53