On GPU Implementation for Multi-Precision Integer Division

Jul 16, 2026

This paper studies efficient implementation of fast integer division on general-purpose GPUs, focusing on a Newton-iteration method based on a shifted-inverse operation. The approach keeps computations entirely in the integer domain and uses data-parallel operators such as multi-precision multiplication, addition, subtraction, comparison, and shifts. The work delivers a CUDA implementation for integer precisions from 215 to 218 bits, includes algorithmic refinements, and proposes a multiplication-focused cost model with evaluation showing near-optimal performance.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

Introduction

Multi-precision integers and GPU motivation

Existing GPU support and the midsize precision regime

Shifted-inverse division and implementation challenges

Paper contributions and scope

arXiv :2606 .06386v2 [ cs .DC] 11 Jul 2026 On GPU Implementation for Multi-Precision Integer Division Martin B. Marchioro 1 , Aske N. Raahauge 1 , Marc I. Løvenskjold 1 , Cosmin E. Oancea 1 , and Stephen M. Watt2 1 DIKU, University of Copenhagen, Copenhagen 2100, Denmark [martin.marchioro@gmail.com](martin.marchioro@gmail.com) , [aske.n.r@di.ku.dk](aske.n.r@di.ku.dk) , [Marc.ivan95@gmail.com](Marc.ivan95@gmail.com) , [cosmin.oancea@di.ku.dk](cosmin.oancea@di.ku.dk) [0000−0001−5421−6876] 2 Cheriton School of Computer Science, University of Waterloo, Canada [smwatt@uwaterloo.ca](smwatt@uwaterloo.ca) [0000−0001−8303−4983] Abstract. This paper presents the issues arising in implementing a fast integer division algorithm on general purpose GPUs. The algorithm uses a Newton iteration based on the shifted inverse operation, keeping all arithmetic in the integer domain and relying on data-parallel operators. The principal contribution is an efficient GPU/cuda implementation for integer precisions from 215 to 218 – sizes not supported by cgbn division. We propose algorithmic refinements, define a cost model in terms of multiplications, build on prefix sums and previous work on multi-precision multiplication, and present an evaluation showing near-optimal performance relative to the model for the target precision. Keywords: Big integer arithmetic · cuda · Data-parallel programming · GPGPU · High-level parallel languages · High-performance computing 1 Introduction Multi-precision integer arithmetic is a basic component of computer algebra, cryptography, exact scientific computation, and symbolic-numeric software. Its performance matters not only for isolated large computations, but also for applications that require many independent integer operations at the same precision. This makes GPUs attractive: they offer high arithmetic throughput and massive parallelism, provided that the computation can be organized to keep data movement and inter-thread communication under control. Existing GPU support for multi-precision integers is strongest at relatively small precisions, where one arithmetic instance can be mapped to a small cooperative group of threads. The nvidia cgbn library (Cooperative Groups Big Numbers) is an important example of this approach [29] . Such libraries provide very high performance in their intended range, but they do not cover all practically interesting sizes. In particular, there is a middle range of integer precisions—large enough that warp-level methods become strained, but still small enough that a complete arithmetic instance can fit within the fast memories of a single GPU thread block. This paper is concerned with this midsize regime. 2 Marchioro, Raahauge, Løvenskjold, Oancea, Watt In previous work we studied GPU implementations of multi-precision addition and multiplication in this regime [32] . That work showed that the classical algorithms, when scheduled carefully, can be made effective on GPUs by assigning one multi-precision operation to a cuda block, keeping operands and intermediate values in registers or shared memory, and minimizing global-memory traffic. It also showed that such algorithms can be expressed in a high-level data-parallel language such as Futhark, although some low-level transformations needed for peak performance remain beyond the current compiler. Division is a more demanding operation. It is not a simple local operation on digits, and the usual high-performance approach is to reduce division to multiplication by first computing an approximation to the reciprocal of the divisor. In conventional Newton iteration this typically requires working in a domain where such reciprocals exist, which can introduce multiple precision floating-point approximations and interactions between different arithmetic domains. For exact integer arithmetic this is undesirable: the implementation must preserve exactness while still exposing enough parallelism for the GPU.

FAQs

What division approach does the paper use on GPUs?

It uses a Newton iteration formulated from a whole shifted inverse rather than a reciprocal, enabling arithmetic to remain in the integer domain while using data-parallel operators.

What precisions does the proposed CUDA implementation target?

The implementation targets integer precisions from 215 to 218 bits, specifically addressing sizes that are not supported by the cgbn division library approach.

What implementation refinements are highlighted for correctness on unsigned integers?

The paper describes explicit sign handling in close-product computation and quotient correction to address cases where the shifted inverse may overestimate by one.

Jul 16, 2026

Upload by Emma Wilson