malachite_base/unsigned_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::num::arithmetic::traits::{ModPowerOf2, ModPowerOf2Assign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12
13impl<T: PrimitiveUnsigned> ModPowerOf2 for UnsignedVector<T> {
14    type Output = Self;
15
16    /// Divides every element of an [`UnsignedVector`] by $2^k$, keeping the remainders, taking the
17    /// vector by value.
18    ///
19    /// The result is reduced modulo $2^k$, which is to say that [`mod_power_of_2_is_reduced`](
20    /// crate::num::arithmetic::traits::ModPowerOf2IsReduced::mod_power_of_2_is_reduced) returns
21    /// `true` for it. The dimension is unchanged: unlike a polynomial, a vector keeps the elements
22    /// that reduce to zero, so $(4, 3)$ modulo 4 is $(0, 3)$.
23    ///
24    /// No `T` reaches $2^W$, where $W$ is `T::WIDTH`, so for $k \geq W$ this leaves the vector
25    /// alone.
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(1)$
36    ///
37    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
38    ///
39    /// # Examples
40    /// ```
41    /// use core::str::FromStr;
42    /// use malachite_base::num::arithmetic::traits::ModPowerOf2;
43    /// use malachite_base::unsigned_vector::UnsignedVector;
44    ///
45    /// // Every element is taken modulo 2.
46    /// assert_eq!(
47    ///     UnsignedVector::<u64>::from_str("(1, 3, 2)")
48    ///         .unwrap()
49    ///         .mod_power_of_2(1)
50    ///         .to_string(),
51    ///     "(1, 1, 0)"
52    /// );
53    ///
54    /// // An element that reduces to zero stays, so the dimension is unchanged.
55    /// assert_eq!(
56    ///     UnsignedVector::<u64>::from_str("(4, 3)")
57    ///         .unwrap()
58    ///         .mod_power_of_2(2)
59    ///         .to_string(),
60    ///     "(0, 3)"
61    /// );
62    ///
63    /// // A power at least as wide as the element type leaves the vector alone.
64    /// assert_eq!(
65    ///     UnsignedVector::<u8>::from_str("(255, 1)")
66    ///         .unwrap()
67    ///         .mod_power_of_2(8)
68    ///         .to_string(),
69    ///     "(255, 1)"
70    /// );
71    /// ```
72    #[inline]
73    fn mod_power_of_2(mut self, pow: u64) -> Self {
74        self.mod_power_of_2_assign(pow);
75        self
76    }
77}
78
79impl<T: PrimitiveUnsigned> ModPowerOf2 for &UnsignedVector<T> {
80    type Output = UnsignedVector<T>;
81
82    /// Divides every element of an [`UnsignedVector`] by $2^k$, keeping the remainders, taking the
83    /// vector by reference.
84    ///
85    /// See the documentation for the [`ModPowerOf2`] implementation on [`UnsignedVector`] for
86    /// details.
87    ///
88    /// # Worst-case complexity
89    /// $T(n) = O(n)$
90    ///
91    /// $M(n) = O(n)$
92    ///
93    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
94    ///
95    /// # Examples
96    /// ```
97    /// use core::str::FromStr;
98    /// use malachite_base::num::arithmetic::traits::ModPowerOf2;
99    /// use malachite_base::unsigned_vector::UnsignedVector;
100    ///
101    /// let v = UnsignedVector::<u64>::from_str("(4, 3)").unwrap();
102    /// assert_eq!((&v).mod_power_of_2(2).to_string(), "(0, 3)");
103    /// // The vector is left alone.
104    /// assert_eq!(v.to_string(), "(4, 3)");
105    /// ```
106    #[inline]
107    fn mod_power_of_2(self, pow: u64) -> UnsignedVector<T> {
108        UnsignedVector {
109            elements: self
110                .elements
111                .iter()
112                .map(|&x| x.mod_power_of_2(pow))
113                .collect(),
114        }
115    }
116}
117
118impl<T: PrimitiveUnsigned> ModPowerOf2Assign for UnsignedVector<T> {
119    /// Divides every element of an [`UnsignedVector`] by $2^k$, replacing each element by the
120    /// remainder.
121    ///
122    /// See the documentation for the [`ModPowerOf2`] implementation on [`UnsignedVector`] for
123    /// details.
124    ///
125    /// # Worst-case complexity
126    /// $T(n) = O(n)$
127    ///
128    /// $M(n) = O(1)$
129    ///
130    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
131    ///
132    /// # Examples
133    /// ```
134    /// use core::str::FromStr;
135    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Assign;
136    /// use malachite_base::unsigned_vector::UnsignedVector;
137    ///
138    /// let mut v = UnsignedVector::<u64>::from_str("(1, 3, 2)").unwrap();
139    /// v.mod_power_of_2_assign(1);
140    /// assert_eq!(v.to_string(), "(1, 1, 0)");
141    ///
142    /// let mut v = UnsignedVector::<u64>::from_str("(4, 3)").unwrap();
143    /// v.mod_power_of_2_assign(2);
144    /// assert_eq!(v.to_string(), "(0, 3)");
145    /// ```
146    fn mod_power_of_2_assign(&mut self, pow: u64) {
147        // A shortcut rather than a necessity: no `T` reaches its own width as a power, so a wide
148        // power is already the identity on every element.
149        if pow >= T::WIDTH {
150            return;
151        }
152        for x in &mut self.elements {
153            x.mod_power_of_2_assign(pow);
154        }
155    }
156}
malachite_base/unsigned_vector/arithmetic/mod_power_of_2.rs

malachite_base/unsigned_vector/arithmetic/
mod_power_of_2.rs
