ocas_domain/
integer.rs

1//! Integer domain implementation.
2//!
3//! Supports arbitrary-precision integers. The default build uses
4//! [`num_bigint::BigInt`]. When the `gmp` feature is enabled, the
5//! implementation moves to `gmp_backend`.
6
7#[cfg(not(feature = "gmp"))]
8use num_bigint::BigInt;
9#[cfg(not(feature = "gmp"))]
10use num_integer::Integer as _;
11#[cfg(not(feature = "gmp"))]
12use num_traits::{One, Zero};
13#[cfg(not(feature = "gmp"))]
14use std::ops::{Add, Div, Mul, Rem, Sub};
15
16#[cfg(not(feature = "gmp"))]
17use crate::domain::{Domain, EuclideanDomain};
18
19/// The integer domain.
20///
21/// # Example
22///
23/// ```
24/// use ocas_domain::{Domain, Integer, IntegerDomain};
25///
26/// let domain = IntegerDomain;
27/// let a = Integer::from(3);
28/// let b = Integer::from(5);
29/// assert_eq!(domain.add(&a, &b), Integer::from(8));
30/// ```
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub struct IntegerDomain;
33
34#[cfg(not(feature = "gmp"))]
35/// Arbitrary-precision integer backed by `num-bigint`.
36///
37/// # Example
38///
39/// ```
40/// use ocas_domain::Integer;
41///
42/// let a = Integer::from(42);
43/// let b = Integer::new(100);
44/// assert_eq!(a.to_string(), "42");
45/// assert_eq!(b.to_string(), "100");
46/// ```
47#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
48pub struct Integer(BigInt);
49
50#[cfg(not(feature = "gmp"))]
51impl Integer {
52    /// Create an integer from a machine integer.
53    pub fn new<T: Into<BigInt>>(value: T) -> Self {
54        Self(value.into())
55    }
56
57    /// Access the underlying `BigInt`.
58    pub fn inner(&self) -> &BigInt {
59        &self.0
60    }
61
62    /// Convert to a `BigInt` regardless of the backend.
63    pub fn to_bigint(&self) -> BigInt {
64        self.0.clone()
65    }
66
67    /// Try to extract the value as `i64`. Returns `None` if it doesn't fit.
68    pub fn to_i64(&self) -> Option<i64> {
69        use num_traits::ToPrimitive;
70        self.0.to_i64()
71    }
72
73    /// Raise to a `u32` power.
74    pub fn pow_u32(&self, exp: u32) -> Self {
75        use num_traits::Pow;
76        Integer(self.0.clone().pow(exp))
77    }
78}
79
80#[cfg(not(feature = "gmp"))]
81impl std::fmt::Display for Integer {
82    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
83        write!(f, "{}", self.0)
84    }
85}
86
87#[cfg(not(feature = "gmp"))]
88impl Domain for IntegerDomain {
89    type Element = Integer;
90
91    fn zero(&self) -> Self::Element {
92        Integer(BigInt::zero())
93    }
94
95    fn one(&self) -> Self::Element {
96        Integer(BigInt::one())
97    }
98
99    fn add(&self, a: &Self::Element, b: &Self::Element) -> Self::Element {
100        Integer(a.0.clone() + b.0.clone())
101    }
102
103    fn sub(&self, a: &Self::Element, b: &Self::Element) -> Self::Element {
104        Integer(a.0.clone() - b.0.clone())
105    }
106
107    fn neg(&self, a: &Self::Element) -> Self::Element {
108        Integer(-a.0.clone())
109    }
110
111    fn mul(&self, a: &Self::Element, b: &Self::Element) -> Self::Element {
112        Integer(a.0.clone() * b.0.clone())
113    }
114
115    fn div(&self, a: &Self::Element, b: &Self::Element) -> Option<Self::Element> {
116        if b.0.is_zero() {
117            return None;
118        }
119        let (q, r) = a.0.clone().div_rem(&b.0);
120        if r.is_zero() { Some(Integer(q)) } else { None }
121    }
122
123    fn inv(&self, a: &Self::Element) -> Option<Self::Element> {
124        if a.0.is_one() {
125            Some(self.one())
126        } else if a.0 == -BigInt::one() {
127            Some(Integer(-BigInt::one()))
128        } else {
129            None
130        }
131    }
132}
133
134#[cfg(not(feature = "gmp"))]
135impl EuclideanDomain for IntegerDomain {
136    fn div_rem(
137        &self,
138        a: &Self::Element,
139        b: &Self::Element,
140    ) -> Option<(Self::Element, Self::Element)> {
141        if b.0.is_zero() {
142            return None;
143        }
144        let (q, r) = a.0.clone().div_rem(&b.0);
145        Some((Integer(q), Integer(r)))
146    }
147}
148
149#[cfg(not(feature = "gmp"))]
150impl From<i64> for Integer {
151    fn from(value: i64) -> Self {
152        Self::new(value)
153    }
154}
155
156#[cfg(not(feature = "gmp"))]
157impl From<BigInt> for Integer {
158    fn from(value: BigInt) -> Self {
159        Self(value)
160    }
161}
162
163// ---------------------------------------------------------------------------
164// Arithmetic operators — forward to the inner BigInt.
165// These allow `number_theory.rs` and factorization code to use `Integer`
166// directly instead of reaching through `.inner()`.
167// ---------------------------------------------------------------------------
168#[cfg(not(feature = "gmp"))]
169macro_rules! impl_int_op_owned {
170    ($trait:ident, $method:ident, $op:tt) => {
171        impl $trait for Integer {
172            type Output = Integer;
173            fn $method(self, rhs: Integer) -> Integer {
174                Integer(self.0 $op rhs.0)
175            }
176        }
177        impl $trait<&Integer> for Integer {
178            type Output = Integer;
179            fn $method(self, rhs: &Integer) -> Integer {
180                Integer(self.0 $op &rhs.0)
181            }
182        }
183        impl $trait<Integer> for &Integer {
184            type Output = Integer;
185            fn $method(self, rhs: Integer) -> Integer {
186                Integer(&self.0 $op rhs.0)
187            }
188        }
189        impl $trait<&Integer> for &Integer {
190            type Output = Integer;
191            fn $method(self, rhs: &Integer) -> Integer {
192                Integer(&self.0 $op &rhs.0)
193            }
194        }
195    };
196}
197
198#[cfg(not(feature = "gmp"))]
199impl_int_op_owned!(Add, add, +);
200#[cfg(not(feature = "gmp"))]
201impl_int_op_owned!(Sub, sub, -);
202#[cfg(not(feature = "gmp"))]
203impl_int_op_owned!(Mul, mul, *);
204#[cfg(not(feature = "gmp"))]
205impl_int_op_owned!(Div, div, /);
206#[cfg(not(feature = "gmp"))]
207impl_int_op_owned!(Rem, rem, %);
208
209#[cfg(not(feature = "gmp"))]
210impl std::ops::Neg for Integer {
211    type Output = Integer;
212    fn neg(self) -> Integer {
213        Integer(-self.0)
214    }
215}
216#[cfg(not(feature = "gmp"))]
217impl std::ops::Neg for &Integer {
218    type Output = Integer;
219    fn neg(self) -> Integer {
220        Integer(-self.0.clone())
221    }
222}
223
224#[cfg(not(feature = "gmp"))]
225impl std::ops::ShrAssign<u32> for Integer {
226    fn shr_assign(&mut self, shift: u32) {
227        self.0 >>= shift;
228    }
229}
230#[cfg(not(feature = "gmp"))]
231impl std::ops::Shr<u32> for Integer {
232    type Output = Integer;
233    fn shr(self, shift: u32) -> Integer {
234        Integer(self.0 >> shift)
235    }
236}
237#[cfg(not(feature = "gmp"))]
238impl std::ops::Shr<u32> for &Integer {
239    type Output = Integer;
240    fn shr(self, shift: u32) -> Integer {
241        Integer(&self.0 >> shift)
242    }
243}
244
245#[cfg(not(feature = "gmp"))]
246impl std::ops::AddAssign<&Integer> for Integer {
247    fn add_assign(&mut self, rhs: &Integer) {
248        self.0 += &rhs.0;
249    }
250}
251#[cfg(not(feature = "gmp"))]
252impl std::ops::SubAssign<&Integer> for Integer {
253    fn sub_assign(&mut self, rhs: &Integer) {
254        self.0 -= &rhs.0;
255    }
256}
257#[cfg(not(feature = "gmp"))]
258impl std::ops::MulAssign<&Integer> for Integer {
259    fn mul_assign(&mut self, rhs: &Integer) {
260        self.0 *= &rhs.0;
261    }
262}
263#[cfg(not(feature = "gmp"))]
264impl std::ops::DivAssign<&Integer> for Integer {
265    fn div_assign(&mut self, rhs: &Integer) {
266        self.0 /= &rhs.0;
267    }
268}
269
270// ---------------------------------------------------------------------------
271// Number-theory helper methods on Integer.
272// These replace the old `BigInt`-based APIs and enable `number_theory.rs`
273// to work with `Integer` directly.
274// ---------------------------------------------------------------------------
275
276#[cfg(not(feature = "gmp"))]
277impl Integer {
278    /// Modular exponentiation: `self^exp mod modulus`.
279    pub fn modpow(&self, exp: &Integer, modulus: &Integer) -> Integer {
280        Integer(self.0.modpow(&exp.0, &modulus.0))
281    }
282
283    /// Floor modulo: result `r` satisfies `0 ≤ r < |modulus|`.
284    pub fn mod_floor(&self, modulus: &Integer) -> Integer {
285        use num_integer::Integer as _;
286        Integer(self.0.mod_floor(&modulus.0))
287    }
288
289    /// Division with remainder: `(quotient, remainder)`.
290    pub fn div_rem(&self, other: &Integer) -> (Integer, Integer) {
291        use num_integer::Integer as _;
292        let (q, r) = self.0.div_rem(&other.0);
293        (Integer(q), Integer(r))
294    }
295
296    /// Returns `true` if the value is even.
297    pub fn is_even(&self) -> bool {
298        use num_integer::Integer as _;
299        self.0.is_even()
300    }
301
302    /// Returns `true` if the value is negative.
303    pub fn is_negative(&self) -> bool {
304        use num_traits::Signed;
305        self.0.is_negative()
306    }
307
308    /// Returns `true` if the value is zero.
309    pub fn is_zero(&self) -> bool {
310        use num_traits::Zero;
311        self.0.is_zero()
312    }
313
314    /// Returns `true` if the value is one.
315    pub fn is_one(&self) -> bool {
316        use num_traits::One;
317        self.0.is_one()
318    }
319
320    /// Absolute value.
321    pub fn abs(&self) -> Integer {
322        use num_traits::Signed;
323        Integer(self.0.abs())
324    }
325
326    /// Integer square root (floor).
327    pub fn sqrt(&self) -> Integer {
328        Integer(self.0.sqrt())
329    }
330}
331
332#[cfg(not(feature = "gmp"))]
333#[cfg(test)]
334mod tests {
335    use super::*;
336
337    #[test]
338    fn integer_addition() {
339        let domain = IntegerDomain;
340        let a = Integer::from(3);
341        let b = Integer::from(5);
342        assert_eq!(domain.add(&a, &b), Integer::from(8));
343    }
344
345    #[test]
346    fn integer_div_exact() {
347        let domain = IntegerDomain;
348        let a = Integer::from(10);
349        let b = Integer::from(3);
350        assert!(domain.div(&a, &b).is_none());
351        let c = Integer::from(2);
352        assert_eq!(domain.div(&a, &c), Some(Integer::from(5)));
353    }
354
355    #[test]
356    fn integer_div_rem() {
357        let domain = IntegerDomain;
358        let a = Integer::from(17);
359        let b = Integer::from(5);
360        let (q, r) = domain.div_rem(&a, &b).unwrap();
361        assert_eq!(q, Integer::from(3));
362        assert_eq!(r, Integer::from(2));
363    }
364}
365
366#[cfg(not(feature = "gmp"))]
367#[cfg(test)]
368mod proptests {
369    use super::*;
370    use proptest::prelude::*;
371
372    fn any_integer() -> impl Strategy<Value = Integer> {
373        any::<i64>().prop_map(Integer::from)
374    }
375
376    proptest! {
377        #[test]
378        fn addition_is_commutative(a in any_integer(), b in any_integer()) {
379            let domain = IntegerDomain;
380            assert_eq!(domain.add(&a, &b), domain.add(&b, &a));
381        }
382
383        #[test]
384        fn multiplication_is_commutative(a in any_integer(), b in any_integer()) {
385            let domain = IntegerDomain;
386            assert_eq!(domain.mul(&a, &b), domain.mul(&b, &a));
387        }
388
389        #[test]
390        fn zero_is_additive_identity(a in any_integer()) {
391            let domain = IntegerDomain;
392            let zero = domain.zero();
393            assert_eq!(domain.add(&a, &zero), a);
394        }
395
396        #[test]
397        fn subtraction_cancels_addition(a in any_integer(), b in any_integer()) {
398            let domain = IntegerDomain;
399            let sum = domain.add(&a, &b);
400            assert_eq!(domain.sub(&sum, &b), a);
401        }
402    }
403}
ocas_domain/integer.rs

ocas_domain/
integer.rs
