malachite_base/unsigned_polynomial/arithmetic/mul_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::traits::Zero;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::num::conversion::traits::ExactFrom;
12use crate::polynomial::{MulPowerOfX, MulPowerOfXAssign};
13use crate::unsigned_polynomial::UnsignedPolynomial;
14use alloc::vec::Vec;
15use core::iter::repeat_n;
16
17impl<T: PrimitiveUnsigned> MulPowerOfX for UnsignedPolynomial<T> {
18 type Output = Self;
19
20 /// Multiplies an [`UnsignedPolynomial`] by $x^n$, taking it by value. Every coefficient moves
21 /// up by $n$ places, and $n$ zeros fill the places below them.
22 ///
23 /// $$
24 /// f(p, n) = x^np.
25 /// $$
26 ///
27 /// The zero polynomial stays zero, and multiplying by $x^0$ changes nothing.
28 ///
29 /// # Worst-case complexity
30 /// $T(n, m) = O(n + m)$
31 ///
32 /// $M(n, m) = O(1)$
33 ///
34 /// where $T$ is time, $M$ is additional memory, $n$ is `n`, and $m$ is `self.len()`.
35 ///
36 /// # Panics
37 /// Panics if the polynomial is nonzero and `n` is greater than `usize::MAX`.
38 ///
39 /// # Examples
40 /// ```
41 /// use core::str::FromStr;
42 /// use malachite_base::num::basic::traits::Zero;
43 /// use malachite_base::polynomial::MulPowerOfX;
44 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
45 ///
46 /// assert_eq!(
47 /// UnsignedPolynomial::<u8>::from_str("x^2+3*x+2")
48 /// .unwrap()
49 /// .mul_power_of_x(2)
50 /// .to_string(),
51 /// "x^4+3*x^3+2*x^2"
52 /// );
53 /// assert_eq!(
54 /// UnsignedPolynomial::<u8>::from_str("5")
55 /// .unwrap()
56 /// .mul_power_of_x(1)
57 /// .to_string(),
58 /// "5*x"
59 /// );
60 /// assert_eq!(
61 /// UnsignedPolynomial::<u8>::ZERO.mul_power_of_x(3),
62 /// UnsignedPolynomial::<u8>::ZERO
63 /// );
64 /// ```
65 ///
66 /// This is equivalent to `nmod_poly_shift_left` from `nmod_poly/shift_left.c`, FLINT 3.6.0.
67 #[inline]
68 fn mul_power_of_x(mut self, n: u64) -> Self {
69 self.mul_power_of_x_assign(n);
70 self
71 }
72}
73
74impl<T: PrimitiveUnsigned> MulPowerOfX for &UnsignedPolynomial<T> {
75 type Output = UnsignedPolynomial<T>;
76
77 /// Multiplies an [`UnsignedPolynomial`] by $x^n$, taking it by reference. Every coefficient
78 /// moves up by $n$ places, and $n$ zeros fill the places below them.
79 ///
80 /// $$
81 /// f(p, n) = x^np.
82 /// $$
83 ///
84 /// The zero polynomial stays zero, and multiplying by $x^0$ changes nothing.
85 ///
86 /// # Worst-case complexity
87 /// $T(n, m) = O(n + m)$
88 ///
89 /// $M(n, m) = O(n + m)$
90 ///
91 /// where $T$ is time, $M$ is additional memory, $n$ is `n`, and $m$ is `self.len()`.
92 ///
93 /// # Panics
94 /// Panics if the polynomial is nonzero and `n` is greater than `usize::MAX`.
95 ///
96 /// # Examples
97 /// ```
98 /// use core::str::FromStr;
99 /// use malachite_base::num::basic::traits::Zero;
100 /// use malachite_base::polynomial::MulPowerOfX;
101 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
102 ///
103 /// assert_eq!(
104 /// (&UnsignedPolynomial::<u8>::from_str("x^2+3*x+2").unwrap())
105 /// .mul_power_of_x(2)
106 /// .to_string(),
107 /// "x^4+3*x^3+2*x^2"
108 /// );
109 /// assert_eq!(
110 /// (&UnsignedPolynomial::<u8>::from_str("5").unwrap())
111 /// .mul_power_of_x(1)
112 /// .to_string(),
113 /// "5*x"
114 /// );
115 /// assert_eq!(
116 /// (&UnsignedPolynomial::<u8>::ZERO).mul_power_of_x(3),
117 /// UnsignedPolynomial::<u8>::ZERO
118 /// );
119 /// ```
120 ///
121 /// This is equivalent to `nmod_poly_shift_left` from `nmod_poly/shift_left.c`, FLINT 3.6.0.
122 fn mul_power_of_x(self, n: u64) -> UnsignedPolynomial<T> {
123 if self.coefficients.is_empty() {
124 return UnsignedPolynomial::ZERO;
125 }
126 let n = usize::exact_from(n);
127 let mut coefficients = Vec::with_capacity(n + self.coefficients.len());
128 coefficients.extend(repeat_n(T::ZERO, n));
129 coefficients.extend_from_slice(&self.coefficients);
130 UnsignedPolynomial { coefficients }
131 }
132}
133
134impl<T: PrimitiveUnsigned> MulPowerOfXAssign for UnsignedPolynomial<T> {
135 /// Multiplies an [`UnsignedPolynomial`] by $x^n$ in place. Every coefficient moves up by $n$
136 /// places, and $n$ zeros fill the places below them.
137 ///
138 /// $$
139 /// p \gets x^np.
140 /// $$
141 ///
142 /// The zero polynomial stays zero, and multiplying by $x^0$ changes nothing.
143 ///
144 /// # Worst-case complexity
145 /// $T(n, m) = O(n + m)$
146 ///
147 /// $M(n, m) = O(n)$
148 ///
149 /// where $T$ is time, $M$ is additional memory, $n$ is `n`, and $m$ is `self.len()`.
150 ///
151 /// # Panics
152 /// Panics if the polynomial is nonzero and `n` is greater than `usize::MAX`.
153 ///
154 /// # Examples
155 /// ```
156 /// use core::str::FromStr;
157 /// use malachite_base::num::basic::traits::Zero;
158 /// use malachite_base::polynomial::MulPowerOfXAssign;
159 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
160 ///
161 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^2+3*x+2").unwrap();
162 /// p.mul_power_of_x_assign(2);
163 /// assert_eq!(p.to_string(), "x^4+3*x^3+2*x^2");
164 ///
165 /// let mut p = UnsignedPolynomial::<u8>::from_str("5").unwrap();
166 /// p.mul_power_of_x_assign(1);
167 /// assert_eq!(p.to_string(), "5*x");
168 ///
169 /// let mut p = UnsignedPolynomial::<u8>::ZERO;
170 /// p.mul_power_of_x_assign(3);
171 /// assert_eq!(p, UnsignedPolynomial::<u8>::ZERO);
172 /// ```
173 ///
174 /// This is equivalent to `nmod_poly_shift_left` from `nmod_poly/shift_left.c`, FLINT 3.6.0.
175 fn mul_power_of_x_assign(&mut self, n: u64) {
176 if n == 0 || self.coefficients.is_empty() {
177 return;
178 }
179 let n = usize::exact_from(n);
180 self.coefficients.splice(0..0, repeat_n(T::ZERO, n));
181 }
182}