malachite_base/unsigned_vector/arithmetic/mod_add_mul_shl.rs
1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::{ModAddMulAssign, ModAddMulShl, ModAddMulShlAssign, ModShl};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12
13// Since $cw2^b \equiv w(c2^b \bmod m) \pmod m$, the shift is applied to the scalar once, and the
14// result is `mod_add_mul_assign` by the shifted scalar.
15fn shifted_scalar<T: PrimitiveUnsigned + ModShl<u64, T, Output = T>>(c: T, bits: u64, m: T) -> T {
16 assert!(c < m, "c must be reduced mod m, but {c} >= {m}");
17 c.mod_shl(bits, m)
18}
19
20impl<T: PrimitiveUnsigned + ModShl<u64, T, Output = T>> ModAddMulShl<Self, T, T>
21 for UnsignedVector<T>
22{
23 type Output = Self;
24
25 /// Adds a scalar multiple of an [`UnsignedVector`], shifted left by `bits`, to an
26 /// [`UnsignedVector`] modulo $m$, taking both vectors by value. The elements and the scalar
27 /// must already be reduced modulo $m$.
28 ///
29 /// The operation is taken element by element, so the result has the same dimension as the
30 /// vectors.
31 ///
32 /// $$
33 /// f(v, w, c, b, m) = (v + cw2^b) \bmod m.
34 /// $$
35 ///
36 /// # Worst-case complexity
37 /// $T(n, b) = O(n + \log b)$
38 ///
39 /// $M(n) = O(1)$
40 ///
41 /// where $T$ is time, $M$ is additional memory, $n$ is `self.dimension()`, and $b$ is `bits`.
42 ///
43 /// # Panics
44 /// Panics if `self` and `w` have different dimensions, or if any element of `self` or `w`, or
45 /// `c`, is greater than or equal to `m`.
46 ///
47 /// # Examples
48 /// ```
49 /// use core::str::FromStr;
50 /// use malachite_base::num::arithmetic::traits::ModAddMulShl;
51 /// use malachite_base::unsigned_vector::UnsignedVector;
52 ///
53 /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
54 /// let w = UnsignedVector::<u8>::from_str("(2, 6, 4)").unwrap();
55 /// assert_eq!(v.mod_add_mul_shl(w, 3, 2, 7).to_string(), "(1, 3, 2)");
56 /// ```
57 #[inline]
58 fn mod_add_mul_shl(mut self, w: Self, c: T, bits: u64, m: T) -> Self {
59 self.mod_add_mul_shl_assign(&w, c, bits, m);
60 self
61 }
62}
63
64impl<T: PrimitiveUnsigned + ModShl<u64, T, Output = T>> ModAddMulShl<&Self, T, T>
65 for UnsignedVector<T>
66{
67 type Output = Self;
68
69 /// Adds a scalar multiple of an [`UnsignedVector`], shifted left by `bits`, to an
70 /// [`UnsignedVector`] modulo $m$, taking the first vector by value and the second by reference.
71 /// The elements and the scalar must already be reduced modulo $m$.
72 ///
73 /// See the documentation for the [`ModAddMulShl`] implementation that takes both vectors by
74 /// value for details.
75 ///
76 /// # Worst-case complexity
77 /// $T(n, b) = O(n + \log b)$
78 ///
79 /// $M(n) = O(1)$
80 ///
81 /// where $T$ is time, $M$ is additional memory, $n$ is `self.dimension()`, and $b$ is `bits`.
82 ///
83 /// # Panics
84 /// Panics if `self` and `w` have different dimensions, or if any element of `self` or `w`, or
85 /// `c`, is greater than or equal to `m`.
86 ///
87 /// # Examples
88 /// ```
89 /// use core::str::FromStr;
90 /// use malachite_base::num::arithmetic::traits::ModAddMulShl;
91 /// use malachite_base::unsigned_vector::UnsignedVector;
92 ///
93 /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
94 /// let w = UnsignedVector::<u8>::from_str("(2, 6, 4)").unwrap();
95 /// assert_eq!(v.mod_add_mul_shl(&w, 3, 2, 7).to_string(), "(1, 3, 2)");
96 /// ```
97 #[inline]
98 fn mod_add_mul_shl(mut self, w: &Self, c: T, bits: u64, m: T) -> Self {
99 self.mod_add_mul_shl_assign(w, c, bits, m);
100 self
101 }
102}
103
104impl<T: PrimitiveUnsigned + ModShl<u64, T, Output = T>> ModAddMulShl<&UnsignedVector<T>, T, T>
105 for &UnsignedVector<T>
106{
107 type Output = UnsignedVector<T>;
108
109 /// Adds a scalar multiple of an [`UnsignedVector`], shifted left by `bits`, to an
110 /// [`UnsignedVector`] modulo $m$, taking both vectors by reference. The elements and the scalar
111 /// must already be reduced modulo $m$.
112 ///
113 /// See the documentation for the [`ModAddMulShl`] implementation that takes both vectors by
114 /// value for details.
115 ///
116 /// # Worst-case complexity
117 /// $T(n, b) = O(n + \log b)$
118 ///
119 /// $M(n) = O(n)$
120 ///
121 /// where $T$ is time, $M$ is additional memory, $n$ is `self.dimension()`, and $b$ is `bits`.
122 ///
123 /// # Panics
124 /// Panics if `self` and `w` have different dimensions, or if any element of `self` or `w`, or
125 /// `c`, is greater than or equal to `m`.
126 ///
127 /// # Examples
128 /// ```
129 /// use core::str::FromStr;
130 /// use malachite_base::num::arithmetic::traits::ModAddMulShl;
131 /// use malachite_base::unsigned_vector::UnsignedVector;
132 ///
133 /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
134 /// let w = UnsignedVector::<u8>::from_str("(2, 6, 4)").unwrap();
135 /// assert_eq!((&v).mod_add_mul_shl(&w, 3, 2, 7).to_string(), "(1, 3, 2)");
136 /// ```
137 fn mod_add_mul_shl(self, w: &UnsignedVector<T>, c: T, bits: u64, m: T) -> UnsignedVector<T> {
138 let mut v = self.clone();
139 v.mod_add_mul_shl_assign(w, c, bits, m);
140 v
141 }
142}
143
144impl<T: PrimitiveUnsigned + ModShl<u64, T, Output = T>> ModAddMulShlAssign<Self, T, T>
145 for UnsignedVector<T>
146{
147 /// Adds a scalar multiple of an [`UnsignedVector`], shifted left by `bits`, to an
148 /// [`UnsignedVector`] modulo $m$, in place, taking the vector on the right-hand side by value.
149 /// The elements and the scalar must already be reduced modulo $m$.
150 ///
151 /// See the documentation for the [`ModAddMulShl`] implementation that takes both vectors by
152 /// value for details.
153 ///
154 /// # Worst-case complexity
155 /// $T(n, b) = O(n + \log b)$
156 ///
157 /// $M(n) = O(1)$
158 ///
159 /// where $T$ is time, $M$ is additional memory, $n$ is `self.dimension()`, and $b$ is `bits`.
160 ///
161 /// # Panics
162 /// Panics if `self` and `w` have different dimensions, or if any element of `self` or `w`, or
163 /// `c`, is greater than or equal to `m`.
164 ///
165 /// # Examples
166 /// ```
167 /// use core::str::FromStr;
168 /// use malachite_base::num::arithmetic::traits::ModAddMulShlAssign;
169 /// use malachite_base::unsigned_vector::UnsignedVector;
170 ///
171 /// let mut v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
172 /// let w = UnsignedVector::<u8>::from_str("(2, 6, 4)").unwrap();
173 /// v.mod_add_mul_shl_assign(w, 3, 2, 7);
174 /// assert_eq!(v.to_string(), "(1, 3, 2)");
175 /// ```
176 #[inline]
177 fn mod_add_mul_shl_assign(&mut self, w: Self, c: T, bits: u64, m: T) {
178 self.mod_add_mul_shl_assign(&w, c, bits, m);
179 }
180}
181
182impl<T: PrimitiveUnsigned + ModShl<u64, T, Output = T>> ModAddMulShlAssign<&Self, T, T>
183 for UnsignedVector<T>
184{
185 /// Adds a scalar multiple of an [`UnsignedVector`], shifted left by `bits`, to an
186 /// [`UnsignedVector`] modulo $m$, in place, taking the vector on the right-hand side by
187 /// reference. The elements and the scalar must already be reduced modulo $m$.
188 ///
189 /// See the documentation for the [`ModAddMulShl`] implementation that takes both vectors by
190 /// value for details.
191 ///
192 /// # Worst-case complexity
193 /// $T(n, b) = O(n + \log b)$
194 ///
195 /// $M(n) = O(1)$
196 ///
197 /// where $T$ is time, $M$ is additional memory, $n$ is `self.dimension()`, and $b$ is `bits`.
198 ///
199 /// # Panics
200 /// Panics if `self` and `w` have different dimensions, or if any element of `self` or `w`, or
201 /// `c`, is greater than or equal to `m`.
202 ///
203 /// # Examples
204 /// ```
205 /// use core::str::FromStr;
206 /// use malachite_base::num::arithmetic::traits::ModAddMulShlAssign;
207 /// use malachite_base::unsigned_vector::UnsignedVector;
208 ///
209 /// let mut v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
210 /// let w = UnsignedVector::<u8>::from_str("(2, 6, 4)").unwrap();
211 /// v.mod_add_mul_shl_assign(&w, 3, 2, 7);
212 /// assert_eq!(v.to_string(), "(1, 3, 2)");
213 /// ```
214 #[inline]
215 fn mod_add_mul_shl_assign(&mut self, w: &Self, c: T, bits: u64, m: T) {
216 self.mod_add_mul_assign(w, shifted_scalar(c, bits, m), m);
217 }
218}