malachite_base/unsigned_polynomial/arithmetic/
mod_is_reduced.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::{Height, ModIsReduced};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_polynomial::UnsignedPolynomial;
12
13impl<T: PrimitiveUnsigned> ModIsReduced<T> for UnsignedPolynomial<T> {
14    /// Returns whether a [`UnsignedPolynomial`] is reduced modulo a [`u64`] $m$; in other words,
15    /// whether every one of its coefficients is less than $m$.
16    ///
17    /// Asking that of every coefficient is asking it of the largest, so this is a comparison
18    /// against the polynomial's [`Height`](Height::to_height). The zero polynomial has no
19    /// coefficients and is reduced modulo every $m$.
20    ///
21    /// $m$ cannot be zero.
22    ///
23    /// $f(p, m) = (\max_i p_i < m)$.
24    ///
25    /// # Worst-case complexity
26    /// $T(n) = O(n)$
27    ///
28    /// $M(n) = O(1)$
29    ///
30    /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients.
31    ///
32    /// # Panics
33    /// Panics if `m` is 0.
34    ///
35    /// # Examples
36    /// ```
37    /// use core::str::FromStr;
38    /// use malachite_base::num::arithmetic::traits::ModIsReduced;
39    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
40    ///
41    /// // The coefficients are 2, 3, and 1, so 4 is large enough and 3 is not.
42    /// let p = UnsignedPolynomial::<u64>::from_str("x^2+3*x+2").unwrap();
43    /// assert_eq!(p.mod_is_reduced(&4), true);
44    /// assert_eq!(p.mod_is_reduced(&3), false);
45    ///
46    /// // The zero polynomial is reduced modulo everything.
47    /// assert_eq!(
48    ///     UnsignedPolynomial::<u64>::from_str("0")
49    ///         .unwrap()
50    ///         .mod_is_reduced(&1),
51    ///     true
52    /// );
53    /// ```
54    #[inline]
55    fn mod_is_reduced(&self, m: &T) -> bool {
56        assert_ne!(*m, T::ZERO);
57        self.to_height() < *m
58    }
59}
malachite_base/unsigned_polynomial/arithmetic/mod_is_reduced.rs

malachite_base/unsigned_polynomial/arithmetic/
mod_is_reduced.rs
