Module lexical_util::div128
source · Expand description
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 division/remainder algorithm for u128, without a fast native approximation.
- Fast division/remainder algorithm for u128, without a fast native approximation.
- Calculate a div/remainder algorithm optimized for power-of-two radixes.
- Optimized fallback division/remainder algorithm for u128.
- Calculate the div/remainder of a value based on the radix.