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