malachite_nz/integer_polynomial/arithmetic/compose_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::Integer;
10use crate::integer_polynomial::IntegerPolynomial;
11use alloc::vec;
12use alloc::vec::Vec;
13use malachite_base::num::basic::traits::Zero;
14use malachite_base::num::conversion::traits::ExactFrom;
15use malachite_base::polynomial::{ComposePowerOfX, ComposePowerOfXAssign, Polynomial};
16
17// The value at 1, the sum of the coefficients.
18fn sum_of_coefficients(coefficients: &[Integer]) -> Integer {
19 coefficients.iter().sum()
20}
21
22// Moves the coefficient of x^i to x^(ik), in place, for k at least 2. The vector is first extended
23// with zeros to the final length; then the coefficients are moved from the top down, so each lands
24// on a place that is already zero. The leading coefficient stays nonzero.
25fn spread(coefficients: &mut Vec<Integer>, k: u64) {
26 let len = coefficients.len();
27 if len <= 1 {
28 return;
29 }
30 let k = usize::exact_from(k);
31 let new_len = (len - 1)
32 .checked_mul(k)
33 .and_then(|n| n.checked_add(1))
34 .unwrap();
35 coefficients.resize(new_len, Integer::ZERO);
36 for i in (1..len).rev() {
37 coefficients.swap(i, i * k);
38 }
39}
40
41impl ComposePowerOfX for IntegerPolynomial {
42 type Output = Self;
43
44 /// Composes an [`IntegerPolynomial`] with $x^k$, giving $p(x^k)$, taking it by value. The
45 /// coefficient of $x^i$ moves to $x^{ik}$, and zeros fill the places in between.
46 ///
47 /// $$
48 /// f(p, k) = p(x^k).
49 /// $$
50 ///
51 /// When $k$ is 0 the result is the constant $p(1)$, the sum of the coefficients; when $k$ is 1,
52 /// or the polynomial is constant, nothing changes.
53 ///
54 /// # Worst-case complexity
55 /// $T(m, k) = O(mk)$
56 ///
57 /// $M(m, k) = O(mk)$
58 ///
59 /// where $T$ is time, $M$ is additional memory, $k$ is `k`, and $m$ is the total number of bits
60 /// of the coefficients.
61 ///
62 /// # Panics
63 /// Panics if the degree of the result is greater than `usize::MAX`.
64 ///
65 /// # Examples
66 /// ```
67 /// use core::str::FromStr;
68 /// use malachite_base::polynomial::ComposePowerOfX;
69 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
70 ///
71 /// let p = IntegerPolynomial::from_str("x^2-3*x+2").unwrap();
72 /// assert_eq!(p.compose_power_of_x(2).to_string(), "x^4-3*x^2+2");
73 /// // With k = 0, this is p(1).
74 /// let p = IntegerPolynomial::from_str("x^2-3*x+2").unwrap();
75 /// assert_eq!(p.compose_power_of_x(0).to_string(), "0");
76 /// ```
77 ///
78 /// This is equivalent to `fmpz_poly_inflate` from `fmpz_poly/inflate.c`, FLINT 3.6.0.
79 #[inline]
80 fn compose_power_of_x(mut self, k: u64) -> Self {
81 self.compose_power_of_x_assign(k);
82 self
83 }
84}
85
86impl ComposePowerOfX for &IntegerPolynomial {
87 type Output = IntegerPolynomial;
88
89 /// Composes an [`IntegerPolynomial`] with $x^k$, giving $p(x^k)$, taking it by reference. The
90 /// coefficient of $x^i$ moves to $x^{ik}$, and zeros fill the places in between.
91 ///
92 /// $$
93 /// f(p, k) = p(x^k).
94 /// $$
95 ///
96 /// When $k$ is 0 the result is the constant $p(1)$, the sum of the coefficients; when $k$ is 1,
97 /// or the polynomial is constant, nothing changes.
98 ///
99 /// # Worst-case complexity
100 /// $T(m, k) = O(mk)$
101 ///
102 /// $M(m, k) = O(mk)$
103 ///
104 /// where $T$ is time, $M$ is additional memory, $k$ is `k`, and $m$ is the total number of bits
105 /// of the coefficients.
106 ///
107 /// # Panics
108 /// Panics if the degree of the result is greater than `usize::MAX`.
109 ///
110 /// # Examples
111 /// ```
112 /// use core::str::FromStr;
113 /// use malachite_base::polynomial::ComposePowerOfX;
114 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
115 ///
116 /// let p = IntegerPolynomial::from_str("x^2-3*x+2").unwrap();
117 /// assert_eq!((&p).compose_power_of_x(2).to_string(), "x^4-3*x^2+2");
118 /// // With k = 0, this is p(1).
119 /// let p = IntegerPolynomial::from_str("x^2-3*x+2").unwrap();
120 /// assert_eq!((&p).compose_power_of_x(0).to_string(), "0");
121 /// ```
122 ///
123 /// This is equivalent to `fmpz_poly_inflate` from `fmpz_poly/inflate.c`, FLINT 3.6.0.
124 fn compose_power_of_x(self, k: u64) -> IntegerPolynomial {
125 if k == 0 {
126 return IntegerPolynomial::from_coefficients_asc(vec![sum_of_coefficients(
127 &self.coefficients,
128 )]);
129 }
130 let mut coefficients = self.coefficients.clone();
131 if k != 1 {
132 spread(&mut coefficients, k);
133 }
134 IntegerPolynomial { coefficients }
135 }
136}
137
138impl ComposePowerOfXAssign for IntegerPolynomial {
139 /// Composes an [`IntegerPolynomial`] with $x^k$ in place, replacing $p$ with $p(x^k)$. The
140 /// coefficient of $x^i$ moves to $x^{ik}$, and zeros fill the places in between.
141 ///
142 /// $$
143 /// p \gets p(x^k).
144 /// $$
145 ///
146 /// When $k$ is 0 the result is the constant $p(1)$, the sum of the coefficients; when $k$ is 1,
147 /// or the polynomial is constant, nothing changes.
148 ///
149 /// # Worst-case complexity
150 /// $T(m, k) = O(mk)$
151 ///
152 /// $M(m, k) = O(mk)$
153 ///
154 /// where $T$ is time, $M$ is additional memory, $k$ is `k`, and $m$ is the total number of bits
155 /// of the coefficients.
156 ///
157 /// # Panics
158 /// Panics if the degree of the result is greater than `usize::MAX`.
159 ///
160 /// # Examples
161 /// ```
162 /// use core::str::FromStr;
163 /// use malachite_base::polynomial::ComposePowerOfXAssign;
164 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
165 ///
166 /// let mut p = IntegerPolynomial::from_str("x^2-3*x+2").unwrap();
167 /// p.compose_power_of_x_assign(2);
168 /// assert_eq!(p.to_string(), "x^4-3*x^2+2");
169 ///
170 /// // With k = 0, this is p(1).
171 /// let mut p = IntegerPolynomial::from_str("x^2-3*x+2").unwrap();
172 /// p.compose_power_of_x_assign(0);
173 /// assert_eq!(p.to_string(), "0");
174 /// ```
175 ///
176 /// This is equivalent to `fmpz_poly_inflate` from `fmpz_poly/inflate.c`, FLINT 3.6.0.
177 fn compose_power_of_x_assign(&mut self, k: u64) {
178 match k {
179 0 => {
180 *self = Self::from_coefficients_asc(vec![sum_of_coefficients(&self.coefficients)]);
181 }
182 1 => {}
183 _ => spread(&mut self.coefficients, k),
184 }
185 }
186}