Faster remainder by direct computation: Applications to compilers and software libraries. (27th February 2019)

• Record Type: Journal Article
• Authors: Lemire, Daniel; Kaser, Owen; Kurz, Nathan
• Is Part Of: Software, practice & experience. Volume 49:Number 6(2019)
• Page Start: 953
• Page End: 970
• Publication Date: 2019-02-27
• Subjects: bit manipulation -- divisibility -- integer division; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2689
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: On common processors, integer multiplication is many times faster than integer division. Dividing a numerator n by a divisor d is mathematically equivalent to multiplication by the inverse of the divisor ( n / d = n ∗1/ d ). If the divisor is known in advance, or if repeated integer divisions will be performed with the same divisor, it can be beneficial to substitute a less costly multiplication for an expensive division. Currently, the remainder of the division by a constant is computed from the quotient by a multiplication and a subtraction. However, if just the remainder is desired and the quotient is unneeded, this may be suboptimal. We present a generally applicable algorithm to compute the remainder more directly. Specifically, we use the fractional portion of the product of the numerator and the inverse of the divisor. On this basis, we also present a new and simpler divisibility algorithm to detect nonzero remainders. We also derive new tight bounds on the precision required when representing the inverse of the divisor. Furthermore, we present simple C implementations that beat the optimized code produced by state‐of‐the‐art C compilers on recent x64 processors (eg, Intel Skylake and AMD Ryzen), sometimes by more than 25%. On all tested platforms, including 64‐bit ARM and POWER8, our divisibility test functions are faster than state‐of‐the‐art Granlund‐Montgomery divisibility test functions, sometimes by more than 50%.