relp_num/integer/big/ops/
mod.rs

1use std::hint::assert_unchecked;
2use std::ops::{Add, AddAssign, Mul};
3
4use num_traits::Zero;
5
6use crate::integer::big::{NonZeroUbig, Ubig};
7use crate::integer::big::ops::non_zero::{add_assign, mul_non_zero};
8
9pub(crate) mod building_blocks;
10pub mod non_zero;
11pub mod div;
12pub mod normalize;
13#[cfg(test)]
14mod normalize_bench;
15
16
17impl<const S: usize> Add for Ubig<S> {
18    type Output = Self;
19
20    #[inline]
21    fn add(self, rhs: Self) -> Self::Output {
22        let (mut left, right) = if rhs.0.len() > self.0.len() {
23            (rhs, self)
24        } else {
25            (self, rhs)
26        };
27
28        if right.is_zero() {
29            return left;
30        }
31
32        left += &right;
33
34        left
35    }
36}
37
38
39impl<const S: usize> Add for NonZeroUbig<S> {
40    type Output = Self;
41
42    #[inline]
43    fn add(self, rhs: Self) -> Self::Output {
44        let (mut left, right) = if rhs.0.len() > self.0.len() {
45            (rhs, self)
46        } else {
47            (self, rhs)
48        };
49
50        left += &right;
51
52        left
53    }
54}
55
56
57impl<const S: usize> AddAssign<&Self> for Ubig<S> {
58    #[inline]
59    fn add_assign(&mut self, rhs: &Ubig<S>) {
60        add_assign(&mut self.0, &rhs.0);
61    }
62}
63
64impl<const S: usize> AddAssign<&Self> for NonZeroUbig<S> {
65    #[inline]
66    fn add_assign(&mut self, rhs: &Self) {
67        unsafe {
68            // SAFETY: Is non zero so not empty
69            assert_unchecked(!self.0.is_empty());
70            assert_unchecked(!rhs.0.is_empty());
71        }
72        add_assign(&mut self.0, &rhs.0);
73    }
74}
75
76impl<const S: usize> Mul for Ubig<S> {
77    type Output = Self;
78
79    fn mul(mut self, rhs: Self) -> Self::Output {
80        if !self.is_zero() && !rhs.is_zero() {
81            unsafe {
82                // SAFETY: Are not empty so not zero
83                Self(mul_non_zero(&self.0, &rhs.0))
84            }
85        } else {
86            self.set_zero();
87            self
88        }
89    }
90}
91
92impl<const S: usize> Mul for NonZeroUbig<S> {
93    type Output = Self;
94
95    fn mul(self, rhs: Self) -> Self::Output {
96        unsafe {
97            // SAFETY: Are not empty so not zero
98            Self(mul_non_zero(&self.0, &rhs.0))
99        }
100    }
101}
102
103#[cfg(test)]
104mod test {
105    use std::str::FromStr;
106
107    use num_traits::One;
108    use smallvec::smallvec;
109
110    use crate::{NonZeroUbig, Ubig};
111
112    #[test]
113    fn test_add() {
114        assert_eq!(Ubig::<8>::from(0_usize) + Ubig::<8>::from(0_usize), Ubig::<8>::from(0_usize));
115        assert_eq!(Ubig::<8>::from(0_usize) + Ubig::<8>::from(1_usize), Ubig::<8>::from(1_usize));
116        assert_eq!(Ubig::<8>::from(1_usize) + Ubig::<8>::from(0_usize), Ubig::<8>::from(1_usize));
117        assert_eq!(Ubig::<8>::from(8_usize) + Ubig::<8>::from(9_usize), Ubig::<8>::from(17_usize));
118        assert_eq!(
119            Ubig::<8>::from(usize::MAX) + Ubig::<8>::from(1_usize),
120            unsafe { Ubig::<8>::from_inner_unchecked(smallvec![0, 1]) },
121        );
122    }
123
124    #[test]
125    fn test_add_unequal_lengths() {
126        // A carry out of the shorter operand has to be propagated into the higher words of the
127        // longer operand, not appended on top of it.
128
129        let one = Ubig::<8>::from(1_usize);
130
131        let large = Ubig::<8>::from_str("18446744073709551616").unwrap(); // 2 ** 64
132        let expected = Ubig::<8>::from_str("18446744073709551617").unwrap();
133        assert_eq!(one.clone() + large.clone(), expected);
134        assert_eq!(large + one.clone(), expected);
135
136        // [usize::MAX, 5] + [1] == [0, 6]
137        let left = unsafe { Ubig::<8>::from_inner_unchecked(smallvec![usize::MAX, 5]) };
138        let expected = unsafe { Ubig::<8>::from_inner_unchecked(smallvec![0, 6]) };
139        assert_eq!(left.clone() + one.clone(), expected);
140        assert_eq!(one.clone() + left, expected);
141
142        // A carry that travels across several words.
143        let left = unsafe {
144            Ubig::<8>::from_inner_unchecked(smallvec![usize::MAX, usize::MAX, usize::MAX, 5])
145        };
146        let expected = unsafe { Ubig::<8>::from_inner_unchecked(smallvec![0, 0, 0, 6]) };
147        assert_eq!(left.clone() + one.clone(), expected);
148        assert_eq!(one.clone() + left, expected);
149
150        // A carry that travels across several words and out of the top one.
151        let left = unsafe {
152            Ubig::<8>::from_inner_unchecked(smallvec![usize::MAX, usize::MAX, usize::MAX])
153        };
154        let expected = unsafe { Ubig::<8>::from_inner_unchecked(smallvec![0, 0, 0, 1]) };
155        assert_eq!(left.clone() + one.clone(), expected);
156        assert_eq!(one.clone() + left, expected);
157
158        // Longer operand on the right, no carry at all.
159        let left = unsafe { Ubig::<8>::from_inner_unchecked(smallvec![1, 2, 3]) };
160        let right = unsafe { Ubig::<8>::from_inner_unchecked(smallvec![10, 20]) };
161        let expected = unsafe { Ubig::<8>::from_inner_unchecked(smallvec![11, 22, 3]) };
162        assert_eq!(left.clone() + right.clone(), expected);
163        assert_eq!(right + left, expected);
164    }
165
166    #[test]
167    fn test_add_non_zero_unequal_lengths() {
168        let one = NonZeroUbig::<8>::one();
169
170        let large = NonZeroUbig::<8>::from_str("18446744073709551616").unwrap(); // 2 ** 64
171        let expected = NonZeroUbig::<8>::from_str("18446744073709551617").unwrap();
172        assert_eq!(one.clone() + large.clone(), expected);
173        assert_eq!(large + one.clone(), expected);
174
175        // [usize::MAX, 5] + [1] == [0, 6]
176        let left = unsafe { NonZeroUbig::<8>::from_inner_unchecked(smallvec![usize::MAX, 5]) };
177        let expected = unsafe { NonZeroUbig::<8>::from_inner_unchecked(smallvec![0, 6]) };
178        assert_eq!(left.clone() + one.clone(), expected);
179        assert_eq!(one.clone() + left, expected);
180
181        let left = unsafe {
182            NonZeroUbig::<8>::from_inner_unchecked(smallvec![usize::MAX, usize::MAX, usize::MAX, 5])
183        };
184        let expected = unsafe { NonZeroUbig::<8>::from_inner_unchecked(smallvec![0, 0, 0, 6]) };
185        assert_eq!(left.clone() + one.clone(), expected);
186        assert_eq!(one + left, expected);
187    }
188
189    #[test]
190    fn test_add_non_zero() {
191        assert_eq!(
192            NonZeroUbig::<8>::from_str("8").unwrap() + NonZeroUbig::<8>::from_str("9").unwrap(),
193            NonZeroUbig::<8>::from_str("17").unwrap(),
194        );
195        assert_eq!(
196            NonZeroUbig::<8>::from_str("18446744073709551615").unwrap() + NonZeroUbig::<8>::one(),
197            NonZeroUbig::<8>::from_str("18446744073709551616").unwrap(),
198        );
199    }
200
201    #[test]
202    fn test_mul() {
203        assert_eq!(Ubig::<8>::from(0_usize) * Ubig::<8>::from(0_usize), Ubig::<8>::from(0_usize));
204        assert_eq!(Ubig::<8>::from(0_usize) * Ubig::<8>::from(1_usize), Ubig::<8>::from(0_usize));
205        assert_eq!(Ubig::<8>::from(1_usize) * Ubig::<8>::from(0_usize), Ubig::<8>::from(0_usize));
206        assert_eq!(Ubig::<8>::from(8_usize) * Ubig::<8>::from(9_usize), Ubig::<8>::from(72_usize));
207        assert_eq!(
208            Ubig::<8>::from(usize::MAX) * Ubig::<8>::from(1_usize),
209            Ubig::<8>::from(usize::MAX),
210        );
211    }
212
213    #[test]
214    fn test_mul_non_zero() {
215        assert_eq!(
216            NonZeroUbig::<8>::from_str("8").unwrap() * NonZeroUbig::<8>::from_str("9").unwrap(),
217            NonZeroUbig::<8>::from_str("72").unwrap(),
218        );
219        assert_eq!(
220            NonZeroUbig::<8>::from_str("18446744073709551615").unwrap() * NonZeroUbig::<8>::one(),
221            NonZeroUbig::<8>::from_str("18446744073709551615").unwrap(),
222        );
223    }
224}
relp_num/integer/big/ops/mod.rs

relp_num/integer/big/ops/
mod.rs
