#[non_exhaustive]pub enum DivisorU64 {
PowerOfTwo(PowerOfTwoDivisorU64),
Up(UpDivisorU64),
AddIndicator(AddIndicatorDivisorU64),
}Expand description
A u64 divisor, precomputed once to divide many values by it
Division by a divisor that is only known at run time needs a divide instruction.
Self::new precomputes a shift and a mask when the magnitude of the divisor is a
power of two, and otherwise a multiplier, so that each division is a high multiply,
shifts and additions. Self::new picks the variant from the divisor and the target.
To divide many values, match on the variant once, before the loop, and call the
variant’s methods in the loop. They don’t branch on the divisor, so the loop doesn’t
depend on the compiler moving a branch out of it. Move the variant into the loop’s
closure, so that the compiler doesn’t reload its fields through a reference for each
value. Self::wrapping_div_rem matches on each call, so a match can fall back to it
for the variants it doesn’t specialize, including variants added later.
§Example
let values: Vec<u64> = vec![100, 7, 64];
let quotients: Vec<_> = match DivisorU64::new(7).unwrap() {
DivisorU64::PowerOfTwo(d) => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),
DivisorU64::AddIndicator(d) => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),
d => values.iter().map(move |n| d.wrapping_div_rem(*n).0).collect(),
};
assert_eq!(quotients, [14, 1, 9]);Variants (Non-exhaustive)§
This enum is marked as non-exhaustive
PowerOfTwo(PowerOfTwoDivisorU64)
A divisor that is a power of two
Up(UpDivisorU64)
A divisor whose rounded-up multiplier is exact in N bits
AddIndicator(AddIndicatorDivisorU64)
Any other divisor
Implementations§
Source§impl DivisorU64
impl DivisorU64
Source§impl DivisorU64
impl DivisorU64
Sourcepub const fn new(divisor: u64) -> Option<Self>
pub const fn new(divisor: u64) -> Option<Self>
Returns a divisor for divisor, or None if divisor is zero
With p = floor(log2(divisor)), it picks Self::Up when the rounded-up
multiplier floor(2^(N+p) / divisor) + 1 satisfies theorem 4.2 of
Granlund and Montgomery, “Division by Invariant Integers using Multiplication” (1994).
Checking one p is enough, because a multiplier that is exact for a smaller p is
also exact for this one, see
ridiculous_fish, “Labor of Division (Episode I)”.
It picks Self::AddIndicator for any divisor the other variants don’t cover.
§Example
const SEVEN: DivisorU64 = DivisorU64::new(7).unwrap();
assert!(DivisorU64::new(0).is_none());