malachite_base/unsigned_vector/arithmetic/
mod_power_of_2_neg.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, ModPowerOf2Neg, ModPowerOf2NegAssign};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_vector::UnsignedVector;
12
13fn assert_reduced<T: PrimitiveUnsigned>(v: &UnsignedVector<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}
23
24// Negates every element modulo 2^pow.
25fn negate<T: PrimitiveUnsigned>(elements: &mut [T], pow: u64) {
26    for x in elements {
27        *x = x.wrapping_neg().mod_power_of_2(pow);
28    }
29}
30
31impl<T: PrimitiveUnsigned> ModPowerOf2Neg for UnsignedVector<T> {
32    type Output = Self;
33
34    /// Negates an [`UnsignedVector`] modulo $2^k$, taking the vector by value. The elements must
35    /// already be reduced modulo $2^k$.
36    ///
37    /// Each element $x$ becomes $-x \bmod 2^k$: $2^k - x$ if $x$ is nonzero, and 0 if it is zero.
38    /// The dimension is unchanged.
39    ///
40    /// $$
41    /// f(v, k) = -v \bmod 2^k.
42    /// $$
43    ///
44    /// # Worst-case complexity
45    /// $T(n) = O(n)$
46    ///
47    /// $M(n) = O(1)$
48    ///
49    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
50    ///
51    /// # Panics
52    /// Panics if `pow` is greater than `T::WIDTH`, or if any element of `self` is greater than or
53    /// equal to $2^k$.
54    ///
55    /// # Examples
56    /// ```
57    /// use core::str::FromStr;
58    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Neg;
59    /// use malachite_base::unsigned_vector::UnsignedVector;
60    ///
61    /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
62    /// assert_eq!(v.mod_power_of_2_neg(3).to_string(), "(3, 7, 5)");
63    ///
64    /// // A zero element stays zero.
65    /// let v = UnsignedVector::<u8>::from_str("(0, 1)").unwrap();
66    /// assert_eq!(v.mod_power_of_2_neg(8).to_string(), "(0, 255)");
67    /// ```
68    ///
69    /// This is equivalent to `_nmod_vec_neg` from `nmod_vec/neg.c`, FLINT 3.6.0, with the modulus
70    /// $2^k$.
71    #[inline]
72    fn mod_power_of_2_neg(mut self, pow: u64) -> Self {
73        self.mod_power_of_2_neg_assign(pow);
74        self
75    }
76}
77
78impl<T: PrimitiveUnsigned> ModPowerOf2Neg for &UnsignedVector<T> {
79    type Output = UnsignedVector<T>;
80
81    /// Negates an [`UnsignedVector`] modulo $2^k$, taking the vector by reference. The elements
82    /// must already be reduced modulo $2^k$.
83    ///
84    /// Each element $x$ becomes $-x \bmod 2^k$: $2^k - x$ if $x$ is nonzero, and 0 if it is zero.
85    /// The dimension is unchanged.
86    ///
87    /// $$
88    /// f(v, k) = -v \bmod 2^k.
89    /// $$
90    ///
91    /// # Worst-case complexity
92    /// $T(n) = O(n)$
93    ///
94    /// $M(n) = O(n)$
95    ///
96    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
97    ///
98    /// # Panics
99    /// Panics if `pow` is greater than `T::WIDTH`, or if any element of `self` is greater than or
100    /// equal to $2^k$.
101    ///
102    /// # Examples
103    /// ```
104    /// use core::str::FromStr;
105    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Neg;
106    /// use malachite_base::unsigned_vector::UnsignedVector;
107    ///
108    /// let v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
109    /// assert_eq!((&v).mod_power_of_2_neg(3).to_string(), "(3, 7, 5)");
110    /// ```
111    ///
112    /// This is equivalent to `_nmod_vec_neg` from `nmod_vec/neg.c`, FLINT 3.6.0, with the modulus
113    /// $2^k$.
114    #[inline]
115    fn mod_power_of_2_neg(self, pow: u64) -> UnsignedVector<T> {
116        assert_reduced(self, pow);
117        let mut elements = self.elements.clone();
118        negate(&mut elements, pow);
119        UnsignedVector { elements }
120    }
121}
122
123impl<T: PrimitiveUnsigned> ModPowerOf2NegAssign for UnsignedVector<T> {
124    /// Negates an [`UnsignedVector`] modulo $2^k$, in place. The elements must already be reduced
125    /// modulo $2^k$.
126    ///
127    /// See [`mod_power_of_2_neg`](ModPowerOf2Neg::mod_power_of_2_neg).
128    ///
129    /// # Worst-case complexity
130    /// $T(n) = O(n)$
131    ///
132    /// $M(n) = O(1)$
133    ///
134    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.dimension()`.
135    ///
136    /// # Panics
137    /// Panics if `pow` is greater than `T::WIDTH`, or if any element of `self` is greater than or
138    /// equal to $2^k$.
139    ///
140    /// # Examples
141    /// ```
142    /// use core::str::FromStr;
143    /// use malachite_base::num::arithmetic::traits::ModPowerOf2NegAssign;
144    /// use malachite_base::unsigned_vector::UnsignedVector;
145    ///
146    /// let mut v = UnsignedVector::<u8>::from_str("(5, 1, 3)").unwrap();
147    /// v.mod_power_of_2_neg_assign(3);
148    /// assert_eq!(v.to_string(), "(3, 7, 5)");
149    /// ```
150    #[inline]
151    fn mod_power_of_2_neg_assign(&mut self, pow: u64) {
152        assert_reduced(self, pow);
153        negate(&mut self.elements, pow);
154    }
155}
malachite_base/unsigned_vector/arithmetic/mod_power_of_2_neg.rs

malachite_base/unsigned_vector/arithmetic/
mod_power_of_2_neg.rs
