malachite_nz/integer_polynomial/arithmetic/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::integer::Integer;
10use crate::integer_polynomial::IntegerPolynomial;
11use crate::natural::Natural;
12use alloc::vec::Vec;
13use malachite_base::num::arithmetic::traits::{DivExactAssign, Factorial};
14use malachite_base::num::conversion::traits::ExactFrom;
15use malachite_base::polynomial::{NthDerivative, NthDerivativeAssign};
16
17// The falling factorials i(i - 1)...(i - n + 1), for i from n: the first is n!, and each is carried
18// to the next by dividing exactly by i - n and multiplying by i, both of which are small.
19fn falling_factorials(n: usize) -> impl FnMut(usize) -> Integer {
20 let mut f = Integer::from(Natural::factorial(u64::exact_from(n)));
21 move |i| {
22 if i > n {
23 f.div_exact_assign(Integer::from(i - n));
24 f *= Integer::from(i);
25 }
26 f.clone()
27 }
28}
29
30// The coefficients of the nth derivative, for n at least 1 and less than `xs.len()`: the
31// coefficient of x^i, for i at least n, times i(i - 1)...(i - n + 1), moved to x^(i - n). The
32// leading coefficient times its falling factorial is nonzero, so the result is normalized.
33//
34// This is equivalent to `_fmpz_poly_nth_derivative` from `fmpz_poly/nth_derivative.c`, FLINT 3.6.0.
35fn nth_derivative_ref(xs: &[Integer], n: usize) -> Vec<Integer> {
36 let mut falling = falling_factorials(n);
37 xs.iter()
38 .enumerate()
39 .skip(n)
40 .map(|(i, c)| c * falling(i))
41 .collect()
42}
43
44fn nth_derivative_in_place(xs: &mut Vec<Integer>, n: u64) {
45 if n == 0 {
46 return;
47 }
48 if u64::exact_from(xs.len()) <= n {
49 xs.clear();
50 return;
51 }
52 let n = usize::exact_from(n);
53 xs.drain(..n);
54 let mut falling = falling_factorials(n);
55 for (j, c) in xs.iter_mut().enumerate() {
56 *c *= falling(j + n);
57 }
58}
59
60impl NthDerivative for IntegerPolynomial {
61 type Output = Self;
62
63 /// Computes the $n$th derivative of an [`IntegerPolynomial`], taking it by value.
64 ///
65 /// $$
66 /// f(p, n) = p^{(n)} = \sum_{i=n}^d i^{\underline n}a_ix^{i-n}.
67 /// $$
68 ///
69 /// Here $i^{\underline n} = i(i-1)\cdots(i-n+1)$ is a falling factorial, and $d$ is the degree.
70 /// The zeroth derivative is the polynomial itself, and a polynomial of degree less than $n$ has
71 /// $n$th derivative zero.
72 ///
73 /// # Worst-case complexity
74 /// $T(b, k) = O(k(b + k \log k))$
75 ///
76 /// $M(b, k) = O(b + k^2 \log k)$
77 ///
78 /// where $T$ is time, $M$ is additional memory, $b$ is the total number of bits of the
79 /// coefficients, and $k$ is `self.len()`.
80 ///
81 /// # Examples
82 /// ```
83 /// use core::str::FromStr;
84 /// use malachite_base::num::basic::traits::Zero;
85 /// use malachite_base::polynomial::NthDerivative;
86 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
87 ///
88 /// let p = IntegerPolynomial::from_str("x^4-3*x^3+2*x-5").unwrap();
89 /// assert_eq!(p.clone().nth_derivative(2).to_string(), "12*x^2-18*x");
90 /// assert_eq!(p.clone().nth_derivative(0).to_string(), "x^4-3*x^3+2*x-5");
91 /// assert_eq!(p.nth_derivative(5), IntegerPolynomial::ZERO);
92 /// ```
93 ///
94 /// This is equivalent to `fmpz_poly_nth_derivative` from `fmpz_poly/nth_derivative.c`, FLINT
95 /// 3.6.0.
96 #[inline]
97 fn nth_derivative(mut self, n: u64) -> Self {
98 self.nth_derivative_assign(n);
99 self
100 }
101}
102
103impl NthDerivative for &IntegerPolynomial {
104 type Output = IntegerPolynomial;
105
106 /// Computes the $n$th derivative of an [`IntegerPolynomial`], taking it by reference.
107 ///
108 /// $$
109 /// f(p, n) = p^{(n)} = \sum_{i=n}^d i^{\underline n}a_ix^{i-n}.
110 /// $$
111 ///
112 /// Here $i^{\underline n} = i(i-1)\cdots(i-n+1)$ is a falling factorial, and $d$ is the degree.
113 /// The zeroth derivative is the polynomial itself, and a polynomial of degree less than $n$ has
114 /// $n$th derivative zero.
115 ///
116 /// # Worst-case complexity
117 /// $T(b, k) = O(k(b + k \log k))$
118 ///
119 /// $M(b, k) = O(b + k^2 \log k)$
120 ///
121 /// where $T$ is time, $M$ is additional memory, $b$ is the total number of bits of the
122 /// coefficients, and $k$ is `self.len()`.
123 ///
124 /// # Examples
125 /// ```
126 /// use core::str::FromStr;
127 /// use malachite_base::num::basic::traits::Zero;
128 /// use malachite_base::polynomial::NthDerivative;
129 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
130 ///
131 /// let p = IntegerPolynomial::from_str("x^4-3*x^3+2*x-5").unwrap();
132 /// assert_eq!((&p).nth_derivative(2).to_string(), "12*x^2-18*x");
133 /// assert_eq!((&p).nth_derivative(0).to_string(), "x^4-3*x^3+2*x-5");
134 /// assert_eq!((&p).nth_derivative(5), IntegerPolynomial::ZERO);
135 /// ```
136 ///
137 /// This is equivalent to `fmpz_poly_nth_derivative` from `fmpz_poly/nth_derivative.c`, FLINT
138 /// 3.6.0.
139 fn nth_derivative(self, n: u64) -> IntegerPolynomial {
140 if n == 0 {
141 return self.clone();
142 }
143 if u64::exact_from(self.coefficients.len()) <= n {
144 return IntegerPolynomial {
145 coefficients: Vec::new(),
146 };
147 }
148 IntegerPolynomial {
149 coefficients: nth_derivative_ref(&self.coefficients, usize::exact_from(n)),
150 }
151 }
152}
153
154impl NthDerivativeAssign for IntegerPolynomial {
155 /// Replaces an [`IntegerPolynomial`] with its $n$th derivative.
156 ///
157 /// $$
158 /// p \gets p^{(n)} = \sum_{i=n}^d i^{\underline n}a_ix^{i-n}.
159 /// $$
160 ///
161 /// Here $i^{\underline n} = i(i-1)\cdots(i-n+1)$ is a falling factorial, and $d$ is the degree.
162 /// The zeroth derivative is the polynomial itself, and a polynomial of degree less than $n$ has
163 /// $n$th derivative zero.
164 ///
165 /// # Worst-case complexity
166 /// $T(b, k) = O(k(b + k \log k))$
167 ///
168 /// $M(b, k) = O(b + k^2 \log k)$
169 ///
170 /// where $T$ is time, $M$ is additional memory, $b$ is the total number of bits of the
171 /// coefficients, and $k$ is `self.len()`.
172 ///
173 /// # Examples
174 /// ```
175 /// use core::str::FromStr;
176 /// use malachite_base::num::basic::traits::Zero;
177 /// use malachite_base::polynomial::NthDerivativeAssign;
178 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
179 ///
180 /// let mut p = IntegerPolynomial::from_str("x^4-3*x^3+2*x-5").unwrap();
181 /// p.nth_derivative_assign(2);
182 /// assert_eq!(p.to_string(), "12*x^2-18*x");
183 ///
184 /// let mut p = IntegerPolynomial::from_str("x^4-3*x^3+2*x-5").unwrap();
185 /// p.nth_derivative_assign(0);
186 /// assert_eq!(p.to_string(), "x^4-3*x^3+2*x-5");
187 ///
188 /// let mut p = IntegerPolynomial::from_str("x^4-3*x^3+2*x-5").unwrap();
189 /// p.nth_derivative_assign(5);
190 /// assert_eq!(p, IntegerPolynomial::ZERO);
191 /// ```
192 ///
193 /// This is equivalent to `fmpz_poly_nth_derivative` from `fmpz_poly/nth_derivative.c`, FLINT
194 /// 3.6.0.
195 #[inline]
196 fn nth_derivative_assign(&mut self, n: u64) {
197 nth_derivative_in_place(&mut self.coefficients, n);
198 }
199}