malachite_base/unsigned_polynomial/arithmetic/mod_power_of_2_add_truncated.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::polynomial::{ModPowerOf2AddTruncated, ModPowerOf2AddTruncatedAssign, Polynomial};
11use crate::unsigned_polynomial::UnsignedPolynomial;
12use crate::unsigned_polynomial::arithmetic::mod_power_of_2_add::{
13 add_assign_ref, add_assign_val, assert_reduced,
14};
15
16// The first `len` elements of `xs`, or all of them if there are fewer.
17fn prefix<T: PrimitiveUnsigned>(xs: &[T], len: u64) -> &[T] {
18 &xs[..usize::try_from(len).map_or(xs.len(), |len| len.min(xs.len()))]
19}
20
21impl<T: PrimitiveUnsigned> ModPowerOf2AddTruncated<Self> for UnsignedPolynomial<T> {
22 type Output = Self;
23
24 /// Adds two [`UnsignedPolynomial`]s modulo $2^k$, keeping only the coefficients of $x^i$ for
25 /// $i$ less than `len`, taking both by value. The coefficients of both must already be reduced
26 /// modulo $2^k$.
27 ///
28 /// $$
29 /// f(p, q, n, k) = ((p + q) \bmod x^n) \bmod 2^k.
30 /// $$
31 ///
32 /// The polynomials need not already be truncated: this is the sum of their images modulo $x^n$,
33 /// so only the first `len` coefficients of each are read. The sum is trimmed, so when
34 /// coefficients cancel modulo $2^k$ at the top of the kept range, the degree is lower still.
35 ///
36 /// # Worst-case complexity
37 /// $T(n) = O(n)$
38 ///
39 /// $M(n) = O(n)$
40 ///
41 /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients of the
42 /// longer polynomial times `pow`.
43 ///
44 /// # Panics
45 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` or `other` is
46 /// greater than or equal to $2^k$.
47 ///
48 /// # Examples
49 /// ```
50 /// use core::str::FromStr;
51 /// use malachite_base::polynomial::ModPowerOf2AddTruncated;
52 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
53 ///
54 /// // The linear coefficients wrap around to 0.
55 /// assert_eq!(
56 /// UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5")
57 /// .unwrap()
58 /// .mod_power_of_2_add_truncated(
59 /// UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
60 /// 3,
61 /// 3
62 /// )
63 /// .to_string(),
64 /// "6*x^2+7"
65 /// );
66 /// assert_eq!(
67 /// UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5")
68 /// .unwrap()
69 /// .mod_power_of_2_add_truncated(
70 /// UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
71 /// 1,
72 /// 3
73 /// )
74 /// .to_string(),
75 /// "7"
76 /// );
77 /// ```
78 ///
79 /// This is equivalent to `nmod_poly_add_series` from `nmod_poly/add_series.c`, FLINT 3.6.0,
80 /// with the modulus $2^k$.
81 fn mod_power_of_2_add_truncated(mut self, mut other: Self, len: u64, pow: u64) -> Self {
82 assert_reduced(&self, &other, pow);
83 self.truncate_assign(len);
84 other.truncate_assign(len);
85 add_assign_val(&mut self.coefficients, other.coefficients, pow);
86 self.trim();
87 self
88 }
89}
90
91impl<T: PrimitiveUnsigned> ModPowerOf2AddTruncated<&Self> for UnsignedPolynomial<T> {
92 type Output = Self;
93
94 /// Adds two [`UnsignedPolynomial`]s modulo $2^k$, keeping only the coefficients of $x^i$ for
95 /// $i$ less than `len`, taking the first by value and the second by reference. The coefficients
96 /// of both must already be reduced modulo $2^k$.
97 ///
98 /// $$
99 /// f(p, q, n, k) = ((p + q) \bmod x^n) \bmod 2^k.
100 /// $$
101 ///
102 /// The polynomials need not already be truncated: this is the sum of their images modulo $x^n$,
103 /// so only the first `len` coefficients of each are read. The sum is trimmed, so when
104 /// coefficients cancel modulo $2^k$ at the top of the kept range, the degree is lower still.
105 ///
106 /// # Worst-case complexity
107 /// $T(n) = O(n)$
108 ///
109 /// $M(n) = O(n)$
110 ///
111 /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients of the
112 /// longer polynomial times `pow`.
113 ///
114 /// # Panics
115 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` or `other` is
116 /// greater than or equal to $2^k$.
117 ///
118 /// # Examples
119 /// ```
120 /// use core::str::FromStr;
121 /// use malachite_base::polynomial::ModPowerOf2AddTruncated;
122 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
123 ///
124 /// // The linear coefficients wrap around to 0.
125 /// assert_eq!(
126 /// UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5")
127 /// .unwrap()
128 /// .mod_power_of_2_add_truncated(
129 /// &UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
130 /// 3,
131 /// 3
132 /// )
133 /// .to_string(),
134 /// "6*x^2+7"
135 /// );
136 /// assert_eq!(
137 /// UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5")
138 /// .unwrap()
139 /// .mod_power_of_2_add_truncated(
140 /// &UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
141 /// 1,
142 /// 3
143 /// )
144 /// .to_string(),
145 /// "7"
146 /// );
147 /// ```
148 ///
149 /// This is equivalent to `nmod_poly_add_series` from `nmod_poly/add_series.c`, FLINT 3.6.0,
150 /// with the modulus $2^k$.
151 fn mod_power_of_2_add_truncated(mut self, other: &Self, len: u64, pow: u64) -> Self {
152 assert_reduced(&self, other, pow);
153 self.truncate_assign(len);
154 add_assign_ref(
155 &mut self.coefficients,
156 prefix(&other.coefficients, len),
157 pow,
158 );
159 self.trim();
160 self
161 }
162}
163
164impl<T: PrimitiveUnsigned> ModPowerOf2AddTruncated<UnsignedPolynomial<T>>
165 for &UnsignedPolynomial<T>
166{
167 type Output = UnsignedPolynomial<T>;
168
169 /// Adds two [`UnsignedPolynomial`]s modulo $2^k$, keeping only the coefficients of $x^i$ for
170 /// $i$ less than `len`, taking the first by reference and the second by value. The coefficients
171 /// of both must already be reduced modulo $2^k$.
172 ///
173 /// $$
174 /// f(p, q, n, k) = ((p + q) \bmod x^n) \bmod 2^k.
175 /// $$
176 ///
177 /// The polynomials need not already be truncated: this is the sum of their images modulo $x^n$,
178 /// so only the first `len` coefficients of each are read. The sum is trimmed, so when
179 /// coefficients cancel modulo $2^k$ at the top of the kept range, the degree is lower still.
180 ///
181 /// # Worst-case complexity
182 /// $T(n) = O(n)$
183 ///
184 /// $M(n) = O(n)$
185 ///
186 /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients of the
187 /// longer polynomial times `pow`.
188 ///
189 /// # Panics
190 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` or `other` is
191 /// greater than or equal to $2^k$.
192 ///
193 /// # Examples
194 /// ```
195 /// use core::str::FromStr;
196 /// use malachite_base::polynomial::ModPowerOf2AddTruncated;
197 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
198 ///
199 /// // The linear coefficients wrap around to 0.
200 /// assert_eq!(
201 /// (&UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap())
202 /// .mod_power_of_2_add_truncated(
203 /// UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
204 /// 3,
205 /// 3
206 /// )
207 /// .to_string(),
208 /// "6*x^2+7"
209 /// );
210 /// assert_eq!(
211 /// (&UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap())
212 /// .mod_power_of_2_add_truncated(
213 /// UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
214 /// 1,
215 /// 3
216 /// )
217 /// .to_string(),
218 /// "7"
219 /// );
220 /// ```
221 ///
222 /// This is equivalent to `nmod_poly_add_series` from `nmod_poly/add_series.c`, FLINT 3.6.0,
223 /// with the modulus $2^k$.
224 fn mod_power_of_2_add_truncated(
225 self,
226 mut other: UnsignedPolynomial<T>,
227 len: u64,
228 pow: u64,
229 ) -> UnsignedPolynomial<T> {
230 assert_reduced(self, &other, pow);
231 other.truncate_assign(len);
232 add_assign_ref(
233 &mut other.coefficients,
234 prefix(&self.coefficients, len),
235 pow,
236 );
237 other.trim();
238 other
239 }
240}
241
242impl<T: PrimitiveUnsigned> ModPowerOf2AddTruncated<&UnsignedPolynomial<T>>
243 for &UnsignedPolynomial<T>
244{
245 type Output = UnsignedPolynomial<T>;
246
247 /// Adds two [`UnsignedPolynomial`]s modulo $2^k$, keeping only the coefficients of $x^i$ for
248 /// $i$ less than `len`, taking both by reference. The coefficients of both must already be
249 /// reduced modulo $2^k$.
250 ///
251 /// $$
252 /// f(p, q, n, k) = ((p + q) \bmod x^n) \bmod 2^k.
253 /// $$
254 ///
255 /// The polynomials need not already be truncated: this is the sum of their images modulo $x^n$,
256 /// so only the first `len` coefficients of each are read. The sum is trimmed, so when
257 /// coefficients cancel modulo $2^k$ at the top of the kept range, the degree is lower still.
258 ///
259 /// # Worst-case complexity
260 /// $T(n) = O(n)$
261 ///
262 /// $M(n) = O(n)$
263 ///
264 /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients of the
265 /// longer polynomial times `pow`.
266 ///
267 /// # Panics
268 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` or `other` is
269 /// greater than or equal to $2^k$.
270 ///
271 /// # Examples
272 /// ```
273 /// use core::str::FromStr;
274 /// use malachite_base::polynomial::ModPowerOf2AddTruncated;
275 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
276 ///
277 /// // The linear coefficients wrap around to 0.
278 /// assert_eq!(
279 /// (&UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap())
280 /// .mod_power_of_2_add_truncated(
281 /// &UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
282 /// 3,
283 /// 3
284 /// )
285 /// .to_string(),
286 /// "6*x^2+7"
287 /// );
288 /// assert_eq!(
289 /// (&UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap())
290 /// .mod_power_of_2_add_truncated(
291 /// &UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
292 /// 1,
293 /// 3
294 /// )
295 /// .to_string(),
296 /// "7"
297 /// );
298 /// ```
299 ///
300 /// This is equivalent to `nmod_poly_add_series` from `nmod_poly/add_series.c`, FLINT 3.6.0,
301 /// with the modulus $2^k$.
302 fn mod_power_of_2_add_truncated(
303 self,
304 other: &UnsignedPolynomial<T>,
305 len: u64,
306 pow: u64,
307 ) -> UnsignedPolynomial<T> {
308 assert_reduced(self, other, pow);
309 let mut coefficients = prefix(&self.coefficients, len).to_vec();
310 add_assign_ref(&mut coefficients, prefix(&other.coefficients, len), pow);
311 let mut result = UnsignedPolynomial { coefficients };
312 result.trim();
313 result
314 }
315}
316
317impl<T: PrimitiveUnsigned> ModPowerOf2AddTruncatedAssign<Self> for UnsignedPolynomial<T> {
318 /// Adds an [`UnsignedPolynomial`] to an [`UnsignedPolynomial`] modulo $2^k$ in place, keeping
319 /// only the coefficients of $x^i$ for $i$ less than `len`, taking the second polynomial by
320 /// value. The coefficients of both must already be reduced modulo $2^k$.
321 ///
322 /// $$
323 /// p \gets ((p + q) \bmod x^n) \bmod 2^k.
324 /// $$
325 ///
326 /// The polynomials need not already be truncated: this is the sum of their images modulo $x^n$,
327 /// so only the first `len` coefficients of each are read. The sum is trimmed, so when
328 /// coefficients cancel modulo $2^k$ at the top of the kept range, the degree is lower still.
329 ///
330 /// # Worst-case complexity
331 /// $T(n) = O(n)$
332 ///
333 /// $M(n) = O(n)$
334 ///
335 /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients of the
336 /// longer polynomial times `pow`.
337 ///
338 /// # Panics
339 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` or `other` is
340 /// greater than or equal to $2^k$.
341 ///
342 /// # Examples
343 /// ```
344 /// use core::str::FromStr;
345 /// use malachite_base::polynomial::ModPowerOf2AddTruncatedAssign;
346 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
347 ///
348 /// // The linear coefficients wrap around to 0.
349 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap();
350 /// p.mod_power_of_2_add_truncated_assign(
351 /// UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
352 /// 3,
353 /// 3,
354 /// );
355 /// assert_eq!(p.to_string(), "6*x^2+7");
356 ///
357 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap();
358 /// p.mod_power_of_2_add_truncated_assign(
359 /// UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
360 /// 1,
361 /// 3,
362 /// );
363 /// assert_eq!(p.to_string(), "7");
364 /// ```
365 ///
366 /// This is equivalent to `nmod_poly_add_series` from `nmod_poly/add_series.c`, FLINT 3.6.0,
367 /// with the modulus $2^k$.
368 fn mod_power_of_2_add_truncated_assign(&mut self, mut other: Self, len: u64, pow: u64) {
369 assert_reduced(self, &other, pow);
370 self.truncate_assign(len);
371 other.truncate_assign(len);
372 add_assign_val(&mut self.coefficients, other.coefficients, pow);
373 self.trim();
374 }
375}
376
377impl<T: PrimitiveUnsigned> ModPowerOf2AddTruncatedAssign<&Self> for UnsignedPolynomial<T> {
378 /// Adds an [`UnsignedPolynomial`] to an [`UnsignedPolynomial`] modulo $2^k$ in place, keeping
379 /// only the coefficients of $x^i$ for $i$ less than `len`, taking the second polynomial by
380 /// reference. The coefficients of both must already be reduced modulo $2^k$.
381 ///
382 /// $$
383 /// p \gets ((p + q) \bmod x^n) \bmod 2^k.
384 /// $$
385 ///
386 /// The polynomials need not already be truncated: this is the sum of their images modulo $x^n$,
387 /// so only the first `len` coefficients of each are read. The sum is trimmed, so when
388 /// coefficients cancel modulo $2^k$ at the top of the kept range, the degree is lower still.
389 ///
390 /// # Worst-case complexity
391 /// $T(n) = O(n)$
392 ///
393 /// $M(n) = O(n)$
394 ///
395 /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients of the
396 /// longer polynomial times `pow`.
397 ///
398 /// # Panics
399 /// Panics if `pow` is greater than `T::WIDTH`, or if any coefficient of `self` or `other` is
400 /// greater than or equal to $2^k$.
401 ///
402 /// # Examples
403 /// ```
404 /// use core::str::FromStr;
405 /// use malachite_base::polynomial::ModPowerOf2AddTruncatedAssign;
406 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
407 ///
408 /// // The linear coefficients wrap around to 0.
409 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap();
410 /// p.mod_power_of_2_add_truncated_assign(
411 /// &UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
412 /// 3,
413 /// 3,
414 /// );
415 /// assert_eq!(p.to_string(), "6*x^2+7");
416 ///
417 /// let mut p = UnsignedPolynomial::<u8>::from_str("x^3+2*x^2+x+5").unwrap();
418 /// p.mod_power_of_2_add_truncated_assign(
419 /// &UnsignedPolynomial::<u8>::from_str("4*x^2+7*x+2").unwrap(),
420 /// 1,
421 /// 3,
422 /// );
423 /// assert_eq!(p.to_string(), "7");
424 /// ```
425 ///
426 /// This is equivalent to `nmod_poly_add_series` from `nmod_poly/add_series.c`, FLINT 3.6.0,
427 /// with the modulus $2^k$.
428 fn mod_power_of_2_add_truncated_assign(&mut self, other: &Self, len: u64, pow: u64) {
429 assert_reduced(self, other, pow);
430 self.truncate_assign(len);
431 add_assign_ref(
432 &mut self.coefficients,
433 prefix(&other.coefficients, len),
434 pow,
435 );
436 self.trim();
437 }
438}