oxinum_int/native/
ops_int.rs

1//! Operator implementations for [`BigInt`]:
2//! `Add`/`Sub`/`Mul`/`Div`/`Rem`/`Neg` (+`*Assign`) for owned and borrowed
3//! combinations. All operations preserve the canonical-zero invariant.
4//!
5//! # Sign of remainder
6//!
7//! Division truncates toward zero (matching Rust's primitive `/`); the
8//! remainder takes the **sign of the dividend** (matching Rust's primitive
9//! `%` and `dashu_int::IBig`):
10//!
11//! ```text
12//! a == (a / b) * b + (a % b)         (a != 0, b != 0)
13//! sign(a % b) == sign(a)   when a % b != 0
14//! ```
15
16use super::int::BigInt;
17use super::uint::BigUint;
18use core::ops::{
19    Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Rem, RemAssign, Sub, SubAssign,
20};
21use oxinum_core::Sign;
22
23// ---------------------------------------------------------------------------
24// Internal pure-data helpers (operate on (Sign, &BigUint) tuples)
25// ---------------------------------------------------------------------------
26
27/// Negate a `Sign`.
28#[inline]
29fn neg_sign(s: Sign) -> Sign {
30    match s {
31        Sign::Positive => Sign::Negative,
32        Sign::Negative => Sign::Positive,
33    }
34}
35
36/// Multiply two signs (XOR: positive iff both equal).
37#[inline]
38fn xor_sign(a: Sign, b: Sign) -> Sign {
39    if a == b {
40        Sign::Positive
41    } else {
42        Sign::Negative
43    }
44}
45
46/// Core addition logic: `(sa * |a|) + (sb * |b|)`.
47fn add_signed(sa: Sign, a: &BigUint, sb: Sign, b: &BigUint) -> BigInt {
48    if sa == sb {
49        // Same sign: add magnitudes.
50        BigInt::from_parts(sa, a + b)
51    } else if a >= b {
52        // Different signs, |a| >= |b|: sign of a wins, mag = |a| - |b|.
53        let diff = a
54            .checked_sub(b)
55            .expect("invariant: a >= b ensures non-negative subtraction");
56        BigInt::from_parts(sa, diff)
57    } else {
58        // Different signs, |a| < |b|: sign of b wins, mag = |b| - |a|.
59        let diff = b
60            .checked_sub(a)
61            .expect("invariant: b > a ensures non-negative subtraction");
62        BigInt::from_parts(sb, diff)
63    }
64}
65
66/// Multiplication core. Sign by XOR.
67fn mul_signed(sa: Sign, a: &BigUint, sb: Sign, b: &BigUint) -> BigInt {
68    BigInt::from_parts(xor_sign(sa, sb), a * b)
69}
70
71/// Division core (truncation toward zero). Returns `(quotient, remainder)`.
72/// Panics if `b` is zero.
73fn divrem_signed(sa: Sign, a: &BigUint, sb: Sign, b: &BigUint) -> (BigInt, BigInt) {
74    if b.is_zero() {
75        panic!("BigInt: division by zero");
76    }
77    let (q_mag, r_mag) = super::div::divrem(a, b);
78    let q_sign = xor_sign(sa, sb);
79    // Remainder sign = sign of dividend when remainder is non-zero.
80    let r_sign = sa;
81    (
82        BigInt::from_parts(q_sign, q_mag),
83        BigInt::from_parts(r_sign, r_mag),
84    )
85}
86
87// ---------------------------------------------------------------------------
88// Neg
89// ---------------------------------------------------------------------------
90
91impl Neg for BigInt {
92    type Output = BigInt;
93    #[inline]
94    fn neg(self) -> BigInt {
95        let (sign, mag) = self.into_parts();
96        BigInt::from_parts(neg_sign(sign), mag)
97    }
98}
99
100impl Neg for &BigInt {
101    type Output = BigInt;
102    #[inline]
103    fn neg(self) -> BigInt {
104        BigInt::from_parts(neg_sign(self.sign()), self.magnitude().clone())
105    }
106}
107
108// ---------------------------------------------------------------------------
109// Add
110// ---------------------------------------------------------------------------
111
112impl Add<&BigInt> for &BigInt {
113    type Output = BigInt;
114    #[inline]
115    fn add(self, rhs: &BigInt) -> BigInt {
116        add_signed(self.sign(), self.magnitude(), rhs.sign(), rhs.magnitude())
117    }
118}
119
120impl Add<BigInt> for BigInt {
121    type Output = BigInt;
122    #[inline]
123    fn add(self, rhs: BigInt) -> BigInt {
124        (&self).add(&rhs)
125    }
126}
127
128impl Add<&BigInt> for BigInt {
129    type Output = BigInt;
130    #[inline]
131    fn add(self, rhs: &BigInt) -> BigInt {
132        (&self).add(rhs)
133    }
134}
135
136impl Add<BigInt> for &BigInt {
137    type Output = BigInt;
138    #[inline]
139    fn add(self, rhs: BigInt) -> BigInt {
140        self.add(&rhs)
141    }
142}
143
144impl AddAssign<&BigInt> for BigInt {
145    #[inline]
146    fn add_assign(&mut self, rhs: &BigInt) {
147        *self = (&*self).add(rhs);
148    }
149}
150
151impl AddAssign<BigInt> for BigInt {
152    #[inline]
153    fn add_assign(&mut self, rhs: BigInt) {
154        *self = (&*self).add(&rhs);
155    }
156}
157
158// ---------------------------------------------------------------------------
159// Sub
160// ---------------------------------------------------------------------------
161
162impl Sub<&BigInt> for &BigInt {
163    type Output = BigInt;
164    #[inline]
165    fn sub(self, rhs: &BigInt) -> BigInt {
166        // a - b = a + (-b)
167        add_signed(
168            self.sign(),
169            self.magnitude(),
170            neg_sign(rhs.sign()),
171            rhs.magnitude(),
172        )
173    }
174}
175
176impl Sub<BigInt> for BigInt {
177    type Output = BigInt;
178    #[inline]
179    fn sub(self, rhs: BigInt) -> BigInt {
180        (&self).sub(&rhs)
181    }
182}
183
184impl Sub<&BigInt> for BigInt {
185    type Output = BigInt;
186    #[inline]
187    fn sub(self, rhs: &BigInt) -> BigInt {
188        (&self).sub(rhs)
189    }
190}
191
192impl Sub<BigInt> for &BigInt {
193    type Output = BigInt;
194    #[inline]
195    fn sub(self, rhs: BigInt) -> BigInt {
196        self.sub(&rhs)
197    }
198}
199
200impl SubAssign<&BigInt> for BigInt {
201    #[inline]
202    fn sub_assign(&mut self, rhs: &BigInt) {
203        *self = (&*self).sub(rhs);
204    }
205}
206
207impl SubAssign<BigInt> for BigInt {
208    #[inline]
209    fn sub_assign(&mut self, rhs: BigInt) {
210        *self = (&*self).sub(&rhs);
211    }
212}
213
214// ---------------------------------------------------------------------------
215// Mul
216// ---------------------------------------------------------------------------
217
218impl Mul<&BigInt> for &BigInt {
219    type Output = BigInt;
220    #[inline]
221    fn mul(self, rhs: &BigInt) -> BigInt {
222        mul_signed(self.sign(), self.magnitude(), rhs.sign(), rhs.magnitude())
223    }
224}
225
226impl Mul<BigInt> for BigInt {
227    type Output = BigInt;
228    #[inline]
229    fn mul(self, rhs: BigInt) -> BigInt {
230        (&self).mul(&rhs)
231    }
232}
233
234impl Mul<&BigInt> for BigInt {
235    type Output = BigInt;
236    #[inline]
237    fn mul(self, rhs: &BigInt) -> BigInt {
238        (&self).mul(rhs)
239    }
240}
241
242impl Mul<BigInt> for &BigInt {
243    type Output = BigInt;
244    #[inline]
245    fn mul(self, rhs: BigInt) -> BigInt {
246        self.mul(&rhs)
247    }
248}
249
250impl MulAssign<&BigInt> for BigInt {
251    #[inline]
252    fn mul_assign(&mut self, rhs: &BigInt) {
253        *self = (&*self).mul(rhs);
254    }
255}
256
257impl MulAssign<BigInt> for BigInt {
258    #[inline]
259    fn mul_assign(&mut self, rhs: BigInt) {
260        *self = (&*self).mul(&rhs);
261    }
262}
263
264// ---------------------------------------------------------------------------
265// Div (truncate toward zero, panic on zero divisor)
266// ---------------------------------------------------------------------------
267
268impl Div<&BigInt> for &BigInt {
269    type Output = BigInt;
270    #[inline]
271    fn div(self, rhs: &BigInt) -> BigInt {
272        divrem_signed(self.sign(), self.magnitude(), rhs.sign(), rhs.magnitude()).0
273    }
274}
275
276impl Div<BigInt> for BigInt {
277    type Output = BigInt;
278    #[inline]
279    fn div(self, rhs: BigInt) -> BigInt {
280        (&self).div(&rhs)
281    }
282}
283
284impl Div<&BigInt> for BigInt {
285    type Output = BigInt;
286    #[inline]
287    fn div(self, rhs: &BigInt) -> BigInt {
288        (&self).div(rhs)
289    }
290}
291
292impl Div<BigInt> for &BigInt {
293    type Output = BigInt;
294    #[inline]
295    fn div(self, rhs: BigInt) -> BigInt {
296        self.div(&rhs)
297    }
298}
299
300impl DivAssign<&BigInt> for BigInt {
301    #[inline]
302    fn div_assign(&mut self, rhs: &BigInt) {
303        *self = (&*self).div(rhs);
304    }
305}
306
307impl DivAssign<BigInt> for BigInt {
308    #[inline]
309    fn div_assign(&mut self, rhs: BigInt) {
310        *self = (&*self).div(&rhs);
311    }
312}
313
314// ---------------------------------------------------------------------------
315// Rem
316// ---------------------------------------------------------------------------
317
318impl Rem<&BigInt> for &BigInt {
319    type Output = BigInt;
320    #[inline]
321    fn rem(self, rhs: &BigInt) -> BigInt {
322        divrem_signed(self.sign(), self.magnitude(), rhs.sign(), rhs.magnitude()).1
323    }
324}
325
326impl Rem<BigInt> for BigInt {
327    type Output = BigInt;
328    #[inline]
329    fn rem(self, rhs: BigInt) -> BigInt {
330        (&self).rem(&rhs)
331    }
332}
333
334impl Rem<&BigInt> for BigInt {
335    type Output = BigInt;
336    #[inline]
337    fn rem(self, rhs: &BigInt) -> BigInt {
338        (&self).rem(rhs)
339    }
340}
341
342impl Rem<BigInt> for &BigInt {
343    type Output = BigInt;
344    #[inline]
345    fn rem(self, rhs: BigInt) -> BigInt {
346        self.rem(&rhs)
347    }
348}
349
350impl RemAssign<&BigInt> for BigInt {
351    #[inline]
352    fn rem_assign(&mut self, rhs: &BigInt) {
353        *self = (&*self).rem(rhs);
354    }
355}
356
357impl RemAssign<BigInt> for BigInt {
358    #[inline]
359    fn rem_assign(&mut self, rhs: BigInt) {
360        *self = (&*self).rem(&rhs);
361    }
362}
363
364// ---------------------------------------------------------------------------
365// divrem free function (analogous to BigUint's)
366// ---------------------------------------------------------------------------
367
368/// Divide-with-remainder for signed `BigInt`. Returns `(quotient, remainder)`
369/// where the quotient truncates toward zero and the remainder takes the sign
370/// of the dividend.
371///
372/// # Panics
373///
374/// Panics if `b` is zero.
375///
376/// # Examples
377///
378/// ```
379/// use oxinum_int::native::{divrem_int, BigInt};
380/// let (q, r) = divrem_int(&BigInt::from(-17i64), &BigInt::from(5i64));
381/// assert_eq!(q, BigInt::from(-3i64));
382/// assert_eq!(r, BigInt::from(-2i64));
383/// ```
384pub fn divrem_int(a: &BigInt, b: &BigInt) -> (BigInt, BigInt) {
385    divrem_signed(a.sign(), a.magnitude(), b.sign(), b.magnitude())
386}
387
388#[cfg(test)]
389mod tests {
390    use super::*;
391
392    #[test]
393    fn neg_zero_is_canonical() {
394        let z = BigInt::zero();
395        let nz = -z.clone();
396        assert_eq!(nz, z);
397        assert_eq!(nz.sign(), Sign::Positive);
398    }
399
400    #[test]
401    fn add_opposite_sign_to_zero() {
402        let a = BigInt::from(42i64);
403        let na = -a.clone();
404        let sum = &a + &na;
405        assert!(sum.is_zero());
406        assert_eq!(sum.sign(), Sign::Positive);
407    }
408
409    #[test]
410    fn sub_basic() {
411        let a = BigInt::from(10i64);
412        let b = BigInt::from(15i64);
413        assert_eq!(&a - &b, BigInt::from(-5i64));
414        assert_eq!(&b - &a, BigInt::from(5i64));
415    }
416
417    #[test]
418    fn mul_sign_table() {
419        let p = BigInt::from(6i64);
420        let n = BigInt::from(-6i64);
421        assert_eq!(&p * &p, BigInt::from(36i64));
422        assert_eq!(&p * &n, BigInt::from(-36i64));
423        assert_eq!(&n * &p, BigInt::from(-36i64));
424        assert_eq!(&n * &n, BigInt::from(36i64));
425    }
426
427    #[test]
428    fn div_truncates_toward_zero() {
429        let cases: &[(i64, i64, i64, i64)] = &[
430            (17, 5, 3, 2),    // 17 = 3*5 + 2
431            (-17, 5, -3, -2), // -17 = -3*5 + (-2)
432            (17, -5, -3, 2),  // 17 = -3*(-5) + 2
433            (-17, -5, 3, -2), // -17 = 3*(-5) + (-2)
434        ];
435        for &(a, b, expected_q, expected_r) in cases {
436            let q = &BigInt::from(a) / &BigInt::from(b);
437            let r = &BigInt::from(a) % &BigInt::from(b);
438            assert_eq!(q, BigInt::from(expected_q), "q mismatch for {a}/{b}");
439            assert_eq!(r, BigInt::from(expected_r), "r mismatch for {a}%{b}");
440        }
441    }
442
443    #[test]
444    #[should_panic(expected = "BigInt: division by zero")]
445    fn div_by_zero_panics() {
446        let _ = &BigInt::from(10i64) / &BigInt::zero();
447    }
448
449    #[test]
450    fn add_assign_idempotent() {
451        let mut a = BigInt::from(10i64);
452        a += BigInt::from(5i64);
453        assert_eq!(a, BigInt::from(15i64));
454        a -= &BigInt::from(7i64);
455        assert_eq!(a, BigInt::from(8i64));
456        a *= BigInt::from(-2i64);
457        assert_eq!(a, BigInt::from(-16i64));
458        a /= &BigInt::from(3i64);
459        assert_eq!(a, BigInt::from(-5i64));
460        a %= BigInt::from(2i64);
461        assert_eq!(a, BigInt::from(-1i64));
462    }
463}
oxinum_int/native/ops_int.rs

oxinum_int/native/
ops_int.rs
