{"ID":3083594,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T09:00:11.459356253Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.06386","arxiv_id":"2606.06386","title":"On GPU Implementation for Multi-Precision Integer Division","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 $2^{15}$ to $2^{18}$ -- 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.","short_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...","url_abs":"https://arxiv.org/abs/2606.06386","url_pdf":"https://arxiv.org/pdf/2606.06386v1","authors":"[\"Martin B. Marchioro\",\"Aske N. Raahauge\",\"Marc I. Løvenskjold\",\"Cosmin E. Oancea\",\"Stephen M. Watt\"]","published":"2026-06-04T16:51:22Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.MS\",\"cs.SC\"]","methods":"[]","has_code":false}