malachite_nz/integer_polynomial/arithmetic/div_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_polynomial::IntegerPolynomial;
10use malachite_base::num::basic::traits::Zero;
11use malachite_base::num::conversion::traits::ExactFrom;
12use malachite_base::polynomial::{DivPowerOfX, DivPowerOfXAssign, Polynomial};
13
14impl DivPowerOfX for IntegerPolynomial {
15 type Output = Self;
16
17 /// Divides an [`IntegerPolynomial`] by $x^n$, discarding the remainder, taking it by value.
18 /// Every coefficient moves down by $n$ places, and the lowest $n$ are dropped.
19 ///
20 /// $$
21 /// f(p, n) = \sum_{i \geq n} p_ix^{i-n}.
22 /// $$
23 ///
24 /// The result is zero when $n$ is at least the number of coefficients, and dividing by $x^0$
25 /// changes nothing. Multiplying the result by $x^n$ and adding back the dropped low part, the
26 /// truncation to $n$ coefficients, gives the polynomial back.
27 ///
28 /// # Worst-case complexity
29 /// $T(m) = O(m)$
30 ///
31 /// $M(m) = O(1)$
32 ///
33 /// where $T$ is time, $M$ is additional memory, and $m$ is the total number of bits of the
34 /// coefficients.
35 ///
36 /// # Examples
37 /// ```
38 /// use core::str::FromStr;
39 /// use malachite_base::num::basic::traits::Zero;
40 /// use malachite_base::polynomial::DivPowerOfX;
41 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
42 ///
43 /// let p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
44 /// assert_eq!(p.div_power_of_x(2).to_string(), "x-3");
45 /// let p = IntegerPolynomial::from_str("-5*x").unwrap();
46 /// assert_eq!(p.div_power_of_x(1).to_string(), "-5");
47 /// let p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
48 /// assert_eq!(p.div_power_of_x(10), IntegerPolynomial::ZERO);
49 /// ```
50 ///
51 /// This is equivalent to `fmpz_poly_shift_right` from `fmpz_poly/shift_right.c`, FLINT 3.6.0.
52 #[inline]
53 fn div_power_of_x(mut self, n: u64) -> Self {
54 self.div_power_of_x_assign(n);
55 self
56 }
57}
58
59impl DivPowerOfX for &IntegerPolynomial {
60 type Output = IntegerPolynomial;
61
62 /// Divides an [`IntegerPolynomial`] by $x^n$, discarding the remainder, taking it by reference.
63 /// Every coefficient moves down by $n$ places, and the lowest $n$ are dropped.
64 ///
65 /// $$
66 /// f(p, n) = \sum_{i \geq n} p_ix^{i-n}.
67 /// $$
68 ///
69 /// The result is zero when $n$ is at least the number of coefficients, and dividing by $x^0$
70 /// changes nothing. Multiplying the result by $x^n$ and adding back the dropped low part, the
71 /// truncation to $n$ coefficients, gives the polynomial back.
72 ///
73 /// # Worst-case complexity
74 /// $T(m) = O(m)$
75 ///
76 /// $M(m) = O(m)$
77 ///
78 /// where $T$ is time, $M$ is additional memory, and $m$ is the total number of bits of the
79 /// coefficients.
80 ///
81 /// # Examples
82 /// ```
83 /// use core::str::FromStr;
84 /// use malachite_base::num::basic::traits::Zero;
85 /// use malachite_base::polynomial::DivPowerOfX;
86 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
87 ///
88 /// let p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
89 /// assert_eq!((&p).div_power_of_x(2).to_string(), "x-3");
90 /// let p = IntegerPolynomial::from_str("-5*x").unwrap();
91 /// assert_eq!((&p).div_power_of_x(1).to_string(), "-5");
92 /// let p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
93 /// assert_eq!((&p).div_power_of_x(10), IntegerPolynomial::ZERO);
94 /// ```
95 ///
96 /// This is equivalent to `fmpz_poly_shift_right` from `fmpz_poly/shift_right.c`, FLINT 3.6.0.
97 fn div_power_of_x(self, n: u64) -> IntegerPolynomial {
98 if n >= self.len() {
99 return IntegerPolynomial::ZERO;
100 }
101 // The leading coefficient is kept, so the result needs no trimming.
102 IntegerPolynomial {
103 coefficients: self.coefficients[usize::exact_from(n)..].to_vec(),
104 }
105 }
106}
107
108impl DivPowerOfXAssign for IntegerPolynomial {
109 /// Divides an [`IntegerPolynomial`] by $x^n$ in place, discarding the remainder. Every
110 /// coefficient moves down by $n$ places, and the lowest $n$ are dropped.
111 ///
112 /// $$
113 /// p \gets \sum_{i \geq n} p_ix^{i-n}.
114 /// $$
115 ///
116 /// The result is zero when $n$ is at least the number of coefficients, and dividing by $x^0$
117 /// changes nothing. Multiplying the result by $x^n$ and adding back the dropped low part, the
118 /// truncation to $n$ coefficients, gives the polynomial back.
119 ///
120 /// # Worst-case complexity
121 /// $T(m) = O(m)$
122 ///
123 /// $M(m) = O(1)$
124 ///
125 /// where $T$ is time, $M$ is additional memory, and $m$ is the total number of bits of the
126 /// coefficients.
127 ///
128 /// # Examples
129 /// ```
130 /// use core::str::FromStr;
131 /// use malachite_base::num::basic::traits::Zero;
132 /// use malachite_base::polynomial::DivPowerOfXAssign;
133 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
134 ///
135 /// let mut p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
136 /// p.div_power_of_x_assign(2);
137 /// assert_eq!(p.to_string(), "x-3");
138 ///
139 /// let mut p = IntegerPolynomial::from_str("-5*x").unwrap();
140 /// p.div_power_of_x_assign(1);
141 /// assert_eq!(p.to_string(), "-5");
142 ///
143 /// let mut p = IntegerPolynomial::from_str("x^3-3*x^2+2*x-5").unwrap();
144 /// p.div_power_of_x_assign(10);
145 /// assert_eq!(p, IntegerPolynomial::ZERO);
146 /// ```
147 ///
148 /// This is equivalent to `fmpz_poly_shift_right` from `fmpz_poly/shift_right.c`, FLINT 3.6.0.
149 fn div_power_of_x_assign(&mut self, n: u64) {
150 if n >= self.len() {
151 *self = Self::ZERO;
152 } else if n != 0 {
153 self.coefficients.drain(..usize::exact_from(n));
154 }
155 }
156}