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