malachite_base/unsigned_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::num::basic::unsigneds::PrimitiveUnsigned;
10use crate::polynomial::{
11    DeflatePowerOfX, DeflatePowerOfXAssign, slice_deflate_power_of_x, vec_deflate_power_of_x,
12};
13use crate::unsigned_polynomial::UnsignedPolynomial;
14
15impl<T: PrimitiveUnsigned> DeflatePowerOfX for UnsignedPolynomial<T> {
16    type Output = Self;
17
18    /// Deflates an [`UnsignedPolynomial`] by $n$, taking it by value, giving the polynomial $q$
19    /// with $q(x^n) = p(x)$. The coefficient of $x^{in}$ moves to $x^i$.
20    ///
21    /// $$
22    /// f(p, n) = q, \quad \text{where} \quad q(x^n) = p(x).
23    /// $$
24    ///
25    /// A constant polynomial deflates to itself, and deflating by 1 changes nothing.
26    ///
27    /// # Worst-case complexity
28    /// $T(m) = O(m)$
29    ///
30    /// $M(m) = O(1)$
31    ///
32    /// where $T$ is time, $M$ is additional memory, and $m$ is `self.len()`.
33    ///
34    /// # Panics
35    /// Panics if `n` is 0, or if the polynomial has a nonzero coefficient at an exponent that is
36    /// not a multiple of `n`.
37    ///
38    /// # Examples
39    /// ```
40    /// use core::str::FromStr;
41    /// use malachite_base::polynomial::DeflatePowerOfX;
42    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
43    ///
44    /// let p = UnsignedPolynomial::<u8>::from_str("x^6+2*x^3+1").unwrap();
45    /// assert_eq!(p.deflate_power_of_x(3).to_string(), "x^2+2*x+1");
46    /// ```
47    ///
48    /// This is equivalent to `nmod_poly_deflate` from `nmod_poly/deflate.c`, FLINT 3.6.0, except
49    /// that it panics rather than dropping the coefficients at other exponents.
50    #[inline]
51    fn deflate_power_of_x(mut self, n: u64) -> Self {
52        self.deflate_power_of_x_assign(n);
53        self
54    }
55}
56
57impl<T: PrimitiveUnsigned> DeflatePowerOfX for &UnsignedPolynomial<T> {
58    type Output = UnsignedPolynomial<T>;
59
60    /// Deflates an [`UnsignedPolynomial`] by $n$, taking it by reference, giving the polynomial $q$
61    /// with $q(x^n) = p(x)$. The coefficient of $x^{in}$ moves to $x^i$.
62    ///
63    /// $$
64    /// f(p, n) = q, \quad \text{where} \quad q(x^n) = p(x).
65    /// $$
66    ///
67    /// A constant polynomial deflates to itself, and deflating by 1 changes nothing.
68    ///
69    /// # Worst-case complexity
70    /// $T(m) = O(m)$
71    ///
72    /// $M(m) = O(m)$
73    ///
74    /// where $T$ is time, $M$ is additional memory, and $m$ is `self.len()`.
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_base::unsigned_polynomial::UnsignedPolynomial;
85    ///
86    /// let p = UnsignedPolynomial::<u8>::from_str("x^6+2*x^3+1").unwrap();
87    /// assert_eq!((&p).deflate_power_of_x(3).to_string(), "x^2+2*x+1");
88    /// ```
89    ///
90    /// This is equivalent to `nmod_poly_deflate` from `nmod_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) -> UnsignedPolynomial<T> {
94        UnsignedPolynomial {
95            coefficients: slice_deflate_power_of_x(&self.coefficients, n, |c| *c == T::ZERO),
96        }
97    }
98}
99
100impl<T: PrimitiveUnsigned> DeflatePowerOfXAssign for UnsignedPolynomial<T> {
101    /// Deflates an [`UnsignedPolynomial`] 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_base::unsigned_polynomial::UnsignedPolynomial;
126    ///
127    /// let mut p = UnsignedPolynomial::<u8>::from_str("x^6+2*x^3+1").unwrap();
128    /// p.deflate_power_of_x_assign(3);
129    /// assert_eq!(p.to_string(), "x^2+2*x+1");
130    /// ```
131    ///
132    /// This is equivalent to `nmod_poly_deflate` from `nmod_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 == T::ZERO);
137    }
138}
malachite_base/unsigned_polynomial/arithmetic/deflate_power_of_x.rs

malachite_base/unsigned_polynomial/arithmetic/
deflate_power_of_x.rs
