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