malachite_nz/integer_polynomial/arithmetic/
deflate_power_of_x.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_polynomial::IntegerPolynomial;
10use malachite_base::polynomial::{
11    DeflatePowerOfX, DeflatePowerOfXAssign, slice_deflate_power_of_x, vec_deflate_power_of_x,
12};
13
14impl DeflatePowerOfX for IntegerPolynomial {
15    type Output = Self;
16
17    /// Deflates an [`IntegerPolynomial`] by $n$, taking it by value, giving the polynomial $q$ with
18    /// $q(x^n) = p(x)$. The coefficient of $x^{in}$ moves to $x^i$.
19    ///
20    /// $$
21    /// f(p, n) = q, \quad \text{where} \quad q(x^n) = p(x).
22    /// $$
23    ///
24    /// A constant polynomial deflates to itself, and deflating by 1 changes nothing.
25    ///
26    /// # Worst-case complexity
27    /// $T(m) = O(m)$
28    ///
29    /// $M(m) = O(1)$
30    ///
31    /// where $T$ is time, $M$ is additional memory, and $m$ is `self.len()`.
32    ///
33    /// # Panics
34    /// Panics if `n` is 0, or if the polynomial has a nonzero coefficient at an exponent that is
35    /// not a multiple of `n`.
36    ///
37    /// # Examples
38    /// ```
39    /// use core::str::FromStr;
40    /// use malachite_base::polynomial::DeflatePowerOfX;
41    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
42    ///
43    /// let p = IntegerPolynomial::from_str("x^4-3*x^2+2").unwrap();
44    /// assert_eq!(p.deflate_power_of_x(2).to_string(), "x^2-3*x+2");
45    /// ```
46    ///
47    /// This is equivalent to `fmpz_poly_deflate` from `fmpz_poly/deflate.c`, FLINT 3.6.0, except
48    /// that it panics rather than dropping the coefficients at other exponents.
49    #[inline]
50    fn deflate_power_of_x(mut self, n: u64) -> Self {
51        self.deflate_power_of_x_assign(n);
52        self
53    }
54}
55
56impl DeflatePowerOfX for &IntegerPolynomial {
57    type Output = IntegerPolynomial;
58
59    /// Deflates an [`IntegerPolynomial`] by $n$, taking it by reference, giving the polynomial $q$
60    /// with $q(x^n) = p(x)$. The coefficient of $x^{in}$ moves to $x^i$.
61    ///
62    /// $$
63    /// f(p, n) = q, \quad \text{where} \quad q(x^n) = p(x).
64    /// $$
65    ///
66    /// A constant polynomial deflates to itself, and deflating by 1 changes nothing.
67    ///
68    /// # Worst-case complexity
69    /// $T(m) = O(m)$
70    ///
71    /// $M(m) = O(m)$
72    ///
73    /// where $T$ is time, $M$ is additional memory, and $m$ is the total number of bits of the
74    /// coefficients.
75    ///
76    /// # Panics
77    /// Panics if `n` is 0, or if the polynomial has a nonzero coefficient at an exponent that is
78    /// not a multiple of `n`.
79    ///
80    /// # Examples
81    /// ```
82    /// use core::str::FromStr;
83    /// use malachite_base::polynomial::DeflatePowerOfX;
84    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
85    ///
86    /// let p = IntegerPolynomial::from_str("x^4-3*x^2+2").unwrap();
87    /// assert_eq!((&p).deflate_power_of_x(2).to_string(), "x^2-3*x+2");
88    /// ```
89    ///
90    /// This is equivalent to `fmpz_poly_deflate` from `fmpz_poly/deflate.c`, FLINT 3.6.0, except
91    /// that it panics rather than dropping the coefficients at other exponents.
92    #[inline]
93    fn deflate_power_of_x(self, n: u64) -> IntegerPolynomial {
94        IntegerPolynomial {
95            coefficients: slice_deflate_power_of_x(&self.coefficients, n, |c| *c == 0u32),
96        }
97    }
98}
99
100impl DeflatePowerOfXAssign for IntegerPolynomial {
101    /// Deflates an [`IntegerPolynomial`] by $n$ in place, replacing $p$ with the polynomial $q$
102    /// such that $q(x^n) = p(x)$. The coefficient of $x^{in}$ moves to $x^i$.
103    ///
104    /// $$
105    /// p \gets q, \quad \text{where} \quad q(x^n) = p(x).
106    /// $$
107    ///
108    /// A constant polynomial deflates to itself, and deflating by 1 changes nothing.
109    ///
110    /// # Worst-case complexity
111    /// $T(m) = O(m)$
112    ///
113    /// $M(m) = O(1)$
114    ///
115    /// where $T$ is time, $M$ is additional memory, and $m$ is `self.len()`.
116    ///
117    /// # Panics
118    /// Panics if `n` is 0, or if the polynomial has a nonzero coefficient at an exponent that is
119    /// not a multiple of `n`.
120    ///
121    /// # Examples
122    /// ```
123    /// use core::str::FromStr;
124    /// use malachite_base::polynomial::DeflatePowerOfXAssign;
125    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
126    ///
127    /// let mut p = IntegerPolynomial::from_str("x^4-3*x^2+2").unwrap();
128    /// p.deflate_power_of_x_assign(2);
129    /// assert_eq!(p.to_string(), "x^2-3*x+2");
130    /// ```
131    ///
132    /// This is equivalent to `fmpz_poly_deflate` from `fmpz_poly/deflate.c`, FLINT 3.6.0, except
133    /// that it panics rather than dropping the coefficients at other exponents.
134    #[inline]
135    fn deflate_power_of_x_assign(&mut self, n: u64) {
136        vec_deflate_power_of_x(&mut self.coefficients, n, |c| *c == 0u32);
137    }
138}
malachite_nz/integer_polynomial/arithmetic/deflate_power_of_x.rs

malachite_nz/integer_polynomial/arithmetic/
deflate_power_of_x.rs
