malachite_base/unsigned_polynomial/arithmetic/
mod_power_of_2_sum.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::arithmetic::traits::{ModPowerOf2IsReduced, ModPowerOf2Sum};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_polynomial::UnsignedPolynomial;
12use crate::unsigned_polynomial::arithmetic::mod_power_of_2_add::{add_assign_ref, add_assign_val};
13use alloc::vec::Vec;
14
15fn assert_reduced<T: PrimitiveUnsigned>(p: &UnsignedPolynomial<T>, pow: u64) {
16    assert!(
17        p.mod_power_of_2_is_reduced(pow),
18        "every polynomial must be reduced mod 2^pow, but {p} has a coefficient >= 2^{pow}"
19    );
20}
21
22// Adds the polynomials' coefficients into one vector, reducing as it goes, and trims once at the
23// end, since leading coefficients can cancel. Summands of different degrees are fine, and the sum
24// of no polynomials is zero.
25fn mod_power_of_2_sum_owned<T: PrimitiveUnsigned, I: Iterator<Item = UnsignedPolynomial<T>>>(
26    xs: I,
27    pow: u64,
28) -> UnsignedPolynomial<T> {
29    assert!(pow <= T::WIDTH);
30    let mut sum: Vec<T> = Vec::new();
31    for p in xs {
32        assert_reduced(&p, pow);
33        add_assign_val(&mut sum, p.coefficients, pow);
34    }
35    let mut sum = UnsignedPolynomial { coefficients: sum };
36    sum.trim();
37    sum
38}
39
40fn mod_power_of_2_sum_ref<
41    'a,
42    T: PrimitiveUnsigned + 'a,
43    I: Iterator<Item = &'a UnsignedPolynomial<T>>,
44>(
45    xs: I,
46    pow: u64,
47) -> UnsignedPolynomial<T> {
48    assert!(pow <= T::WIDTH);
49    let mut sum: Vec<T> = Vec::new();
50    for p in xs {
51        assert_reduced(p, pow);
52        add_assign_ref(&mut sum, &p.coefficients, pow);
53    }
54    let mut sum = UnsignedPolynomial { coefficients: sum };
55    sum.trim();
56    sum
57}
58
59impl<T: PrimitiveUnsigned> ModPowerOf2Sum for UnsignedPolynomial<T> {
60    /// Adds up all the [`UnsignedPolynomial`]s in an iterator modulo $2^k$, taking the polynomials
61    /// by value. The coefficients must already be reduced.
62    ///
63    /// The summands may have different degrees, and the sum of no polynomials is zero.
64    ///
65    /// $f((p_i)_ {i=0}^{n-1}) = q$, where every coefficient of $q$ is less than $2^k$ and $\sum_
66    /// {i=0}^{n-1} p_i \equiv q \mod 2^k$, coefficient by coefficient.
67    ///
68    /// # Worst-case complexity
69    /// $T(n) = O(n)$
70    ///
71    /// $M(m) = O(m)$
72    ///
73    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of coefficients of all
74    /// the polynomials, and $m$ is the greatest number of coefficients of any of them.
75    ///
76    /// # Panics
77    /// Panics if `pow` is greater than `T::WIDTH` or if any coefficient is greater than or equal to
78    /// $2^k$.
79    ///
80    /// # Examples
81    /// ```
82    /// use core::str::FromStr;
83    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Sum;
84    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
85    ///
86    /// let ps = ["x^2+2*x+3", "7*x+5", "x^3+7*x^2+6*x"]
87    ///     .map(|s| UnsignedPolynomial::<u8>::from_str(s).unwrap());
88    /// assert_eq!(
89    ///     UnsignedPolynomial::mod_power_of_2_sum(ps.into_iter(), 3).to_string(),
90    ///     "x^3+7*x"
91    /// );
92    /// ```
93    #[inline]
94    fn mod_power_of_2_sum<I: Iterator<Item = Self>>(xs: I, pow: u64) -> Self {
95        mod_power_of_2_sum_owned(xs, pow)
96    }
97}
98
99impl<'a, T: PrimitiveUnsigned> ModPowerOf2Sum<&'a Self> for UnsignedPolynomial<T> {
100    /// Adds up all the [`UnsignedPolynomial`]s in an iterator modulo $2^k$, taking the polynomials
101    /// by reference. The coefficients must already be reduced.
102    ///
103    /// The summands may have different degrees, and the sum of no polynomials is zero.
104    ///
105    /// $f((p_i)_ {i=0}^{n-1}) = q$, where every coefficient of $q$ is less than $2^k$ and $\sum_
106    /// {i=0}^{n-1} p_i \equiv q \mod 2^k$, coefficient by coefficient.
107    ///
108    /// # Worst-case complexity
109    /// $T(n) = O(n)$
110    ///
111    /// $M(m) = O(m)$
112    ///
113    /// where $T$ is time, $M$ is additional memory, $n$ is the total number of coefficients of all
114    /// the polynomials, and $m$ is the greatest number of coefficients of any of them.
115    ///
116    /// # Panics
117    /// Panics if `pow` is greater than `T::WIDTH` or if any coefficient is greater than or equal to
118    /// $2^k$.
119    ///
120    /// # Examples
121    /// ```
122    /// use core::str::FromStr;
123    /// use malachite_base::num::arithmetic::traits::ModPowerOf2Sum;
124    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
125    ///
126    /// let ps = ["x^2+2*x+3", "7*x+5", "x^3+7*x^2+6*x"]
127    ///     .map(|s| UnsignedPolynomial::<u8>::from_str(s).unwrap());
128    /// assert_eq!(
129    ///     UnsignedPolynomial::mod_power_of_2_sum(ps.iter(), 3).to_string(),
130    ///     "x^3+7*x"
131    /// );
132    /// ```
133    #[inline]
134    fn mod_power_of_2_sum<I: Iterator<Item = &'a Self>>(xs: I, pow: u64) -> Self {
135        mod_power_of_2_sum_ref(xs, pow)
136    }
137}
malachite_base/unsigned_polynomial/arithmetic/mod_power_of_2_sum.rs

malachite_base/unsigned_polynomial/arithmetic/
mod_power_of_2_sum.rs
