29697842029

Committed 19 Jul 2026 05:57PM UTC coverage: 97.785% (-0.03%) from 97.818%

Build # 29697842029

Build Type

Pull #157

github

Committed by

kaidokert

Commit Message

Implement num_integer::Integer for HeaplessBigInt

The last Tier-1 parity item — gcd/lcm/div_floor/mod_floor/divides/
is_multiple_of/is_even/is_odd/div_rem, Nct-only, mirroring FixedUInt.

- div_floor/mod_floor/div_rem: the unsigned div/rem (floor == truncating).
- gcd: Stein's binary algorithm. Heapless `>>` narrows `len`, so the running
  values shrink — value-correct (comparisons are value-based), but the result
  is pinned to the operand width max(len): widen before the final `<< shift`
  so no bit is lost and the width matches FixedUInt<k>. Dedicated
  heapless-internal test for the sub-capacity width case.
- lcm = a / gcd(a, b) * b; is_even/is_odd: O(1) LSB check like FixedUInt.

Tests: generic gcd/lcm/div/parity for both carriers (carrier_num_traits) plus
heapless-internal gcd width-preservation and multi-limb gcd/lcm.

Tier-1 parity is now complete: HeaplessBigInt<_, Nct> is a drop-in
num_traits::PrimInt + num_integer::Integer.

Pull Request Pull Request #157: Implement num_integer::Integer for HeaplessBigInt

Coverage Stats

60 of 63 new or added lines in 1 file covered. (95.24%)

4812 of 4921 relevant lines covered (97.79%)

5932.01 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.24

/src/heapless/num_integer_impl.rs

//! `num_integer::Integer` for `HeaplessBigInt<T, CAP, Nct>`.
//!
//! Nct-only, mirroring `FixedUInt`. `div_floor`/`mod_floor`/`div_rem` are the
//! unsigned div/rem (floor == truncating); `gcd` is Stein's binary algorithm;
//! `lcm` = `a / gcd(a, b) * b`. `is_even`/`is_odd` delegate to the O(1)
//! `Parity` LSB check. Everything resolves at the operand width `max(len)`.

use super::HeaplessBigInt;
use crate::MachineWord;
use const_num_traits::{CarryingMul, Nct, One, PrimBits, Zero};

impl<T, const CAP: usize> num_integer::Integer for HeaplessBigInt<T, CAP, Nct>
where
    T: MachineWord + CarryingMul<Unsigned = T, Output = T>,
{
    fn div_floor(&self, other: &Self) -> Self {
        *self / *other
    }

    fn mod_floor(&self, other: &Self) -> Self {
        *self % *other
    }

    fn gcd(&self, other: &Self) -> Self {
        // Stein's (binary) GCD. Heapless `>>` narrows `len`, so the running
        // values shrink as they're stripped of factors of two — that's
        // value-correct (comparisons are value-based). The result is pinned to
        // the operand width `max(len)`: widen before the final `<< shift` so no
        // bit is lost and the width matches FixedUInt<k>.
        let width = core::cmp::max(self.len(), other.len());
        let mut m = *self;
        let mut n = *other;
        let zero = <Self as Zero>::zero();
        if m == zero || n == zero {
            return m | n; // already at max(len) via BitOr
        }

        // Common factors of two, then strip each value to odd.
        let shift = PrimBits::trailing_zeros(m | n);
        m = m >> (PrimBits::trailing_zeros(m) as usize);
        n = n >> (PrimBits::trailing_zeros(n) as usize);

        while m != n {
            if m > n {
                m -= n;
                m = m >> (PrimBits::trailing_zeros(m) as usize);
            } else {
                n -= m;
                n = n >> (PrimBits::trailing_zeros(n) as usize);
            }
        }
        m.widened(width) << (shift as usize)
    }

    fn lcm(&self, other: &Self) -> Self {
        if <Self as Zero>::is_zero(self) && <Self as Zero>::is_zero(other) {
            return <Self as Zero>::zero();
        }
        let gcd = self.gcd(other);
        *self * (*other / gcd)
    }

    fn divides(&self, other: &Self) -> bool {
        self.is_multiple_of(other)
    }

    fn is_multiple_of(&self, other: &Self) -> bool {
        *self % *other == <Self as Zero>::zero()
    }

    fn is_even(&self) -> bool {
        // O(1) LSB check, like FixedUInt. `len == 0` (zero) is even; otherwise
        // `len > 0` guarantees `limbs[0]` exists.
        self.len == 0 || self.limbs[0] & <T as One>::one() == <T as Zero>::zero()
    }

    fn is_odd(&self) -> bool {
        !self.is_even()
    }

    fn div_rem(&self, other: &Self) -> (Self, Self) {
        // Inherent div_rem (single pass); resolves over `&self`, so it's the
        // inherent method, not this trait one.
        self.div_rem(other)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use num_integer::Integer;

    type H = HeaplessBigInt<u32, 8, Nct>; // 256-bit CAP

    #[test]
    fn gcd_preserves_operand_width() {
        // Two len-2 (64-bit) values in a CAP-8 carrier. Stein's `>>` narrows
        // the running values, but the result is pinned to the operand width
        // (len 2), not the narrow gcd magnitude — matching FixedUInt<u32, 2>.
        let a = H::from_le_bytes(&12u64.to_le_bytes()); // len 2
        let b = H::from_le_bytes(&18u64.to_le_bytes()); // len 2
        let g = a.gcd(&b);
        assert_eq!(g.len(), 2, "gcd resolves at the operand width");
        assert_eq!(g.limbs[0], 6);
        assert_eq!(g.limbs[1], 0);
    }

    #[test]
    fn gcd_lcm_multi_limb() {
        // 64-bit powers of two spanning 2 u32 limbs.
        let a = H::from_le_bytes(&0x1_0000_0000u64.to_le_bytes()); // 2^32
        let b = H::from_le_bytes(&0x1_8000_0000u64.to_le_bytes()); // 3·2^31
        assert_eq!(a.gcd(&b), H::from_le_bytes(&0x8000_0000u64.to_le_bytes())); // 2^31
        // lcm(2^32, 3·2^31) = 3·2^32
        assert_eq!(a.lcm(&b), H::from_le_bytes(&0x3_0000_0000u64.to_le_bytes()));
    }
}

1	//! `num_integer::Integer` for `HeaplessBigInt<T, CAP, Nct>`.
2	//!
3	//! Nct-only, mirroring `FixedUInt`. `div_floor`/`mod_floor`/`div_rem` are the
4	//! unsigned div/rem (floor == truncating); `gcd` is Stein's binary algorithm;
5	//! `lcm` = `a / gcd(a, b) * b`. `is_even`/`is_odd` delegate to the O(1)
6	//! `Parity` LSB check. Everything resolves at the operand width `max(len)`.
7
8	use super::HeaplessBigInt;
9	use crate::MachineWord;
10	use const_num_traits::{CarryingMul, Nct, One, PrimBits, Zero};
11
12	impl<T, const CAP: usize> num_integer::Integer for HeaplessBigInt<T, CAP, Nct>
13	where
14	T: MachineWord + CarryingMul<Unsigned = T, Output = T>,
15	{
16	fn div_floor(&self, other: &Self) -> Self {	3✔
17	self / other	3✔
18	}	3✔
19
20	fn mod_floor(&self, other: &Self) -> Self {	3✔
21	self % other	3✔
22	}	3✔
23
24	fn gcd(&self, other: &Self) -> Self {	15✔
25	// Stein's (binary) GCD. Heapless `>>` narrows `len`, so the running
26	// values shrink as they're stripped of factors of two — that's
27	// value-correct (comparisons are value-based). The result is pinned to
28	// the operand width `max(len)`: widen before the final `<< shift` so no
29	// bit is lost and the width matches FixedUInt<k>.
30	let width = core::cmp::max(self.len(), other.len());	15✔
31	let mut m = *self;	15✔
32	let mut n = *other;	15✔
33	let zero = <Self as Zero>::zero();	15✔
34	if m == zero \|\| n == zero {	15✔
35	return m \| n; // already at max(len) via BitOr	3✔
36	}	12✔
37
38	// Common factors of two, then strip each value to odd.
39	let shift = PrimBits::trailing_zeros(m \| n);	12✔
40	m = m >> (PrimBits::trailing_zeros(m) as usize);	12✔
41	n = n >> (PrimBits::trailing_zeros(n) as usize);	12✔
42
43	while m != n {	30✔
44	if m > n {	18✔
45	m -= n;	6✔
46	m = m >> (PrimBits::trailing_zeros(m) as usize);	6✔
47	} else {	12✔
48	n -= m;	12✔
49	n = n >> (PrimBits::trailing_zeros(n) as usize);	12✔
50	}	12✔
51	}
52	m.widened(width) << (shift as usize)	12✔
53	}	15✔
54
55	fn lcm(&self, other: &Self) -> Self {	7✔
56	if <Self as Zero>::is_zero(self) && <Self as Zero>::is_zero(other) {	7✔
57	return <Self as Zero>::zero();	3✔
58	}	4✔
59	let gcd = self.gcd(other);	4✔
60	self (*other / gcd)	4✔
61	}	7✔
62
NEW 63	fn divides(&self, other: &Self) -> bool {	×
NEW 64	self.is_multiple_of(other)	×
NEW 65	}	×
66
67	fn is_multiple_of(&self, other: &Self) -> bool {	6✔
68	self % other == <Self as Zero>::zero()	6✔
69	}	6✔
70
71	fn is_even(&self) -> bool {	9✔
72	// O(1) LSB check, like FixedUInt. `len == 0` (zero) is even; otherwise
73	// `len > 0` guarantees `limbs[0]` exists.
74	self.len == 0 \|\| self.limbs[0] & <T as One>::one() == <T as Zero>::zero()	9✔
75	}	9✔
76
77	fn is_odd(&self) -> bool {	3✔
78	!self.is_even()	3✔
79	}	3✔
80
81	fn div_rem(&self, other: &Self) -> (Self, Self) {	3✔
82	// Inherent div_rem (single pass); resolves over `&self`, so it's the
83	// inherent method, not this trait one.
84	self.div_rem(other)	3✔
85	}	3✔
86	}
87
88	#[cfg(test)]
89	mod tests {
90	use super::*;
91	use num_integer::Integer;
92
93	type H = HeaplessBigInt<u32, 8, Nct>; // 256-bit CAP
94
95	#[test]
96	fn gcd_preserves_operand_width() {	1✔
97	// Two len-2 (64-bit) values in a CAP-8 carrier. Stein's `>>` narrows
98	// the running values, but the result is pinned to the operand width
99	// (len 2), not the narrow gcd magnitude — matching FixedUInt<u32, 2>.
100	let a = H::from_le_bytes(&12u64.to_le_bytes()); // len 2	1✔
101	let b = H::from_le_bytes(&18u64.to_le_bytes()); // len 2	1✔
102	let g = a.gcd(&b);	1✔
103	assert_eq!(g.len(), 2, "gcd resolves at the operand width");	1✔
104	assert_eq!(g.limbs[0], 6);	1✔
105	assert_eq!(g.limbs[1], 0);	1✔
106	}	1✔
107
108	#[test]
109	fn gcd_lcm_multi_limb() {	1✔
110	// 64-bit powers of two spanning 2 u32 limbs.
111	let a = H::from_le_bytes(&0x1_0000_0000u64.to_le_bytes()); // 2^32	1✔
112	let b = H::from_le_bytes(&0x1_8000_0000u64.to_le_bytes()); // 3·2^31	1✔
113	assert_eq!(a.gcd(&b), H::from_le_bytes(&0x8000_0000u64.to_le_bytes())); // 2^31	1✔
114	// lcm(2^32, 3·2^31) = 3·2^32
115	assert_eq!(a.lcm(&b), H::from_le_bytes(&0x3_0000_0000u64.to_le_bytes()));	1✔
116	}	1✔
117	}

kaidokert / fixed-bigint-rs / 29697842029

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous