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

malachite_base/unsigned_polynomial/arithmetic/
mod_sum.rs
