malachite_nz/integer_polynomial/arithmetic/
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 alloc::vec::Vec;
12use malachite_base::polynomial::{Derivative, DerivativeAssign};
13
14// The coefficients of the derivative of the polynomial whose coefficients `xs` holds in ascending
15// order: the coefficient of x^i, for i at least 1, times i. The leading coefficient of a
16// nonconstant polynomial, times its degree, is nonzero, so the result is normalized.
17fn derivative_ref(xs: &[Integer]) -> Vec<Integer> {
18    xs.iter()
19        .enumerate()
20        .skip(1)
21        .map(|(i, c)| c * Integer::from(i))
22        .collect()
23}
24
25fn derivative_in_place(xs: &mut Vec<Integer>) {
26    if xs.is_empty() {
27        return;
28    }
29    xs.remove(0);
30    for (i, c) in xs.iter_mut().enumerate() {
31        *c *= Integer::from(i + 1);
32    }
33}
34
35impl Derivative for IntegerPolynomial {
36    type Output = Self;
37
38    /// Computes the derivative of an [`IntegerPolynomial`], taking it by value.
39    ///
40    /// $$
41    /// f(p) = p' = \sum_{i=1}^n ia_ix^{i-1}.
42    /// $$
43    ///
44    /// The coefficient of $x^i$ is multiplied by $i$ and moves to $x^{i-1}$. A constant polynomial,
45    /// including zero, has derivative zero.
46    ///
47    /// # Worst-case complexity
48    /// $T(n, m) = O(n + m \log m)$
49    ///
50    /// $M(n, m) = O(n + m \log m)$
51    ///
52    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
53    /// coefficients, and $m$ is `self.len()`.
54    ///
55    /// # Examples
56    /// ```
57    /// use core::str::FromStr;
58    /// use malachite_base::num::basic::traits::Zero;
59    /// use malachite_base::polynomial::Derivative;
60    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
61    ///
62    /// let p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
63    /// assert_eq!(p.derivative().to_string(), "3*x^2-6*x+2");
64    ///
65    /// let p = IntegerPolynomial::from_str("7").unwrap();
66    /// assert_eq!(p.derivative(), IntegerPolynomial::ZERO);
67    /// ```
68    ///
69    /// This is equivalent to `fmpz_poly_derivative` from `fmpz_poly/derivative.c`, FLINT 3.6.0.
70    #[inline]
71    fn derivative(mut self) -> Self {
72        self.derivative_assign();
73        self
74    }
75}
76
77impl Derivative for &IntegerPolynomial {
78    type Output = IntegerPolynomial;
79
80    /// Computes the derivative of an [`IntegerPolynomial`], taking it by reference.
81    ///
82    /// $$
83    /// f(p) = p' = \sum_{i=1}^n ia_ix^{i-1}.
84    /// $$
85    ///
86    /// The coefficient of $x^i$ is multiplied by $i$ and moves to $x^{i-1}$. A constant polynomial,
87    /// including zero, has derivative zero.
88    ///
89    /// # Worst-case complexity
90    /// $T(n, m) = O(n + m \log m)$
91    ///
92    /// $M(n, m) = O(n + m \log m)$
93    ///
94    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
95    /// coefficients, and $m$ is `self.len()`.
96    ///
97    /// # Examples
98    /// ```
99    /// use core::str::FromStr;
100    /// use malachite_base::num::basic::traits::Zero;
101    /// use malachite_base::polynomial::Derivative;
102    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
103    ///
104    /// let p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
105    /// assert_eq!((&p).derivative().to_string(), "3*x^2-6*x+2");
106    ///
107    /// let p = IntegerPolynomial::from_str("7").unwrap();
108    /// assert_eq!((&p).derivative(), IntegerPolynomial::ZERO);
109    /// ```
110    ///
111    /// This is equivalent to `fmpz_poly_derivative` from `fmpz_poly/derivative.c`, FLINT 3.6.0.
112    #[inline]
113    fn derivative(self) -> IntegerPolynomial {
114        IntegerPolynomial {
115            coefficients: derivative_ref(&self.coefficients),
116        }
117    }
118}
119
120impl DerivativeAssign for IntegerPolynomial {
121    /// Replaces an [`IntegerPolynomial`] with its derivative.
122    ///
123    /// $$
124    /// p \gets p' = \sum_{i=1}^n ia_ix^{i-1}.
125    /// $$
126    ///
127    /// The coefficient of $x^i$ is multiplied by $i$ and moves to $x^{i-1}$. A constant polynomial,
128    /// including zero, has derivative zero.
129    ///
130    /// # Worst-case complexity
131    /// $T(n, m) = O(n + m \log m)$
132    ///
133    /// $M(n, m) = O(n + m \log m)$
134    ///
135    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
136    /// coefficients, and $m$ is `self.len()`.
137    ///
138    /// # Examples
139    /// ```
140    /// use core::str::FromStr;
141    /// use malachite_base::num::basic::traits::Zero;
142    /// use malachite_base::polynomial::DerivativeAssign;
143    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
144    ///
145    /// let mut p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
146    /// p.derivative_assign();
147    /// assert_eq!(p.to_string(), "3*x^2-6*x+2");
148    ///
149    /// let mut p = IntegerPolynomial::from_str("7").unwrap();
150    /// p.derivative_assign();
151    /// assert_eq!(p, IntegerPolynomial::ZERO);
152    /// ```
153    ///
154    /// This is equivalent to `fmpz_poly_derivative` from `fmpz_poly/derivative.c`, FLINT 3.6.0.
155    #[inline]
156    fn derivative_assign(&mut self) {
157        derivative_in_place(&mut self.coefficients);
158    }
159}
malachite_nz/integer_polynomial/arithmetic/derivative.rs

malachite_nz/integer_polynomial/arithmetic/
derivative.rs
