dashu_int/modular/
add.rs

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

dashu_int/modular/
add.rs
