malachite_base/unsigned_polynomial/arithmetic/mod_power_of_2_derivative.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;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::polynomial::{ModPowerOf2Derivative, ModPowerOf2DerivativeAssign};
12use crate::unsigned_polynomial::UnsignedPolynomial;
13
14fn assert_reduced<T: PrimitiveUnsigned>(p: &UnsignedPolynomial<T>, pow: u64) {
15 assert!(pow <= T::WIDTH);
16 assert!(
17 p.mod_power_of_2_is_reduced(pow),
18 "self must be reduced mod 2^pow, but {p} has a coefficient >= 2^{pow}"
19 );
20}
21
22// Multiplies the coefficient of x^i, for i at least 1, by i, reduces it modulo 2^pow, and moves it
23// to x^(i-1). Arithmetic modulo 2^WIDTH, with a wrapping running counter for i, loses nothing,
24// since 2^pow divides 2^WIDTH. The products can be zero, so the result is trimmed.
25fn mod_power_of_2_derivative_ref<T: PrimitiveUnsigned>(
26 p: &UnsignedPolynomial<T>,
27 pow: u64,
28) -> UnsignedPolynomial<T> {
29 assert_reduced(p, pow);
30 let mut i = T::ZERO;
31 let mut q = UnsignedPolynomial {
32 coefficients: p
33 .coefficients
34 .iter()
35 .skip(1)
36 .map(|&c| {
37 i.wrapping_add_assign(T::ONE);
38 c.wrapping_mul(i).mod_power_of_2(pow)
39 })
40 .collect(),
41 };
42 q.trim();
43 q
44}
45
46fn mod_power_of_2_derivative_in_place<T: PrimitiveUnsigned>(
47 p: &mut UnsignedPolynomial<T>,
48 pow: u64,
49) {
50 assert_reduced(p, pow);
51 if p.coefficients.is_empty() {
52 return;
53 }
54 p.coefficients.remove(0);
55 let mut i = T::ZERO;
56 for c in &mut p.coefficients {
57 i.wrapping_add_assign(T::ONE);
58 *c = c.wrapping_mul(i).mod_power_of_2(pow);
59 }
60 p.trim();
61}
62
63impl<T: PrimitiveUnsigned> ModPowerOf2Derivative for UnsignedPolynomial<T> {
64 type Output = Self;
65
66 /// Computes the derivative of an [`UnsignedPolynomial`] modulo $2^k$, taking the polynomial by
67 /// value. The coefficients must already be reduced modulo $2^k$.
68 ///
69 /// $$
70 /// f(p, k) = p' \bmod 2^k.
71 /// $$
72 ///
73 /// The coefficient of $x^i$ is multiplied by $i$, reduced, and moved to $x^{i-1}$. Since $ia_i$
74 /// can be divisible by the modulus even when $a_i$ is not zero, the derivative can lose any
75 /// number of degrees. A constant polynomial, including zero, has derivative zero.
76 ///
77 /// # Worst-case complexity
78 /// $T(n) = O(n)$
79 ///
80 /// $M(n) = O(n)$
81 ///
82 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
83 ///
84 /// # Panics
85 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is greater than
86 /// or equal to $2^k$.
87 ///
88 /// # Examples
89 /// ```
90 /// use core::str::FromStr;
91 /// use malachite_base::polynomial::ModPowerOf2Derivative;
92 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
93 ///
94 /// let p = UnsignedPolynomial::<u8>::from_str("x^3+3*x^2+2*x+1").unwrap();
95 /// assert_eq!(p.mod_power_of_2_derivative(2).to_string(), "3*x^2+2*x+2");
96 ///
97 /// let p = UnsignedPolynomial::<u8>::from_str("x^5+x").unwrap();
98 /// assert_eq!(p.mod_power_of_2_derivative(1).to_string(), "x^4+1");
99 ///
100 /// // The derivative can lose more than one degree.
101 /// let p = UnsignedPolynomial::<u8>::from_str("x^4+x^3+1").unwrap();
102 /// assert_eq!(p.mod_power_of_2_derivative(1).to_string(), "x^2");
103 /// ```
104 ///
105 /// This is equivalent to `nmod_poly_derivative` from `nmod_poly/derivative.c`, FLINT 3.6.0,
106 /// with the modulus $2^k$.
107 #[inline]
108 fn mod_power_of_2_derivative(mut self, pow: u64) -> Self {
109 mod_power_of_2_derivative_in_place(&mut self, pow);
110 self
111 }
112}
113
114impl<T: PrimitiveUnsigned> ModPowerOf2Derivative for &UnsignedPolynomial<T> {
115 type Output = UnsignedPolynomial<T>;
116
117 /// Computes the derivative of an [`UnsignedPolynomial`] modulo $2^k$, taking the polynomial by
118 /// reference. The coefficients must already be reduced modulo $2^k$.
119 ///
120 /// $$
121 /// f(p, k) = p' \bmod 2^k.
122 /// $$
123 ///
124 /// The coefficient of $x^i$ is multiplied by $i$, reduced, and moved to $x^{i-1}$. Since $ia_i$
125 /// can be divisible by the modulus even when $a_i$ is not zero, the derivative can lose any
126 /// number of degrees. A constant polynomial, including zero, has derivative zero.
127 ///
128 /// # Worst-case complexity
129 /// $T(n) = O(n)$
130 ///
131 /// $M(n) = O(n)$
132 ///
133 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
134 ///
135 /// # Panics
136 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is greater than
137 /// or equal to $2^k$.
138 ///
139 /// # Examples
140 /// ```
141 /// use core::str::FromStr;
142 /// use malachite_base::polynomial::ModPowerOf2Derivative;
143 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
144 ///
145 /// let p = UnsignedPolynomial::<u8>::from_str("x^3+3*x^2+2*x+1").unwrap();
146 /// assert_eq!((&p).mod_power_of_2_derivative(2).to_string(), "3*x^2+2*x+2");
147 ///
148 /// let p = UnsignedPolynomial::<u8>::from_str("x^5+x").unwrap();
149 /// assert_eq!((&p).mod_power_of_2_derivative(1).to_string(), "x^4+1");
150 ///
151 /// // The derivative can lose more than one degree.
152 /// let p = UnsignedPolynomial::<u8>::from_str("x^4+x^3+1").unwrap();
153 /// assert_eq!((&p).mod_power_of_2_derivative(1).to_string(), "x^2");
154 /// ```
155 ///
156 /// This is equivalent to `nmod_poly_derivative` from `nmod_poly/derivative.c`, FLINT 3.6.0,
157 /// with the modulus $2^k$.
158 #[inline]
159 fn mod_power_of_2_derivative(self, pow: u64) -> UnsignedPolynomial<T> {
160 mod_power_of_2_derivative_ref(self, pow)
161 }
162}
163
164impl<T: PrimitiveUnsigned> ModPowerOf2DerivativeAssign for UnsignedPolynomial<T> {
165 /// Replaces an [`UnsignedPolynomial`] with its derivative modulo $2^k$, in place. The
166 /// coefficients must already be reduced modulo $2^k$.
167 ///
168 /// $$
169 /// p \gets p' \bmod 2^k.
170 /// $$
171 ///
172 /// The coefficient of $x^i$ is multiplied by $i$, reduced, and moved to $x^{i-1}$. Since $ia_i$
173 /// can be divisible by the modulus even when $a_i$ is not zero, the derivative can lose any
174 /// number of degrees. A constant polynomial, including zero, has derivative zero.
175 ///
176 /// # Worst-case complexity
177 /// $T(n) = O(n)$
178 ///
179 /// $M(n) = O(n)$
180 ///
181 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
182 ///
183 /// # Panics
184 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is greater than
185 /// or equal to $2^k$.
186 ///
187 /// # Examples
188 /// ```
189 /// use core::str::FromStr;
190 /// use malachite_base::polynomial::ModPowerOf2DerivativeAssign;
191 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
192 ///
193 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^3+3*x^2+2*x+1").unwrap();
194 /// p.mod_power_of_2_derivative_assign(2);
195 /// assert_eq!(p.to_string(), "3*x^2+2*x+2");
196 ///
197 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^5+x").unwrap();
198 /// p.mod_power_of_2_derivative_assign(1);
199 /// assert_eq!(p.to_string(), "x^4+1");
200 ///
201 /// // The derivative can lose more than one degree.
202 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^4+x^3+1").unwrap();
203 /// p.mod_power_of_2_derivative_assign(1);
204 /// assert_eq!(p.to_string(), "x^2");
205 /// ```
206 ///
207 /// This is equivalent to `nmod_poly_derivative` from `nmod_poly/derivative.c`, FLINT 3.6.0,
208 /// with the modulus $2^k$.
209 #[inline]
210 fn mod_power_of_2_derivative_assign(&mut self, pow: u64) {
211 mod_power_of_2_derivative_in_place(self, pow);
212 }
213}