fastdiv/
lib.rs

1//! This crate performs fast division by a runtime constant divisor,
2//! by precomputing a division factor that can be used repeatedly.
3//!
4//! # Example
5//! ```
6//! use fastdiv::FastDiv;
7//!
8//! let d: u32 = 3;
9//! let m = d.precompute_div();
10//!
11//! let n1 = 4;
12//! let n2 = 9;
13//!
14//! assert_eq!(n1 / d, n1.fast_div(m));
15//! assert_eq!(n2 / d, n2.fast_div(m));
16//!
17//! assert_eq!(n1 % d, n1.fast_mod(m, d));
18//! assert_eq!(n2 % d, n2.fast_mod(m, d));
19//!
20//! assert_eq!(n1 % d == 0, n1.is_multiple_of(m));
21//! assert_eq!(n2 % d == 0, n2.is_multiple_of(m));
22//! ```
23
24#[inline]
25const fn mul128_u32(lowbits: u64, d: u32) -> u64 {
26    (lowbits as u128 * d as u128 >> 64) as u64
27}
28#[inline]
29const fn mul128_u64(lowbits: u128, d: u64) -> u64 {
30    let mut bottom_half = (lowbits & 0xFFFFFFFFFFFFFFFF) * d as u128;
31    bottom_half >>= 64;
32    let top_half = (lowbits >> 64) * d as u128;
33    let both_halves = bottom_half + top_half;
34    (both_halves >> 64) as u64
35}
36
37#[inline]
38const fn compute_m_u32(d: u32) -> u64 {
39    (0xFFFFFFFFFFFFFFFF / d as u64) + 1
40}
41#[inline]
42const fn fastmod_u32(a: u32, m: u64, d: u32) -> u32 {
43    let lowbits = m.wrapping_mul(a as u64);
44    mul128_u32(lowbits, d) as u32
45}
46// for d > 1
47#[inline]
48const fn fastdiv_u32(a: u32, m: u64) -> u32 {
49    mul128_u32(m, a) as u32
50}
51#[inline]
52const fn is_divisible_u32(n: u32, m: u64) -> bool {
53    (n as u64).wrapping_mul(m) <= m - 1
54}
55
56#[inline]
57const fn compute_m_u64(d: u64) -> u128 {
58    (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF / d as u128) + 1
59}
60#[inline]
61const fn fastmod_u64(a: u64, m: u128, d: u64) -> u64 {
62    let lowbits = m.wrapping_mul(a as u128);
63    mul128_u64(lowbits, d)
64}
65// for d > 1
66#[inline]
67const fn fastdiv_u64(a: u64, m: u128) -> u64 {
68    mul128_u64(m, a)
69}
70#[inline]
71const fn is_divisible_u64(n: u64, m: u128) -> bool {
72    (n as u128).wrapping_mul(m) <= m - 1
73}
74
75/// Allows precomputing the division factor for fast division, modulo, and divisibility checks.
76pub trait FastDiv: Copy {
77    type PrecomputedDiv: Copy;
78    /// Precompute the division factor from the divisor `self`.
79    fn precompute_div(self) -> Self::PrecomputedDiv;
80    /// Divide by the divisor, given the precomputed division factor.
81    fn fast_div(self, precomputed: Self::PrecomputedDiv) -> Self;
82    /// Compute the remainder of the division of `self` by the divisor, given the precomputed division factor and the divisor `d`.
83    /// If the precomputed division factor does not come from the same provided divisor, the
84    /// result is unspecified.
85    fn fast_mod(self, precomputed: Self::PrecomputedDiv, d: Self) -> Self;
86    /// Check if `self` is a multiple of the divisor, given the precomputed division factor.
87    fn is_multiple_of(self, precomputed: Self::PrecomputedDiv) -> bool;
88}
89
90#[derive(Clone, Copy, Eq, PartialEq)]
91pub struct PrecomputedDivU32 {
92    m: u64,
93}
94#[derive(Clone, Copy, Eq, PartialEq)]
95pub struct PrecomputedDivU64 {
96    m: u128,
97}
98
99impl FastDiv for u32 {
100    type PrecomputedDiv = PrecomputedDivU32;
101
102    #[inline]
103    fn precompute_div(self) -> Self::PrecomputedDiv {
104        assert!(self > 1);
105        Self::PrecomputedDiv {
106            m: compute_m_u32(self),
107        }
108    }
109
110    #[inline]
111    fn fast_div(self, precomputed: Self::PrecomputedDiv) -> Self {
112        fastdiv_u32(self, precomputed.m)
113    }
114
115    #[inline]
116    fn fast_mod(self, precomputed: Self::PrecomputedDiv, d: Self) -> Self {
117        fastmod_u32(self, precomputed.m, d)
118    }
119
120    #[inline]
121    fn is_multiple_of(self, precomputed: Self::PrecomputedDiv) -> bool {
122        is_divisible_u32(self, precomputed.m)
123    }
124}
125
126impl FastDiv for u64 {
127    type PrecomputedDiv = PrecomputedDivU64;
128
129    #[inline]
130    fn precompute_div(self) -> Self::PrecomputedDiv {
131        assert!(self > 1);
132        Self::PrecomputedDiv {
133            m: compute_m_u64(self),
134        }
135    }
136
137    #[inline]
138    fn fast_div(self, precomputed: Self::PrecomputedDiv) -> Self {
139        fastdiv_u64(self, precomputed.m)
140    }
141
142    #[inline]
143    fn fast_mod(self, precomputed: Self::PrecomputedDiv, d: Self) -> Self {
144        fastmod_u64(self, precomputed.m, d)
145    }
146
147    #[inline]
148    fn is_multiple_of(self, precomputed: Self::PrecomputedDiv) -> bool {
149        is_divisible_u64(self, precomputed.m)
150    }
151}
152
153#[cfg(test)]
154mod tests {
155    use super::*;
156
157    #[test]
158    fn div_u32() {
159        let n: u32 = 1000;
160        for j in 2..n {
161            let p = j.precompute_div();
162            for i in 0..n {
163                assert_eq!(i.fast_mod(p, j), i % j);
164                assert_eq!(i.fast_div(p), i / j);
165                assert_eq!(i.is_multiple_of(p), i % j == 0);
166            }
167        }
168    }
169
170    #[test]
171    fn div_u64() {
172        let n: u32 = 1000;
173        for j in 2..n {
174            let p = j.precompute_div();
175            for i in 0..n {
176                assert_eq!(i.fast_mod(p, j), i % j);
177                assert_eq!(i.fast_div(p), i / j);
178                assert_eq!(i.is_multiple_of(p), i % j == 0);
179            }
180        }
181    }
182}
fastdiv/lib.rs

fastdiv/
lib.rs
