malachite_nz/integer_vector/arithmetic/mod_power_of_2.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::integer_vector::IntegerVector;
10use crate::natural_vector::NaturalVector;
11use malachite_base::num::arithmetic::traits::{ModPowerOf2, RemPowerOf2, RemPowerOf2Assign};
12
13impl ModPowerOf2 for IntegerVector {
14 type Output = NaturalVector;
15
16 /// Divides every element of an [`IntegerVector`] by $2^k$, keeping the remainders as a
17 /// [`NaturalVector`], taking the vector by value.
18 ///
19 /// Each remainder is non-negative, as with [`ModPowerOf2`] for
20 /// [`Integer`](crate::integer::Integer): a negative element $x$ becomes $2^k - (-x \bmod 2^k)$
21 /// unless it is a multiple of $2^k$. So the result has natural elements, and is reduced modulo
22 /// $2^k$, which is to say that [`mod_power_of_2_is_reduced`](
23 /// malachite_base::num::arithmetic::traits::ModPowerOf2IsReduced::mod_power_of_2_is_reduced)
24 /// returns `true` for it. The dimension is unchanged: unlike a polynomial, a vector keeps the
25 /// elements that reduce to zero.
26 ///
27 /// $$
28 /// f(v, k) = w, \quad \text{where} \quad w_i = v_i - 2^k \left \lfloor \frac{v_i}{2^k}
29 /// \right \rfloor.
30 /// $$
31 ///
32 /// # Worst-case complexity
33 /// $T(n) = O(n)$
34 ///
35 /// $M(n) = O(n)$
36 ///
37 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
38 /// elements.
39 ///
40 /// # Examples
41 /// ```
42 /// use core::str::FromStr;
43 /// use malachite_base::num::arithmetic::traits::ModPowerOf2;
44 /// use malachite_nz::integer_vector::IntegerVector;
45 ///
46 /// // Every element is taken modulo 4, and negative ones become non-negative.
47 /// let v = IntegerVector::from_str("(1, -3, -2)").unwrap();
48 /// assert_eq!(v.clone().mod_power_of_2(2).to_string(), "(1, 1, 2)");
49 ///
50 /// // An element that reduces to zero stays, so the dimension is unchanged.
51 /// let v = IntegerVector::from_str("(-4, 3)").unwrap();
52 /// assert_eq!(v.clone().mod_power_of_2(2).to_string(), "(0, 3)");
53 /// ```
54 #[inline]
55 fn mod_power_of_2(self, pow: u64) -> NaturalVector {
56 NaturalVector {
57 elements: self
58 .elements
59 .into_iter()
60 .map(|x| x.mod_power_of_2(pow))
61 .collect(),
62 }
63 }
64}
65
66impl ModPowerOf2 for &IntegerVector {
67 type Output = NaturalVector;
68
69 /// Divides every element of an [`IntegerVector`] by $2^k$, keeping the remainders as a
70 /// [`NaturalVector`], taking the vector by reference.
71 ///
72 /// See the documentation for the [`ModPowerOf2`] implementation on [`IntegerVector`] that takes
73 /// the vector by value for details.
74 ///
75 /// # Worst-case complexity
76 /// $T(n) = O(n)$
77 ///
78 /// $M(n) = O(n)$
79 ///
80 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
81 /// elements.
82 ///
83 /// # Examples
84 /// ```
85 /// use core::str::FromStr;
86 /// use malachite_base::num::arithmetic::traits::ModPowerOf2;
87 /// use malachite_nz::integer_vector::IntegerVector;
88 ///
89 /// // Every element is taken modulo 4, and negative ones become non-negative.
90 /// let v = IntegerVector::from_str("(1, -3, -2)").unwrap();
91 /// assert_eq!((&v).mod_power_of_2(2).to_string(), "(1, 1, 2)");
92 ///
93 /// // An element that reduces to zero stays, so the dimension is unchanged.
94 /// let v = IntegerVector::from_str("(-4, 3)").unwrap();
95 /// assert_eq!((&v).mod_power_of_2(2).to_string(), "(0, 3)");
96 /// ```
97 #[inline]
98 fn mod_power_of_2(self, pow: u64) -> NaturalVector {
99 NaturalVector {
100 elements: self
101 .elements
102 .iter()
103 .map(|x| x.mod_power_of_2(pow))
104 .collect(),
105 }
106 }
107}
108
109impl RemPowerOf2 for IntegerVector {
110 type Output = Self;
111
112 /// Divides every element of an [`IntegerVector`] by $2^k$, keeping the remainders, taking the
113 /// vector by value.
114 ///
115 /// Each remainder has the sign of its element and a smaller absolute value than $2^k$, as with
116 /// [`RemPowerOf2`] for [`Integer`](crate::integer::Integer)s. This is the remainder of
117 /// truncating division, and the result stays an [`IntegerVector`]; for a remainder that is
118 /// always non-negative, and a [`NaturalVector`] result, use [`ModPowerOf2`]. The dimension is
119 /// unchanged.
120 ///
121 /// $$
122 /// f(v, k) = w, \quad \text{where} \quad w_i = v_i - 2^k \operatorname{sgn}(v_i)
123 /// \left \lfloor \frac{|v_i|}{2^k} \right \rfloor.
124 /// $$
125 ///
126 /// # Worst-case complexity
127 /// $T(n) = O(n)$
128 ///
129 /// $M(n) = O(1)$
130 ///
131 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
132 /// elements.
133 ///
134 /// # Examples
135 /// ```
136 /// use core::str::FromStr;
137 /// use malachite_base::num::arithmetic::traits::RemPowerOf2;
138 /// use malachite_nz::integer_vector::IntegerVector;
139 ///
140 /// // Every element is taken modulo 4, keeping its sign.
141 /// let v = IntegerVector::from_str("(1, -7, -2)").unwrap();
142 /// assert_eq!(v.clone().rem_power_of_2(2).to_string(), "(1, -3, -2)");
143 ///
144 /// // An element that reduces to zero stays, so the dimension is unchanged.
145 /// let v = IntegerVector::from_str("(-4, -3)").unwrap();
146 /// assert_eq!(v.clone().rem_power_of_2(2).to_string(), "(0, -3)");
147 /// ```
148 #[inline]
149 fn rem_power_of_2(mut self, pow: u64) -> Self {
150 self.rem_power_of_2_assign(pow);
151 self
152 }
153}
154
155impl RemPowerOf2 for &IntegerVector {
156 type Output = IntegerVector;
157
158 /// Divides every element of an [`IntegerVector`] by $2^k$, keeping the remainders, taking the
159 /// vector by reference.
160 ///
161 /// See the documentation for the [`RemPowerOf2`] implementation on [`IntegerVector`] that takes
162 /// the vector by value for details.
163 ///
164 /// # Worst-case complexity
165 /// $T(n) = O(n)$
166 ///
167 /// $M(n) = O(n)$
168 ///
169 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
170 /// elements.
171 ///
172 /// # Examples
173 /// ```
174 /// use core::str::FromStr;
175 /// use malachite_base::num::arithmetic::traits::RemPowerOf2;
176 /// use malachite_nz::integer_vector::IntegerVector;
177 ///
178 /// // Every element is taken modulo 4, keeping its sign.
179 /// let v = IntegerVector::from_str("(1, -7, -2)").unwrap();
180 /// assert_eq!((&v).rem_power_of_2(2).to_string(), "(1, -3, -2)");
181 ///
182 /// // An element that reduces to zero stays, so the dimension is unchanged.
183 /// let v = IntegerVector::from_str("(-4, -3)").unwrap();
184 /// assert_eq!((&v).rem_power_of_2(2).to_string(), "(0, -3)");
185 /// ```
186 #[inline]
187 fn rem_power_of_2(self, pow: u64) -> IntegerVector {
188 IntegerVector {
189 elements: self
190 .elements
191 .iter()
192 .map(|x| x.rem_power_of_2(pow))
193 .collect(),
194 }
195 }
196}
197
198impl RemPowerOf2Assign for IntegerVector {
199 /// Divides every element of an [`IntegerVector`] by $2^k$, replacing each element by the
200 /// remainder.
201 ///
202 /// See the documentation for the [`RemPowerOf2`] implementation on [`IntegerVector`] that takes
203 /// the vector by value for details.
204 ///
205 /// # Worst-case complexity
206 /// $T(n) = O(n)$
207 ///
208 /// $M(n) = O(1)$
209 ///
210 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
211 /// elements.
212 ///
213 /// # Examples
214 /// ```
215 /// use core::str::FromStr;
216 /// use malachite_base::num::arithmetic::traits::RemPowerOf2Assign;
217 /// use malachite_nz::integer_vector::IntegerVector;
218 ///
219 /// let mut v = IntegerVector::from_str("(1, -7, -2)").unwrap();
220 /// v.rem_power_of_2_assign(2);
221 /// assert_eq!(v.to_string(), "(1, -3, -2)");
222 /// ```
223 fn rem_power_of_2_assign(&mut self, pow: u64) {
224 for x in &mut self.elements {
225 x.rem_power_of_2_assign(pow);
226 }
227 }
228}