fixed_bigint/fixeduint/
num_integer_impl.rs

1use super::{FixedUInt, MachineWord};
2
3use crate::personality::Nct;
4use num_traits::{PrimInt, Zero};
5
6// Most code here from num_integer crate, unsigned implementation
7
8impl<T: MachineWord, const N: usize> num_integer::Integer for FixedUInt<T, N, Nct> {
9    fn div_floor(&self, other: &Self) -> Self {
10        *self / *other
11    }
12    fn mod_floor(&self, other: &Self) -> Self {
13        *self % *other
14    }
15    fn gcd(&self, other: &Self) -> Self {
16        // Use Stein's algorithm
17        let mut m = *self;
18        let mut n = *other;
19        let zero = Self::zero();
20        if m == zero || n == zero {
21            return m | n;
22        }
23
24        // find common factors of 2
25        let shift = (m | n).trailing_zeros();
26
27        // divide n and m by 2 until odd
28        m = m >> m.trailing_zeros();
29        n = n >> n.trailing_zeros();
30
31        while m != n {
32            if m > n {
33                m -= n;
34                m = m >> m.trailing_zeros();
35            } else {
36                n -= m;
37                n = n >> n.trailing_zeros();
38            }
39        }
40        m << shift
41    }
42    fn lcm(&self, other: &Self) -> Self {
43        if self.is_zero() && other.is_zero() {
44            return Self::zero();
45        }
46        let gcd = self.gcd(other);
47        *self * (*other / gcd)
48    }
49    fn divides(&self, other: &Self) -> bool {
50        self.is_multiple_of(other)
51    }
52    fn is_multiple_of(&self, other: &Self) -> bool {
53        (*self) % other == Self::zero()
54    }
55    fn is_even(&self) -> bool {
56        // O(1): only check LSB of first word, not full-width AND + compare
57        N == 0 || self.array[0] & T::one() == T::zero()
58    }
59    fn is_odd(&self) -> bool {
60        !self.is_even()
61    }
62    fn div_rem(&self, other: &Self) -> (Self, Self) {
63        self.div_rem(other)
64    }
65}
fixed_bigint/fixeduint/num_integer_impl.rs

fixed_bigint/fixeduint/
num_integer_impl.rs
