malachite_base/unsigned_vector/arithmetic/
mod_power_of_2_mul.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::{ModPowerOf2IsReduced, ModPowerOf2Mul, ModPowerOf2MulAssign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12
13fn assert_reduced<T: PrimitiveUnsigned>(v: &UnsignedVector<T>, c: T, pow: u64) {
14    assert!(
15        pow <= T::WIDTH,
16        "pow must be at most T::WIDTH, but it is {pow}"
17    );
18    assert!(
19        v.mod_power_of_2_is_reduced(pow),
20        "self must be reduced mod 2^pow, but {v} has an element >= 2^{pow}"
21    );
22    assert!(
23        c.mod_power_of_2_is_reduced(pow),
24        "c must be reduced mod 2^pow, but {c} >= 2^{pow}"
25    );
26}
27
28impl<T: PrimitiveUnsigned> ModPowerOf2Mul<T> for UnsignedVector<T> {
29    type Output = Self;
30
31    /// Multiplies every element of an [`UnsignedVector`] by a scalar modulo $2^k$, taking the
32    /// vector by value. The elements and the scalar must already be reduced modulo $2^k$.
33    ///
34    /// Each product is reduced modulo $2^k$, and the result has the same dimension as the vector.
35    ///
36    /// $$
37    /// f(v, c, k) = cv \bmod 2^k.
38    /// $$
39    ///
40    /// # Worst-case complexity
41    /// $T(n) = O(n)$
42    ///
43    /// $M(n) = O(1)$
44    ///
45    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
46    ///
47    /// # Panics
48    /// Panics if `pow` is greater than `T::WIDTH`, or if any element of `self`, or `c`, is greater
49    /// than or equal to $2^k$.
50    ///
51    /// # Examples
52    /// ```
53    /// use core::str::FromStr;
54    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Mul;
55    /// use malachite_base::unsigned_vector::UnsignedVector;
56    ///
57    /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
58    /// assert_eq!(v.mod_power_of_2_mul(3, 3).to_string(), "(7, 3, 1)");
59    /// ```
60    #[inline]
61    fn mod_power_of_2_mul(mut self, c: T, pow: u64) -> Self {
62        self.mod_power_of_2_mul_assign(c, pow);
63        self
64    }
65}
66
67impl<T: PrimitiveUnsigned> ModPowerOf2Mul<T> for &UnsignedVector<T> {
68    type Output = UnsignedVector<T>;
69
70    /// Multiplies every element of an [`UnsignedVector`] by a scalar modulo $2^k$, taking the
71    /// vector by reference. The elements and the scalar must already be reduced modulo $2^k$.
72    ///
73    /// See the documentation for the [`ModPowerOf2Mul`] implementation that takes the vector by
74    /// value for details.
75    ///
76    /// # Worst-case complexity
77    /// $T(n) = O(n)$
78    ///
79    /// $M(n) = O(n)$
80    ///
81    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
82    ///
83    /// # Panics
84    /// Panics if `pow` is greater than `T::WIDTH`, or if any element of `self`, or `c`, is greater
85    /// than or equal to $2^k$.
86    ///
87    /// # Examples
88    /// ```
89    /// use core::str::FromStr;
90    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Mul;
91    /// use malachite_base::unsigned_vector::UnsignedVector;
92    ///
93    /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
94    /// assert_eq!((&v).mod_power_of_2_mul(3, 3).to_string(), "(7, 3, 1)");
95    /// ```
96    fn mod_power_of_2_mul(self, c: T, pow: u64) -> UnsignedVector<T> {
97        assert_reduced(self, c, pow);
98        UnsignedVector {
99            elements: self
100                .elements
101                .iter()
102                .map(|&x| x.mod_power_of_2_mul(c, pow))
103                .collect(),
104        }
105    }
106}
107
108impl<T: PrimitiveUnsigned> ModPowerOf2MulAssign<T> for UnsignedVector<T> {
109    /// Multiplies every element of an [`UnsignedVector`] by a scalar modulo $2^k$, in place. The
110    /// elements and the scalar must already be reduced modulo $2^k$.
111    ///
112    /// See the documentation for the [`ModPowerOf2Mul`] implementation that takes the vector by
113    /// value for details.
114    ///
115    /// # Worst-case complexity
116    /// $T(n) = O(n)$
117    ///
118    /// $M(n) = O(1)$
119    ///
120    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
121    ///
122    /// # Panics
123    /// Panics if `pow` is greater than `T::WIDTH`, or if any element of `self`, or `c`, is greater
124    /// than or equal to $2^k$.
125    ///
126    /// # Examples
127    /// ```
128    /// use core::str::FromStr;
129    /// use malachite_base::num::arithmetic::traits::ModPowerOf2MulAssign;
130    /// use malachite_base::unsigned_vector::UnsignedVector;
131    ///
132    /// let mut v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
133    /// v.mod_power_of_2_mul_assign(3, 3);
134    /// assert_eq!(v.to_string(), "(7, 3, 1)");
135    /// ```
136    fn mod_power_of_2_mul_assign(&mut self, c: T, pow: u64) {
137        assert_reduced(self, c, pow);
138        for x in &mut self.elements {
139            x.mod_power_of_2_mul_assign(c, pow);
140        }
141    }
142}
malachite_base/unsigned_vector/arithmetic/mod_power_of_2_mul.rs

malachite_base/unsigned_vector/arithmetic/
mod_power_of_2_mul.rs
