malachite_base/unsigned_polynomial/arithmetic/mod_power_of_2_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, ModPowerOf2IsReduced};
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_polynomial::UnsignedPolynomial;
12
13impl<T: PrimitiveUnsigned> ModPowerOf2IsReduced for UnsignedPolynomial<T> {
14 /// Returns whether a [`UnsignedPolynomial`] is reduced modulo $2^k$; in other words, whether
15 /// every one of its coefficients has no more than $k$ significant bits.
16 ///
17 /// Asking that of every coefficient is asking it of the largest, so this is the number of
18 /// significant bits of the polynomial's [`Height`](Height::to_height) — which bit length
19 /// being monotone means is the largest of the coefficients' bit lengths, so the height itself
20 /// never has to be built. The zero polynomial has no coefficients and is reduced modulo every
21 /// power of 2, including $2^0$.
22 ///
23 /// $f(p, k) = (\max_i p_i < 2^k)$.
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 /// # Examples
33 /// ```
34 /// use core::str::FromStr;
35 /// use malachite_base::num::arithmetic::traits::ModPowerOf2IsReduced;
36 /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
37 ///
38 /// // The largest coefficient is 3, which needs two bits.
39 /// let p = UnsignedPolynomial::<u64>::from_str("x^2+3*x+2").unwrap();
40 /// assert_eq!(p.mod_power_of_2_is_reduced(2), true);
41 /// assert_eq!(p.mod_power_of_2_is_reduced(1), false);
42 ///
43 /// // The zero polynomial is reduced modulo every power of 2.
44 /// assert_eq!(
45 /// UnsignedPolynomial::<u64>::from_str("0")
46 /// .unwrap()
47 /// .mod_power_of_2_is_reduced(0),
48 /// true
49 /// );
50 /// ```
51 #[inline]
52 fn mod_power_of_2_is_reduced(&self, pow: u64) -> bool {
53 self.height_significant_bits() <= pow
54 }
55}