Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets

Mitsunari Shigeo, Hoshino Takashi · 2026

Read Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets by Mitsunari Shigeo, Hoshino Takashi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-07902.txt.

Description

Mitsunari and Hoshino optimize 32-bit unsigned division by constants for 64-bit processors. The Granlund-Montgomery method, improved by later work and adopted by major compilers, still generates code shaped for 32-bit CPUs in cases like division by seven. Their method exploits 64-bit capabilities that the older code leaves unused. Patches implemented for LLVM and GCC reach speedups of 1.67 times on an Intel Xeon w9-3495X and about double on an Apple M4 in microbenchmarks. The LLVM patch has already merged into LLVM main, showing the approach works in practice.

Catalog record

CREATORMitsunari Shigeo, Hoshino Takashi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14109
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.07902

Browse the full library · About the Tower of Babel