malachite_base/unsigned_vector/arithmetic/mod_op.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::{Mod, ModAssign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12use core::ops::{Rem, RemAssign};
13
14impl<T: PrimitiveUnsigned> Rem<T> for UnsignedVector<T> {
15 type Output = Self;
16
17 /// Divides every element of an [`UnsignedVector`] by a `T`, keeping the remainders, taking the
18 /// vector by value.
19 ///
20 /// $v \\% m$ is the vector whose $i$th element is $v_i \\% m$. The dimension is unchanged:
21 /// unlike a polynomial, a vector keeps the elements that reduce to zero, so $(4, 3)$ modulo 4
22 /// is $(0, 3)$.
23 ///
24 /// The result is reduced modulo $m$, which is to say that
25 /// [`mod_is_reduced`](crate::num::arithmetic::traits::ModIsReduced::mod_is_reduced) returns
26 /// `true` for it.
27 ///
28 /// $$
29 /// f(v, m) = w, \\quad \text{where} \\quad w_i = v_i - m \left \lfloor \frac{v_i}{m}
30 /// \right \rfloor.
31 /// $$
32 ///
33 /// # Worst-case complexity
34 /// $T(n) = O(n)$
35 ///
36 /// $M(n) = O(1)$
37 ///
38 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
39 ///
40 /// # Panics
41 /// Panics if `m` is 0.
42 ///
43 /// # Examples
44 /// ```
45 /// use core::str::FromStr;
46 /// use malachite_base::unsigned_vector::UnsignedVector;
47 ///
48 /// let v = UnsignedVector::<u64>::from_str("(5, 4, 1)").unwrap();
49 /// assert_eq!((v % 3).to_string(), "(2, 1, 1)");
50 ///
51 /// // An element that reduces to zero stays, so the dimension is unchanged.
52 /// let v = UnsignedVector::<u64>::from_str("(4, 3)").unwrap();
53 /// assert_eq!((v % 4).to_string(), "(0, 3)");
54 /// ```
55 #[inline]
56 fn rem(mut self, m: T) -> Self {
57 self %= m;
58 self
59 }
60}
61
62impl<T: PrimitiveUnsigned> Rem<T> for &UnsignedVector<T> {
63 type Output = UnsignedVector<T>;
64
65 /// Divides every element of an [`UnsignedVector`] by a `T`, keeping the remainders, taking the
66 /// vector by reference.
67 ///
68 /// See the documentation for the [`Rem`] implementation on [`UnsignedVector`] that takes the
69 /// vector by value for details.
70 ///
71 /// # Worst-case complexity
72 /// $T(n) = O(n)$
73 ///
74 /// $M(n) = O(n)$
75 ///
76 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
77 ///
78 /// # Panics
79 /// Panics if `m` is 0.
80 ///
81 /// # Examples
82 /// ```
83 /// use core::str::FromStr;
84 /// use malachite_base::unsigned_vector::UnsignedVector;
85 ///
86 /// let v = UnsignedVector::<u64>::from_str("(5, 4, 1)").unwrap();
87 /// assert_eq!((&v % 3).to_string(), "(2, 1, 1)");
88 ///
89 /// // An element that reduces to zero stays, so the dimension is unchanged.
90 /// let v = UnsignedVector::<u64>::from_str("(4, 3)").unwrap();
91 /// assert_eq!((&v % 4).to_string(), "(0, 3)");
92 /// // The vector is left alone.
93 /// assert_eq!(v.to_string(), "(4, 3)");
94 /// ```
95 fn rem(self, m: T) -> UnsignedVector<T> {
96 assert_ne!(m, T::ZERO, "division by zero");
97 UnsignedVector {
98 elements: self.elements.iter().map(|&x| x % m).collect(),
99 }
100 }
101}
102
103impl<T: PrimitiveUnsigned> RemAssign<T> for UnsignedVector<T> {
104 /// Divides every element of an [`UnsignedVector`] by a `T`, replacing each element by the
105 /// remainder.
106 ///
107 /// See the documentation for the [`Rem`] implementation on [`UnsignedVector`] that takes the
108 /// vector by value for details.
109 ///
110 /// # Worst-case complexity
111 /// $T(n) = O(n)$
112 ///
113 /// $M(n) = O(1)$
114 ///
115 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
116 ///
117 /// # Panics
118 /// Panics if `m` is 0.
119 ///
120 /// # Examples
121 /// ```
122 /// use core::str::FromStr;
123 /// use malachite_base::unsigned_vector::UnsignedVector;
124 ///
125 /// let mut v = UnsignedVector::<u64>::from_str("(5, 4, 1)").unwrap();
126 /// v %= 3;
127 /// assert_eq!(v.to_string(), "(2, 1, 1)");
128 ///
129 /// let mut v = UnsignedVector::<u64>::from_str("(4, 3)").unwrap();
130 /// v %= 4;
131 /// assert_eq!(v.to_string(), "(0, 3)");
132 /// ```
133 fn rem_assign(&mut self, m: T) {
134 assert_ne!(m, T::ZERO, "division by zero");
135 for x in &mut self.elements {
136 *x %= m;
137 }
138 }
139}
140
141impl<T: PrimitiveUnsigned> Mod<T> for UnsignedVector<T> {
142 type Output = Self;
143
144 /// Divides every element of an [`UnsignedVector`] by a `T`, keeping the remainders, taking the
145 /// vector by value.
146 ///
147 /// An [`UnsignedVector`]'s elements are never negative, so this agrees with `%` everywhere; it
148 /// is the same operation under the name the mod-family traits use. See the documentation for
149 /// the [`Rem`] implementation on [`UnsignedVector`] that takes the vector by value for details.
150 ///
151 /// # Worst-case complexity
152 /// $T(n) = O(n)$
153 ///
154 /// $M(n) = O(1)$
155 ///
156 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
157 ///
158 /// # Panics
159 /// Panics if `m` is 0.
160 ///
161 /// # Examples
162 /// ```
163 /// use core::str::FromStr;
164 /// use malachite_base::num::arithmetic::traits::Mod;
165 /// use malachite_base::unsigned_vector::UnsignedVector;
166 ///
167 /// let v = UnsignedVector::<u64>::from_str("(4, 4, 5)").unwrap();
168 /// assert_eq!(v.mod_op(3).to_string(), "(1, 1, 2)");
169 /// ```
170 #[inline]
171 fn mod_op(self, m: T) -> Self {
172 self % m
173 }
174}
175
176impl<T: PrimitiveUnsigned> Mod<T> for &UnsignedVector<T> {
177 type Output = UnsignedVector<T>;
178
179 /// Divides every element of an [`UnsignedVector`] by a `T`, keeping the remainders, taking the
180 /// vector by reference.
181 ///
182 /// An [`UnsignedVector`]'s elements are never negative, so this agrees with `%` everywhere; it
183 /// is the same operation under the name the mod-family traits use. See the documentation for
184 /// the [`Rem`] implementation on [`UnsignedVector`] that takes the vector by value for details.
185 ///
186 /// # Worst-case complexity
187 /// $T(n) = O(n)$
188 ///
189 /// $M(n) = O(n)$
190 ///
191 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
192 ///
193 /// # Panics
194 /// Panics if `m` is 0.
195 ///
196 /// # Examples
197 /// ```
198 /// use core::str::FromStr;
199 /// use malachite_base::num::arithmetic::traits::Mod;
200 /// use malachite_base::unsigned_vector::UnsignedVector;
201 ///
202 /// let v = UnsignedVector::<u64>::from_str("(4, 4, 5)").unwrap();
203 /// assert_eq!((&v).mod_op(3).to_string(), "(1, 1, 2)");
204 /// ```
205 #[inline]
206 fn mod_op(self, m: T) -> UnsignedVector<T> {
207 self % m
208 }
209}
210
211impl<T: PrimitiveUnsigned> ModAssign<T> for UnsignedVector<T> {
212 /// Divides every element of an [`UnsignedVector`] by a `T`, replacing each element by the
213 /// remainder.
214 ///
215 /// An [`UnsignedVector`]'s elements are never negative, so this agrees with `%=` everywhere; it
216 /// is the same operation under the name the mod-family traits use. See the documentation for
217 /// the [`Rem`] implementation on [`UnsignedVector`] that takes the vector by value for details.
218 ///
219 /// # Worst-case complexity
220 /// $T(n) = O(n)$
221 ///
222 /// $M(n) = O(1)$
223 ///
224 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
225 ///
226 /// # Panics
227 /// Panics if `m` is 0.
228 ///
229 /// # Examples
230 /// ```
231 /// use core::str::FromStr;
232 /// use malachite_base::num::arithmetic::traits::ModAssign;
233 /// use malachite_base::unsigned_vector::UnsignedVector;
234 ///
235 /// let mut v = UnsignedVector::<u64>::from_str("(4, 4, 5)").unwrap();
236 /// v.mod_assign(3);
237 /// assert_eq!(v.to_string(), "(1, 1, 2)");
238 /// ```
239 #[inline]
240 fn mod_assign(&mut self, m: T) {
241 *self %= m;
242 }
243}