Module div128

Optimized division algorithms for u128.

Fast Algorithms

The more optimized algorithms for calculating the divisor constants are based off of the paper “Division by Invariant Integers Using Multiplication”, by T. Granlund and P. Montgomery, in “Proc. of the SIGPLAN94 Conference on Programming Language Design and Implementation”, available online here.

This approach is derived from the Rust algorithm for formatting 128-bit values, and therefore is similarly dual-licensed under MIT/Apache-2.0.

Fallback Algorithms

The slower algorithms in this module are derived off of dtolnay/itoa and Rust’s compiler-builtins crate. This copies a specific path of LLVM’s __udivmodti4 intrinsic, which does division/ modulus for u128 in a single step. Rust implements both division and modulus in terms of this intrinsic, but calls the intrinsic twice for subsequent division and modulus operations on the same dividend/divisor, leading to significant performance overhead.

This module calculates the optimal divisors for each radix, and exports a general-purpose division algorithm for u128 where the divisor can fit in a u64. The moderate algorithm is derived from dtolnay/itoa, which can be found here, which in turn is derived from Rust’s compiler-builtins crate, which can be found here.

Licensing for these routines is therefore subject to an MIT/Illinois dual license (a BSD-like license), while the rest of the module is subject to an MIT/Apache-2.0 dual-license.

Generation

See etc/div128.py for the script to generate the divisors and the constants, and the division algorithm.

Functions

• fast_u128_divrem
  Fast division/remainder algorithm for u128, without a fast native approximation.
• moderate_u128_divrem
  Fast division/remainder algorithm for u128, without a fast native approximation.
• pow2_u128_divrem
  Calculate a div/remainder algorithm optimized for power-of-two radixes. This is trivial: the number of digits we process is 64 / log2(radix). Therefore, the shr is log2(radix) * digits, and the mask is just the lower shr bits of the digits.
• slow_u128_divrem
  Optimized fallback division/remainder algorithm for u128.
• u128_divrem
  Calculate the div/remainder of a value based on the radix.