Skip to main content

utils/
number.rs

1//! Traits for using numbers as generic data types.
2
3use std::fmt::Debug;
4use std::iter::{Product, Sum};
5use std::ops::{
6    Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
7    Mul, MulAssign, Neg, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
8};
9
10/// Trait implemented by the primitive number types, combining common supertraits.
11pub trait Number:
12    Copy
13    + Debug
14    + Default
15    + PartialEq
16    + PartialOrd
17    + Add<Output = Self>
18    + AddAssign
19    + Div<Output = Self>
20    + DivAssign
21    + Mul<Output = Self>
22    + MulAssign
23    + Rem<Output = Self>
24    + RemAssign
25    + Sub<Output = Self>
26    + SubAssign
27    + Sum<Self>
28    + for<'a> Sum<&'a Self>
29    + Product<Self>
30    + for<'a> Product<&'a Self>
31{
32    const ZERO: Self;
33    const ONE: Self;
34    const MIN: Self;
35    const MAX: Self;
36
37    #[must_use]
38    fn abs(self) -> Self;
39    #[must_use]
40    fn rem_euclid(self, rhs: Self) -> Self;
41    #[must_use]
42    fn squared_diff(self, rhs: Self) -> Self;
43}
44
45/// Trait implemented by the primitive signed integer and floating point types.
46pub trait Signed: Number + Neg<Output = Self> + From<i8> {
47    const MINUS_ONE: Self;
48}
49
50/// Trait implemented by the primitive integer types.
51pub trait Integer:
52    Number
53    + Not<Output = Self>
54    + BitAnd<Output = Self>
55    + BitAndAssign
56    + BitOr<Output = Self>
57    + BitOrAssign
58    + BitXor<Output = Self>
59    + BitXorAssign
60    + Shl<Output = Self>
61    + Shl<u32, Output = Self>
62    + ShlAssign
63    + ShlAssign<u32>
64    + Shr<Output = Self>
65    + Shr<u32, Output = Self>
66    + ShrAssign
67    + ShrAssign<u32>
68    + TryInto<i128>
69    + From<bool>
70{
71    type NonZero: Copy + TryFrom<Self> + Into<Self>;
72    type Unsigned: UnsignedInteger<Signed = Self::Signed>;
73    type Signed: SignedInteger<Unsigned = Self::Unsigned>;
74
75    const BITS: u32;
76
77    #[must_use]
78    fn abs_diff(self, rhs: Self) -> Self::Unsigned;
79    #[must_use]
80    fn checked_add(self, rhs: Self) -> Option<Self>;
81    #[must_use]
82    fn checked_sub(self, rhs: Self) -> Option<Self>;
83    #[must_use]
84    fn checked_mul(self, rhs: Self) -> Option<Self>;
85    #[must_use]
86    fn isolate_lowest_one(self) -> Self;
87    #[must_use]
88    fn lowest_one(self) -> Option<u32>;
89    #[must_use]
90    fn trailing_ones(self) -> u32;
91    #[must_use]
92    fn trailing_zeros(self) -> u32;
93    #[must_use]
94    fn unsigned_abs(self) -> Self::Unsigned;
95    #[must_use]
96    fn saturating_sub_0(self, rhs: Self) -> Self::Unsigned;
97}
98
99/// Trait implemented by the primitive unsigned integer types.
100pub trait UnsignedInteger:
101    Integer<Unsigned = Self> + From<u8> + TryFrom<u128, Error: Debug>
102{
103    /// The maximum number of decimal digits which always fit in the type.
104    const SAFE_DIGITS: usize;
105
106    #[must_use]
107    fn cast_signed(self) -> Self::Signed;
108
109    #[must_use]
110    fn wrapping_add_signed(self, rhs: Self::Signed) -> Self;
111
112    #[must_use]
113    fn wrapping_sub(self, rhs: Self) -> Self;
114}
115
116/// Trait implemented by the primitive signed integer types.
117pub trait SignedInteger: Integer<Signed = Self> + Signed {
118    #[must_use]
119    fn cast_unsigned(self) -> Self::Unsigned;
120}
121
122macro_rules! number_impl {
123    (int => $($u:ident: $s:ident ),+) => {
124        $(impl Number for $u {
125            const ZERO: Self = 0;
126            const ONE: Self = 1;
127            const MIN: Self = Self::MIN;
128            const MAX: Self = Self::MAX;
129
130            #[inline]
131            fn abs(self) -> Self {
132                self // no-op for unsigned integers
133            }
134
135            #[inline]
136            fn rem_euclid(self, rhs: Self) -> Self {
137                self.rem_euclid(rhs)
138            }
139
140            #[inline]
141            fn squared_diff(self, rhs: Self) -> Self {
142                let diff = self.abs_diff(rhs);
143                diff * diff
144            }
145        })+
146
147        $(impl Integer for $u {
148            type NonZero = std::num::NonZero<$u>;
149            type Unsigned = $u;
150            type Signed = $s;
151
152            const BITS: u32 = $u::BITS;
153
154            #[inline]
155            fn abs_diff(self, rhs: Self) -> Self::Unsigned {
156                self.abs_diff(rhs)
157            }
158            #[inline]
159            fn checked_add(self, rhs: Self) -> Option<Self> {
160                self.checked_add(rhs)
161            }
162            #[inline]
163            fn checked_sub(self, rhs: Self) -> Option<Self> {
164                self.checked_sub(rhs)
165            }
166            #[inline]
167            fn checked_mul(self, rhs: Self) -> Option<Self> {
168                self.checked_mul(rhs)
169            }
170            #[inline]
171            fn isolate_lowest_one(self) -> Self {
172                self.isolate_lowest_one()
173            }
174            #[inline]
175            fn lowest_one(self) -> Option<u32> {
176                self.lowest_one()
177            }
178            #[inline]
179            fn trailing_ones(self) -> u32 {
180                self.trailing_ones()
181            }
182            #[inline]
183            fn trailing_zeros(self) -> u32 {
184                self.trailing_zeros()
185            }
186            #[inline]
187            fn unsigned_abs(self) -> Self::Unsigned {
188                self // no-op for unsigned integers
189            }
190            #[inline]
191            fn saturating_sub_0(self, rhs: Self) -> Self::Unsigned {
192                self.saturating_sub(rhs)
193            }
194        })+
195
196        $(impl UnsignedInteger for $u {
197            const SAFE_DIGITS: usize = $u::MAX.ilog10() as usize;
198
199            #[inline]
200            fn cast_signed(self) -> Self::Signed {
201                self.cast_signed()
202            }
203
204            #[inline]
205            fn wrapping_add_signed(self, rhs: Self::Signed) -> Self {
206                self.wrapping_add_signed(rhs)
207            }
208
209            #[inline]
210            fn wrapping_sub(self, rhs: Self) -> Self {
211                self.wrapping_sub(rhs)
212            }
213        })+
214
215        $(impl Number for $s {
216            const ZERO: Self = 0;
217            const ONE: Self = 1;
218            const MIN: Self = Self::MIN;
219            const MAX: Self = Self::MAX;
220
221            #[inline]
222            fn abs(self) -> Self {
223                self.abs()
224            }
225
226            #[inline]
227            fn rem_euclid(self, rhs: Self) -> Self {
228                self.rem_euclid(rhs)
229            }
230
231            #[inline]
232            fn squared_diff(self, rhs: Self) -> Self {
233                let diff = self - rhs;
234                diff * diff
235            }
236        })+
237
238        $(impl Signed for $s {
239            const MINUS_ONE: Self = -Self::ONE;
240        })+
241
242        $(impl Integer for $s {
243            type NonZero = std::num::NonZero<$s>;
244            type Unsigned = $u;
245            type Signed = $s;
246
247            const BITS: u32 = $s::BITS;
248
249            #[inline]
250            fn abs_diff(self, rhs: Self) -> Self::Unsigned {
251                self.abs_diff(rhs)
252            }
253            #[inline]
254            fn checked_add(self, rhs: Self) -> Option<Self> {
255                self.checked_add(rhs)
256            }
257            #[inline]
258            fn checked_sub(self, rhs: Self) -> Option<Self> {
259                self.checked_sub(rhs)
260            }
261            #[inline]
262            fn checked_mul(self, rhs: Self) -> Option<Self> {
263                self.checked_mul(rhs)
264            }
265            #[inline]
266            fn isolate_lowest_one(self) -> Self {
267                self.isolate_lowest_one()
268            }
269            #[inline]
270            fn lowest_one(self) -> Option<u32> {
271                self.lowest_one()
272            }
273            #[inline]
274            fn trailing_ones(self) -> u32 {
275                self.trailing_ones()
276            }
277            #[inline]
278            fn trailing_zeros(self) -> u32 {
279                self.trailing_zeros()
280            }
281            #[inline]
282            fn unsigned_abs(self) -> Self::Unsigned {
283                self.unsigned_abs()
284            }
285            #[inline]
286            #[expect(clippy::cast_sign_loss)]
287            fn saturating_sub_0(self, rhs: Self) -> Self::Unsigned {
288                // Equivalent to `self.saturating_sub(rhs).max(0) as $u`, but avoids overflow for
289                // e.g. i32::MAX - i32::MIN
290                let diff = (self as $u).wrapping_sub(rhs as $u);
291                let mask = (0 as $u).wrapping_sub($u::from(self >= rhs));
292                diff & mask
293            }
294        })+
295
296        $(impl SignedInteger for $s {
297            #[inline]
298            fn cast_unsigned(self) -> Self::Unsigned {
299                self.cast_unsigned()
300            }
301        })+
302    };
303    (float => $($t:ident),+) => {$(
304        impl Number for $t {
305            const ZERO: Self = 0.0;
306            const ONE: Self = 1.0;
307            const MIN: Self = Self::NEG_INFINITY;
308            const MAX: Self = Self::INFINITY;
309
310            #[inline]
311            fn abs(self) -> Self {
312                self.abs()
313            }
314
315            #[inline]
316            fn rem_euclid(self, rhs: Self) -> Self {
317                self.rem_euclid(rhs)
318            }
319
320            #[inline]
321            fn squared_diff(self, rhs: Self) -> Self {
322                let diff = self - rhs;
323                diff * diff
324            }
325        }
326
327        impl Signed for $t {
328            const MINUS_ONE: Self = -Self::ONE;
329        }
330    )+};
331}
332number_impl! {int => u8: i8, u16: i16, u32: i32, u64: i64, u128: i128, usize: isize}
333number_impl! {float => f32, f64}
334
335/// Checks if the provided unsigned integer `n` is a prime number.
336///
337/// # Examples
338/// ```
339/// # use utils::number::is_prime;
340/// assert_eq!(is_prime(7901u32), true);
341/// assert_eq!(is_prime(2147483647u32), true);
342/// assert_eq!(is_prime(4294967291u32), true);
343/// assert_eq!(is_prime(6u32), false);
344/// assert_eq!(is_prime(123u32), false);
345/// ```
346#[inline]
347#[must_use]
348pub fn is_prime<T: UnsignedInteger>(n: T) -> bool {
349    if n <= T::ONE {
350        return false;
351    }
352    if n == T::from(2) || n == T::from(3) {
353        return true;
354    }
355    if n % T::from(2) == T::ZERO || n % T::from(3) == T::ZERO {
356        return false;
357    }
358
359    let mut i = T::from(5);
360    while let Some(square) = i.checked_mul(i)
361        && square <= n
362    {
363        if n % i == T::ZERO || n % (i + T::from(2)) == T::ZERO {
364            return false;
365        }
366
367        if let Some(next) = i.checked_add(T::from(6)) {
368            i = next;
369        } else {
370            break;
371        }
372    }
373
374    true
375}
376
377/// Computes the sum of the divisors for unsigned integer `n`.
378///
379/// Returns `None` if the sum overflows.
380///
381/// # Examples
382/// ```
383/// # use utils::number::sum_of_divisors;
384/// assert_eq!(sum_of_divisors(5u32), Some(6));
385/// assert_eq!(sum_of_divisors(32u32), Some(63));
386/// assert_eq!(sum_of_divisors(50u32), Some(93));
387/// assert_eq!(sum_of_divisors(857_656_800u32), None);
388/// assert_eq!(sum_of_divisors(857_656_800u64), Some(4_376_251_152));
389/// ```
390#[inline]
391#[must_use]
392pub fn sum_of_divisors<T: UnsignedInteger>(n: T) -> Option<T> {
393    if n <= T::ONE {
394        return Some(n);
395    }
396
397    let mut sum = T::ZERO;
398    let mut d = T::ONE;
399    while let Some(square) = d.checked_mul(d)
400        && square <= n
401    {
402        if n % d == T::ZERO {
403            sum = sum.checked_add(d)?;
404
405            let q = n / d;
406            if q != d {
407                sum = sum.checked_add(q)?;
408            }
409        }
410
411        d += T::ONE;
412    }
413
414    Some(sum)
415}
416
417/// Computes the greatest common divisor (GCD) using the Euclidean algorithm.
418///
419/// # Examples
420/// ```
421/// # use utils::number::gcd;
422/// assert_eq!(gcd(252, 105), 21);
423/// assert_eq!(gcd(-12, 8), -4);
424/// ```
425#[inline]
426#[must_use]
427pub fn gcd<T: Integer>(mut a: T, mut b: T) -> T {
428    while b != T::ZERO {
429        (a, b) = (b, a % b);
430    }
431    a
432}
433
434/// Computes the extended greatest common divisor.
435///
436/// Returns `(gcd, s, t)` such that `gcd = s * a + t * b`.
437///
438/// Unlike [`gcd`], this function is only defined for signed integers as the `s` and `t`
439/// coefficients may be negative.
440///
441/// # Examples
442/// ```
443/// # use utils::number::egcd;
444/// assert_eq!(egcd(252, 105), (21, -2, 5));
445/// assert_eq!((252 * -2) + (105 * 5), 21);
446/// ```
447#[inline]
448#[must_use]
449pub fn egcd<T: SignedInteger>(mut a: T, mut b: T) -> (T, T, T) {
450    let (mut x0, mut x1, mut y0, mut y1) = (T::ONE, T::ZERO, T::ZERO, T::ONE);
451
452    while b != T::ZERO {
453        let q = a / b;
454        (a, b) = (b, a % b);
455        (x0, x1) = (x1, x0 - q * x1);
456        (y0, y1) = (y1, y0 - q * y1);
457    }
458
459    (a, x0, y0)
460}
461
462/// Computes the lowest common multiple (LCM).
463///
464/// # Examples
465/// ```
466/// # use utils::number::lcm;
467/// assert_eq!(lcm(6, 4), 12);
468/// assert_eq!(lcm(21, 6), 42);
469/// ```
470#[inline]
471#[must_use]
472pub fn lcm<T: Integer>(a: T, b: T) -> T {
473    if a == T::ZERO || b == T::ZERO {
474        return T::ZERO;
475    }
476
477    (a / gcd(a, b)).abs() * b.abs()
478}
479
480/// Computes the modular inverse of `a` modulo `b` if it exists.
481///
482/// # Examples
483/// ```
484/// # use utils::number::mod_inverse;
485/// assert_eq!(mod_inverse(3, 5), Some(2));
486/// assert_eq!((3 * 2) % 5, 1);
487///
488/// assert_eq!(mod_inverse(10, 23), Some(7));
489/// assert_eq!((10 * 7) % 23, 1);
490///
491/// assert_eq!(mod_inverse(2, 8), None);
492/// ```
493#[inline]
494#[must_use]
495pub fn mod_inverse<T: SignedInteger>(a: T, b: T) -> Option<T> {
496    let (gcd, x, _) = egcd(a, b);
497    if gcd == T::ONE {
498        Some(x.rem_euclid(b))
499    } else {
500        None
501    }
502}
503
504/// Solves a system of simultaneous congruences using the Chinese Remainder Theorem.
505///
506/// This function finds the smallest non-negative integer `x` where `x % modulus = residue` for each
507/// provided (residue, modulus) pair.
508///
509/// # Examples
510/// ```
511/// # use utils::number::chinese_remainder;
512/// assert_eq!(chinese_remainder([1, 2, 3], [5, 7, 11]), Some(366));
513/// assert_eq!(366 % 5, 1);
514/// assert_eq!(366 % 7, 2);
515/// assert_eq!(366 % 11, 3);
516/// ```
517#[inline]
518#[must_use]
519pub fn chinese_remainder<T: SignedInteger>(
520    residues: impl IntoIterator<Item = T>,
521    moduli: impl IntoIterator<Item = T, IntoIter: Clone>,
522) -> Option<T> {
523    let moduli = moduli.into_iter();
524    let product = moduli.clone().product();
525
526    let mut sum = T::ZERO;
527    for (residue, modulus) in residues.into_iter().zip(moduli) {
528        let p = product / modulus;
529        sum += residue * mod_inverse(p, modulus)? * p;
530    }
531
532    Some(sum.rem_euclid(product))
533}
534
535/// Calculates `base.pow(exponent) % modulus`.
536///
537/// # Examples
538/// ```
539/// # use utils::number::mod_pow;
540/// assert_eq!(mod_pow::<u64>(2, 10, 1000), 24);
541/// assert_eq!(mod_pow::<u64>(65, 100000, 2147483647), 1085966926);
542/// ```
543#[inline]
544#[must_use]
545pub fn mod_pow<T: UnsignedInteger>(base: T, exponent: T, modulus: T) -> T {
546    let mut result = T::ONE;
547    let mut base = base % modulus;
548    let mut exponent = exponent;
549
550    while exponent > T::ZERO {
551        if exponent % T::from(2) == T::ONE {
552            result = (result * base) % modulus;
553        }
554        exponent >>= 1;
555        base = (base * base) % modulus;
556    }
557
558    result
559}