malachite_base/unsigned_polynomial/arithmetic/mod_power_of_2_nth_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::num::conversion::traits::ExactFrom;
12use crate::polynomial::{ModPowerOf2NthDerivative, ModPowerOf2NthDerivativeAssign};
13use crate::unsigned_polynomial::UnsignedPolynomial;
14
15fn assert_reduced<T: PrimitiveUnsigned>(p: &UnsignedPolynomial<T>, pow: u64) {
16 assert!(pow <= T::WIDTH);
17 assert!(
18 p.mod_power_of_2_is_reduced(pow),
19 "self must be reduced mod 2^pow, but {p} has a coefficient >= 2^{pow}"
20 );
21}
22
23// Multiplies the coefficient of x^i, for i at least n, by the falling factorial i(i - 1)...(i - n +
24// 1) modulo 2^pow and moves it to x^(i - n). Each falling factorial is multiplied out from its n
25// factors with wrapping arithmetic, which loses nothing, since 2^pow divides 2^WIDTH. They are all
26// multiples of n!, so if 2^pow divides n!, which happens when n - n.count_ones() is at least pow,
27// the result is zero. The products can be zero, so the result is trimmed.
28fn mod_power_of_2_nth_derivative_in_place<T: PrimitiveUnsigned>(
29 p: &mut UnsignedPolynomial<T>,
30 n: u64,
31 pow: u64,
32) {
33 assert_reduced(p, pow);
34 if n == 0 {
35 return;
36 }
37 if u64::exact_from(p.coefficients.len()) <= n || n - u64::from(n.count_ones()) >= pow {
38 p.coefficients.clear();
39 return;
40 }
41 let mut top = T::wrapping_from(n);
42 p.coefficients.drain(..usize::exact_from(n));
43 for c in &mut p.coefficients {
44 let mut falling = T::ONE;
45 let mut factor = top;
46 for _ in 0..n {
47 falling.wrapping_mul_assign(factor);
48 factor.wrapping_sub_assign(T::ONE);
49 }
50 *c = c.wrapping_mul(falling).mod_power_of_2(pow);
51 top.wrapping_add_assign(T::ONE);
52 }
53 p.trim();
54}
55
56impl<T: PrimitiveUnsigned> ModPowerOf2NthDerivative for UnsignedPolynomial<T> {
57 type Output = Self;
58
59 /// Computes the $n$th derivative of an [`UnsignedPolynomial`] modulo $2^k$, taking the
60 /// polynomial by value. The coefficients must already be reduced modulo $2^k$.
61 ///
62 /// $$
63 /// f(p, n, k) = p^{(n)} \bmod 2^k.
64 /// $$
65 ///
66 /// The coefficient of $x^i$ is multiplied by the falling factorial $i^{\underline n} =
67 /// i(i-1)\cdots(i-n+1)$, reduced, and moved to $x^{i-n}$. The products can be zero even when
68 /// the coefficients are not, so the derivative can lose any number of degrees; if $2^k$ divides
69 /// $n!$, every falling factorial is a multiple of the modulus, and the result is zero.
70 ///
71 /// # Worst-case complexity
72 /// $T(k, n) = O(kn)$
73 ///
74 /// $M(k) = O(k)$
75 ///
76 /// where $T$ is time, $M$ is additional memory, $k$ is `self.len()`, and $n$ is `n`.
77 ///
78 /// # Panics
79 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is greater than
80 /// or equal to $2^k$.
81 ///
82 /// # Examples
83 /// ```
84 /// use core::str::FromStr;
85 /// use malachite_base::polynomial::ModPowerOf2NthDerivative;
86 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
87 ///
88 /// let p = UnsignedPolynomial::<u8>::from_str("x^4+3*x^3+2*x+5").unwrap();
89 /// assert_eq!(
90 /// p.clone().mod_power_of_2_nth_derivative(2, 3).to_string(),
91 /// "4*x^2+2*x"
92 /// );
93 /// assert_eq!(
94 /// p.mod_power_of_2_nth_derivative(0, 3).to_string(),
95 /// "x^4+3*x^3+2*x+5"
96 /// );
97 ///
98 /// // 2^3 divides 4!.
99 /// let p = UnsignedPolynomial::<u8>::from_str("x^5+x^4").unwrap();
100 /// assert_eq!(p.mod_power_of_2_nth_derivative(4, 3).to_string(), "0");
101 /// ```
102 ///
103 /// FLINT has no `nmod_poly_nth_derivative`; this computes the same multipliers as
104 /// `fmpz_poly_nth_derivative` from `fmpz_poly/nth_derivative.c`, FLINT 3.6.0, directly modulo
105 /// $2^k$.
106 #[inline]
107 fn mod_power_of_2_nth_derivative(mut self, n: u64, pow: u64) -> Self {
108 mod_power_of_2_nth_derivative_in_place(&mut self, n, pow);
109 self
110 }
111}
112
113impl<T: PrimitiveUnsigned> ModPowerOf2NthDerivative for &UnsignedPolynomial<T> {
114 type Output = UnsignedPolynomial<T>;
115
116 /// Computes the $n$th derivative of an [`UnsignedPolynomial`] modulo $2^k$, taking the
117 /// polynomial by reference. The coefficients must already be reduced modulo $2^k$.
118 ///
119 /// $$
120 /// f(p, n, k) = p^{(n)} \bmod 2^k.
121 /// $$
122 ///
123 /// The coefficient of $x^i$ is multiplied by the falling factorial $i^{\underline n} =
124 /// i(i-1)\cdots(i-n+1)$, reduced, and moved to $x^{i-n}$. The products can be zero even when
125 /// the coefficients are not, so the derivative can lose any number of degrees; if $2^k$ divides
126 /// $n!$, every falling factorial is a multiple of the modulus, and the result is zero.
127 ///
128 /// # Worst-case complexity
129 /// $T(k, n) = O(kn)$
130 ///
131 /// $M(k) = O(k)$
132 ///
133 /// where $T$ is time, $M$ is additional memory, $k$ is `self.len()`, and $n$ is `n`.
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::ModPowerOf2NthDerivative;
143 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
144 ///
145 /// let p = UnsignedPolynomial::<u8>::from_str("x^4+3*x^3+2*x+5").unwrap();
146 /// assert_eq!(
147 /// (&p).mod_power_of_2_nth_derivative(2, 3).to_string(),
148 /// "4*x^2+2*x"
149 /// );
150 /// assert_eq!(
151 /// (&p).mod_power_of_2_nth_derivative(0, 3).to_string(),
152 /// "x^4+3*x^3+2*x+5"
153 /// );
154 ///
155 /// // 2^3 divides 4!.
156 /// let p = UnsignedPolynomial::<u8>::from_str("x^5+x^4").unwrap();
157 /// assert_eq!((&p).mod_power_of_2_nth_derivative(4, 3).to_string(), "0");
158 /// ```
159 ///
160 /// FLINT has no `nmod_poly_nth_derivative`; this computes the same multipliers as
161 /// `fmpz_poly_nth_derivative` from `fmpz_poly/nth_derivative.c`, FLINT 3.6.0, directly modulo
162 /// $2^k$.
163 #[inline]
164 fn mod_power_of_2_nth_derivative(self, n: u64, pow: u64) -> UnsignedPolynomial<T> {
165 let mut p = self.clone();
166 mod_power_of_2_nth_derivative_in_place(&mut p, n, pow);
167 p
168 }
169}
170
171impl<T: PrimitiveUnsigned> ModPowerOf2NthDerivativeAssign for UnsignedPolynomial<T> {
172 /// Replaces an [`UnsignedPolynomial`] with its $n$th derivative modulo $2^k$, in place. The
173 /// coefficients must already be reduced modulo $2^k$.
174 ///
175 /// $$
176 /// p \gets p^{(n)} \bmod 2^k.
177 /// $$
178 ///
179 /// The coefficient of $x^i$ is multiplied by the falling factorial $i^{\underline n} =
180 /// i(i-1)\cdots(i-n+1)$, reduced, and moved to $x^{i-n}$. The products can be zero even when
181 /// the coefficients are not, so the derivative can lose any number of degrees; if $2^k$ divides
182 /// $n!$, every falling factorial is a multiple of the modulus, and the result is zero.
183 ///
184 /// # Worst-case complexity
185 /// $T(k, n) = O(kn)$
186 ///
187 /// $M(k) = O(k)$
188 ///
189 /// where $T$ is time, $M$ is additional memory, $k$ is `self.len()`, and $n$ is `n`.
190 ///
191 /// # Panics
192 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` is greater than
193 /// or equal to $2^k$.
194 ///
195 /// # Examples
196 /// ```
197 /// use core::str::FromStr;
198 /// use malachite_base::polynomial::ModPowerOf2NthDerivativeAssign;
199 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
200 ///
201 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^4+3*x^3+2*x+5").unwrap();
202 /// p.mod_power_of_2_nth_derivative_assign(2, 3);
203 /// assert_eq!(p.to_string(), "4*x^2+2*x");
204 ///
205 /// // 2^3 divides 4!.
206 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^5+x^4").unwrap();
207 /// p.mod_power_of_2_nth_derivative_assign(4, 3);
208 /// assert_eq!(p.to_string(), "0");
209 /// ```
210 ///
211 /// FLINT has no `nmod_poly_nth_derivative`; this computes the same multipliers as
212 /// `fmpz_poly_nth_derivative` from `fmpz_poly/nth_derivative.c`, FLINT 3.6.0, directly modulo
213 /// $2^k$.
214 #[inline]
215 fn mod_power_of_2_nth_derivative_assign(&mut self, n: u64, pow: u64) {
216 mod_power_of_2_nth_derivative_in_place(self, n, pow);
217 }
218}