dashu_int/modular/
add.rs

1//! Modular addition and subtraction.
2
3use super::repr::{Reduced, ReducedDword, ReducedLarge, ReducedRepr, ReducedWord};
4use crate::{add, cmp, div_const::ConstLargeDivisor, error::panic_different_rings, shift};
5use core::ops::{Add, AddAssign, Neg, Sub, SubAssign};
6use num_modular::Reducer;
7
8impl<'a> Neg for Reduced<'a> {
9    type Output = Reduced<'a>;
10
11    #[inline]
12    fn neg(self) -> Reduced<'a> {
13        match self.into_repr() {
14            ReducedRepr::Single(raw, ring) => {
15                Self::from_single(ReducedWord(ring.0.neg(raw.0)), ring)
16            }
17            ReducedRepr::Double(raw, ring) => {
18                Self::from_double(ReducedDword(ring.0.neg(raw.0)), ring)
19            }
20            ReducedRepr::Large(mut raw, ring) => {
21                negate_in_place(ring, &mut raw);
22                Self::from_large(raw, ring)
23            }
24        }
25    }
26}
27
28impl<'a> Neg for &Reduced<'a> {
29    type Output = Reduced<'a>;
30
31    #[inline]
32    fn neg(self) -> Reduced<'a> {
33        self.clone().neg()
34    }
35}
36
37impl<'a> Add<Reduced<'a>> for Reduced<'a> {
38    type Output = Reduced<'a>;
39
40    #[inline]
41    fn add(self, rhs: Reduced<'a>) -> Reduced<'a> {
42        self.add(&rhs)
43    }
44}
45
46impl<'a> Add<&Reduced<'a>> for Reduced<'a> {
47    type Output = Reduced<'a>;
48
49    #[inline]
50    fn add(mut self, rhs: &Reduced<'a>) -> Reduced<'a> {
51        self.add_assign(rhs);
52        self
53    }
54}
55
56impl<'a> Add<Reduced<'a>> for &Reduced<'a> {
57    type Output = Reduced<'a>;
58
59    #[inline]
60    fn add(self, rhs: Reduced<'a>) -> Reduced<'a> {
61        rhs.add(self)
62    }
63}
64
65impl<'a> Add<&Reduced<'a>> for &Reduced<'a> {
66    type Output = Reduced<'a>;
67
68    #[inline]
69    fn add(self, rhs: &Reduced<'a>) -> Reduced<'a> {
70        self.clone().add(rhs)
71    }
72}
73
74impl<'a> AddAssign<Reduced<'a>> for Reduced<'a> {
75    #[inline]
76    fn add_assign(&mut self, rhs: Reduced<'a>) {
77        self.add_assign(&rhs)
78    }
79}
80
81impl<'a> AddAssign<&Reduced<'a>> for Reduced<'a> {
82    #[inline]
83    fn add_assign(&mut self, rhs: &Reduced<'a>) {
84        match (self.repr_mut(), rhs.repr()) {
85            (ReducedRepr::Single(raw0, ring), ReducedRepr::Single(raw1, ring1)) => {
86                Reduced::check_same_ring_single(ring, ring1);
87                ring.0.add_in_place(&mut raw0.0, &raw1.0);
88            }
89            (ReducedRepr::Double(raw0, ring), ReducedRepr::Double(raw1, ring1)) => {
90                Reduced::check_same_ring_double(ring, ring1);
91                ring.0.add_in_place(&mut raw0.0, &raw1.0);
92            }
93            (ReducedRepr::Large(raw0, ring), ReducedRepr::Large(raw1, ring1)) => {
94                Reduced::check_same_ring_large(ring, ring1);
95                add_in_place(ring, raw0, raw1);
96            }
97            _ => panic_different_rings(),
98        }
99    }
100}
101
102impl<'a> Sub<Reduced<'a>> for Reduced<'a> {
103    type Output = Reduced<'a>;
104
105    #[inline]
106    fn sub(self, rhs: Reduced<'a>) -> Reduced<'a> {
107        self.sub(&rhs)
108    }
109}
110
111impl<'a> Sub<&Reduced<'a>> for Reduced<'a> {
112    type Output = Reduced<'a>;
113
114    #[inline]
115    fn sub(mut self, rhs: &Reduced<'a>) -> Reduced<'a> {
116        self.sub_assign(rhs);
117        self
118    }
119}
120
121impl<'a> Sub<Reduced<'a>> for &Reduced<'a> {
122    type Output = Reduced<'a>;
123
124    #[inline]
125    fn sub(self, mut rhs: Reduced<'a>) -> Reduced<'a> {
126        match (self.repr(), rhs.repr_mut()) {
127            (ReducedRepr::Single(raw0, ring), ReducedRepr::Single(raw1, ring1)) => {
128                Reduced::check_same_ring_single(ring, ring1);
129                raw1.0 = ring.0.sub(&raw0.0, &raw1.0);
130            }
131            (ReducedRepr::Double(raw0, ring), ReducedRepr::Double(raw1, ring1)) => {
132                Reduced::check_same_ring_double(ring, ring1);
133                raw1.0 = ring.0.sub(&raw0.0, &raw1.0);
134            }
135            (ReducedRepr::Large(raw0, ring), ReducedRepr::Large(raw1, ring1)) => {
136                Reduced::check_same_ring_large(ring, ring1);
137                sub_in_place_swap(ring, raw0, raw1);
138            }
139            _ => panic_different_rings(),
140        }
141        rhs
142    }
143}
144
145impl<'a> Sub<&Reduced<'a>> for &Reduced<'a> {
146    type Output = Reduced<'a>;
147
148    #[inline]
149    fn sub(self, rhs: &Reduced<'a>) -> Reduced<'a> {
150        self.clone().sub(rhs)
151    }
152}
153
154impl<'a> SubAssign<Reduced<'a>> for Reduced<'a> {
155    #[inline]
156    fn sub_assign(&mut self, rhs: Reduced<'a>) {
157        self.sub_assign(&rhs)
158    }
159}
160
161impl<'a> SubAssign<&Reduced<'a>> for Reduced<'a> {
162    #[inline]
163    fn sub_assign(&mut self, rhs: &Reduced<'a>) {
164        match (self.repr_mut(), rhs.repr()) {
165            (ReducedRepr::Single(raw0, ring), ReducedRepr::Single(raw1, ring1)) => {
166                Reduced::check_same_ring_single(ring, ring1);
167                ring.0.sub_in_place(&mut raw0.0, &raw1.0);
168            }
169            (ReducedRepr::Double(raw0, ring), ReducedRepr::Double(raw1, ring1)) => {
170                Reduced::check_same_ring_double(ring, ring1);
171                ring.0.sub_in_place(&mut raw0.0, &raw1.0);
172            }
173            (ReducedRepr::Large(raw0, ring), ReducedRepr::Large(raw1, ring1)) => {
174                Reduced::check_same_ring_large(ring, ring1);
175                sub_in_place(ring, raw0, raw1);
176            }
177            _ => panic_different_rings(),
178        }
179    }
180}
181
182impl<'a> Reduced<'a> {
183    /// Calculate 2*target mod m in reduced form
184    ///
185    /// # Examples
186    ///
187    /// ```
188    /// # use dashu_int::{fast_div::ConstDivisor, UBig};
189    /// let p = UBig::from(0x1234u16);
190    /// let ring = ConstDivisor::new(p.clone());
191    /// let a = ring.reduce(4000);
192    /// assert_eq!(a.dbl(), ring.reduce(4000 + 4000));
193    /// ```
194    pub fn dbl(self) -> Self {
195        match self.into_repr() {
196            ReducedRepr::Single(raw, ring) => {
197                Reduced::from_single(ReducedWord(ring.0.dbl(raw.0)), ring)
198            }
199            ReducedRepr::Double(raw, ring) => {
200                Reduced::from_double(ReducedDword(ring.0.dbl(raw.0)), ring)
201            }
202            ReducedRepr::Large(mut raw, ring) => {
203                dbl_in_place(ring, &mut raw);
204                Reduced::from_large(raw, ring)
205            }
206        }
207    }
208}
209
210pub(crate) fn negate_in_place(ring: &ConstLargeDivisor, raw: &mut ReducedLarge) {
211    debug_assert!(raw.is_valid(ring));
212    if !raw.0.iter().all(|w| *w == 0) {
213        let overflow = add::sub_same_len_in_place_swap(&ring.normalized_divisor, &mut raw.0);
214        debug_assert!(!overflow);
215    }
216}
217
218fn add_in_place(ring: &ConstLargeDivisor, lhs: &mut ReducedLarge, rhs: &ReducedLarge) {
219    debug_assert!(lhs.is_valid(ring) && rhs.is_valid(ring));
220    let modulus = &ring.normalized_divisor;
221    let overflow = add::add_same_len_in_place(&mut lhs.0, &rhs.0);
222    if overflow || cmp::cmp_same_len(&lhs.0, modulus).is_ge() {
223        let overflow2 = add::sub_same_len_in_place(&mut lhs.0, modulus);
224        debug_assert_eq!(overflow, overflow2);
225    }
226}
227
228fn dbl_in_place(ring: &ConstLargeDivisor, raw: &mut ReducedLarge) {
229    debug_assert!(raw.is_valid(ring));
230    let modulus = &ring.normalized_divisor;
231    let overflow = shift::shl_in_place(&mut raw.0, 1) > 0;
232    if overflow || cmp::cmp_same_len(&raw.0, modulus).is_ge() {
233        let overflow2 = add::sub_same_len_in_place(&mut raw.0, modulus);
234        debug_assert_eq!(overflow, overflow2);
235    }
236}
237
238fn sub_in_place(ring: &ConstLargeDivisor, lhs: &mut ReducedLarge, rhs: &ReducedLarge) {
239    debug_assert!(lhs.is_valid(ring) && rhs.is_valid(ring));
240    let modulus = &ring.normalized_divisor;
241    let overflow = add::sub_same_len_in_place(&mut lhs.0, &rhs.0);
242    if overflow {
243        let overflow2 = add::add_same_len_in_place(&mut lhs.0, modulus);
244        debug_assert!(overflow2);
245    }
246}
247
248/// rhs = self - rhs
249fn sub_in_place_swap(ring: &ConstLargeDivisor, lhs: &ReducedLarge, rhs: &mut ReducedLarge) {
250    debug_assert!(lhs.is_valid(ring) && rhs.is_valid(ring));
251    let modulus = &ring.normalized_divisor;
252    let overflow = add::sub_same_len_in_place_swap(&lhs.0, &mut rhs.0);
253    if overflow {
254        let overflow2 = add::add_same_len_in_place(&mut rhs.0, modulus);
255        debug_assert!(overflow2);
256    }
257}
dashu_int/modular/add.rs

dashu_int/modular/
add.rs
