malachite_base/unsigned_polynomial/arithmetic/
mod_product.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/>.
8use crate::num::arithmetic::traits::{ModIsReduced, ModMulAssign, ModProduct};
9use crate::num::basic::traits::Zero;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::polynomial::Polynomial;
12use crate::unsigned_polynomial::UnsignedPolynomial;
13
14fn assert_reduced<T: PrimitiveUnsigned>(p: &UnsignedPolynomial<T>, m: T) {
15    assert!(
16        p.mod_is_reduced(&m),
17        "every polynomial must be reduced mod m, but {p} has a coefficient >= {m}"
18    );
19}
20
21// Multiplies the polynomials together one at a time. Once the partial product is zero it stays
22// zero, so the factors after the one that made it zero are not examined; this happens more often
23// than for numbers, since modulo a power of 2 or a composite number two nonzero polynomials can
24// multiply to zero.
25fn mod_product_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    // The constant 1, reduced: the zero polynomial when the modulus is 1.
31    let mut product = if m == T::ONE {
32        UnsignedPolynomial::ZERO
33    } else {
34        UnsignedPolynomial::one()
35    };
36    for p in xs {
37        assert_reduced(&p, m);
38        product.mod_mul_assign(p, m);
39        if product == UnsignedPolynomial::ZERO {
40            break;
41        }
42    }
43    product
44}
45
46fn mod_product_ref<'a, T: PrimitiveUnsigned + 'a, I: Iterator<Item = &'a UnsignedPolynomial<T>>>(
47    xs: I,
48    m: T,
49) -> UnsignedPolynomial<T> {
50    assert_ne!(m, T::ZERO, "m cannot be zero");
51    // The constant 1, reduced: the zero polynomial when the modulus is 1.
52    let mut product = if m == T::ONE {
53        UnsignedPolynomial::ZERO
54    } else {
55        UnsignedPolynomial::one()
56    };
57    for p in xs {
58        assert_reduced(p, m);
59        product.mod_mul_assign(p, m);
60        if product == UnsignedPolynomial::ZERO {
61            break;
62        }
63    }
64    product
65}
66
67impl<T: PrimitiveUnsigned> ModProduct<Self, T> for UnsignedPolynomial<T> {
68    /// Multiplies together all the [`UnsignedPolynomial`]s in an iterator modulo another number
69    /// $m$, taking the polynomials by value. The coefficients must already be reduced.
70    ///
71    /// The product of no polynomials is the constant 1, reduced: the zero polynomial when $m = 1$.
72    ///
73    /// $f((p_i)_ {i=0}^{n-1}) = q$, where every coefficient of $q$ is less than $m$ and $\prod_
74    /// {i=0}^{n-1} p_i \equiv q \mod m$, coefficient by coefficient.
75    ///
76    /// # Worst-case complexity
77    /// $T(n) = O(n^2)$
78    ///
79    /// $M(n) = O(n)$
80    ///
81    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of coefficients of
82    /// all the polynomials.
83    ///
84    /// # Panics
85    /// Panics if `m` is zero or if any coefficient is greater than or equal to `m`. As soon as the
86    /// partial product is zero, the remaining polynomials are not examined, so an unreduced
87    /// coefficient after that point is not detected.
88    ///
89    /// # Examples
90    /// ```
91    /// use core::str::FromStr;
92    /// use malachite_base::num::arithmetic::traits::ModProduct;
93    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
94    ///
95    /// let ps = ["x+3", "2*x+1", "x^2+5"].map(|s| UnsignedPolynomial::<u8>::from_str(s).unwrap());
96    /// assert_eq!(
97    ///     UnsignedPolynomial::mod_product(ps.into_iter(), 9).to_string(),
98    ///     "2*x^4+7*x^3+4*x^2+8*x+6"
99    /// );
100    /// ```
101    #[inline]
102    fn mod_product<I: Iterator<Item = Self>>(xs: I, m: T) -> Self {
103        mod_product_owned(xs, m)
104    }
105}
106
107impl<'a, T: PrimitiveUnsigned> ModProduct<&'a Self, T> for UnsignedPolynomial<T> {
108    /// Multiplies together all the [`UnsignedPolynomial`]s in an iterator modulo another number
109    /// $m$, taking the polynomials by reference. The coefficients must already be reduced.
110    ///
111    /// The product of no polynomials is the constant 1, reduced: the zero polynomial when $m = 1$.
112    ///
113    /// $f((p_i)_ {i=0}^{n-1}) = q$, where every coefficient of $q$ is less than $m$ and $\prod_
114    /// {i=0}^{n-1} p_i \equiv q \mod m$, coefficient by coefficient.
115    ///
116    /// # Worst-case complexity
117    /// $T(n) = O(n^2)$
118    ///
119    /// $M(n) = O(n)$
120    ///
121    /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of coefficients of
122    /// all the polynomials.
123    ///
124    /// # Panics
125    /// Panics if `m` is zero or if any coefficient is greater than or equal to `m`. As soon as the
126    /// partial product is zero, the remaining polynomials are not examined, so an unreduced
127    /// coefficient after that point is not detected.
128    ///
129    /// # Examples
130    /// ```
131    /// use core::str::FromStr;
132    /// use malachite_base::num::arithmetic::traits::ModProduct;
133    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
134    ///
135    /// let ps = ["x+3", "2*x+1", "x^2+5"].map(|s| UnsignedPolynomial::<u8>::from_str(s).unwrap());
136    /// assert_eq!(
137    ///     UnsignedPolynomial::mod_product(ps.iter(), 9).to_string(),
138    ///     "2*x^4+7*x^3+4*x^2+8*x+6"
139    /// );
140    /// ```
141    #[inline]
142    fn mod_product<I: Iterator<Item = &'a Self>>(xs: I, m: T) -> Self {
143        mod_product_ref(xs, m)
144    }
145}
malachite_base/unsigned_polynomial/arithmetic/mod_product.rs

malachite_base/unsigned_polynomial/arithmetic/
mod_product.rs
