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