num_bigint_dig/algorithms/
sub.rs

1use core::cmp;
2use core::cmp::Ordering::*;
3
4use num_traits::Zero;
5use smallvec::SmallVec;
6
7use crate::algorithms::cmp_slice;
8use crate::big_digit::{BigDigit, SignedDoubleBigDigit, BITS};
9use crate::bigint::Sign::{self, *};
10use crate::{BigUint, VEC_SIZE};
11
12/// Subtract with borrow:
13#[inline]
14pub fn sbb(a: BigDigit, b: BigDigit, acc: &mut SignedDoubleBigDigit) -> BigDigit {
15    *acc += a as SignedDoubleBigDigit;
16    *acc -= b as SignedDoubleBigDigit;
17    let lo = *acc as BigDigit;
18    *acc >>= BITS;
19    lo
20}
21
22pub fn sub2(a: &mut [BigDigit], b: &[BigDigit]) {
23    let mut borrow = 0;
24
25    let len = cmp::min(a.len(), b.len());
26    let (a_lo, a_hi) = a.split_at_mut(len);
27    let (b_lo, b_hi) = b.split_at(len);
28
29    for (a, b) in a_lo.iter_mut().zip(b_lo) {
30        *a = sbb(*a, *b, &mut borrow);
31    }
32
33    if borrow != 0 {
34        for a in a_hi {
35            *a = sbb(*a, 0, &mut borrow);
36            if borrow == 0 {
37                break;
38            }
39        }
40    }
41
42    // note: we're _required_ to fail on underflow
43    assert!(
44        borrow == 0 && b_hi.iter().all(|x| *x == 0),
45        "Cannot subtract b from a because b is larger than a."
46    );
47}
48
49// Only for the Sub impl. `a` and `b` must have same length.
50#[inline]
51pub fn __sub2rev(a: &[BigDigit], b: &mut [BigDigit]) -> BigDigit {
52    debug_assert!(b.len() == a.len());
53
54    let mut borrow = 0;
55
56    for (ai, bi) in a.iter().zip(b) {
57        *bi = sbb(*ai, *bi, &mut borrow);
58    }
59
60    borrow as BigDigit
61}
62
63pub fn sub2rev(a: &[BigDigit], b: &mut [BigDigit]) {
64    debug_assert!(b.len() >= a.len());
65
66    let len = cmp::min(a.len(), b.len());
67    let (a_lo, a_hi) = a.split_at(len);
68    let (b_lo, b_hi) = b.split_at_mut(len);
69
70    let borrow = __sub2rev(a_lo, b_lo);
71
72    assert!(a_hi.is_empty());
73
74    // note: we're _required_ to fail on underflow
75    assert!(
76        borrow == 0 && b_hi.iter().all(|x| *x == 0),
77        "Cannot subtract b from a because b is larger than a."
78    );
79}
80
81pub fn sub_sign(a: &[BigDigit], b: &[BigDigit]) -> (Sign, BigUint) {
82    // Normalize:
83    let a = &a[..a.iter().rposition(|&x| x != 0).map_or(0, |i| i + 1)];
84    let b = &b[..b.iter().rposition(|&x| x != 0).map_or(0, |i| i + 1)];
85
86    match cmp_slice(a, b) {
87        Greater => {
88            let mut a: SmallVec<[BigDigit; VEC_SIZE]> = a.into();
89            sub2(&mut a, b);
90            (Plus, BigUint::new_native(a))
91        }
92        Less => {
93            let mut b: SmallVec<[BigDigit; VEC_SIZE]> = b.into();
94            sub2(&mut b, a);
95            (Minus, BigUint::new_native(b))
96        }
97        _ => (NoSign, Zero::zero()),
98    }
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104
105    use num_traits::Num;
106
107    use crate::BigInt;
108
109    #[test]
110    fn test_sub_sign() {
111        fn sub_sign_i(a: &[BigDigit], b: &[BigDigit]) -> BigInt {
112            let (sign, val) = sub_sign(a, b);
113            BigInt::from_biguint(sign, val)
114        }
115
116        let a = BigUint::from_str_radix("265252859812191058636308480000000", 10).unwrap();
117        let b = BigUint::from_str_radix("26525285981219105863630848000000", 10).unwrap();
118        let a_i = BigInt::from_biguint(Plus, a.clone());
119        let b_i = BigInt::from_biguint(Plus, b.clone());
120
121        assert_eq!(sub_sign_i(&a.data[..], &b.data[..]), &a_i - &b_i);
122        assert_eq!(sub_sign_i(&b.data[..], &a.data[..]), &b_i - &a_i);
123    }
124}
num_bigint_dig/algorithms/sub.rs

num_bigint_dig/algorithms/
sub.rs
