malachite_base/unsigned_polynomial/arithmetic/
height.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;
10use crate::num::basic::unsigneds::PrimitiveUnsigned;
11use crate::unsigned_polynomial::UnsignedPolynomial;
12
13impl<T: PrimitiveUnsigned> Height for UnsignedPolynomial<T> {
14    type Output = T;
15
16    /// Returns the height of a [`UnsignedPolynomial`]: the largest of its coefficients.
17    ///
18    /// The zero polynomial has no coefficients, and its height is 0.
19    ///
20    /// $$
21    /// f(p) = H(p) = \max_i |p_i|.
22    /// $$
23    ///
24    /// # Worst-case complexity
25    /// $T(n) = O(n)$
26    ///
27    /// $M(n) = O(1)$
28    ///
29    /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients.
30    ///
31    /// # Examples
32    /// ```
33    /// use core::str::FromStr;
34    /// use malachite_base::num::arithmetic::traits::Height;
35    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
36    ///
37    /// assert_eq!(
38    ///     UnsignedPolynomial::<u64>::from_str("x^2+3*x+2")
39    ///         .unwrap()
40    ///         .to_height(),
41    ///     3
42    /// );
43    /// assert_eq!(
44    ///     UnsignedPolynomial::<u64>::from_str("x^100")
45    ///         .unwrap()
46    ///         .to_height(),
47    ///     1
48    /// );
49    /// assert_eq!(
50    ///     UnsignedPolynomial::<u64>::from_str("0")
51    ///         .unwrap()
52    ///         .to_height(),
53    ///     0
54    /// );
55    /// ```
56    ///
57    /// This is equivalent to `fmpz_poly_height` from `fmpz_poly/norms.c`, FLINT 3.6.0, for a
58    /// polynomial whose coefficients are all nonnegative.
59    #[inline]
60    fn to_height(&self) -> T {
61        self.coefficients_asc()
62            .iter()
63            .copied()
64            .max()
65            .unwrap_or(T::ZERO)
66    }
67
68    /// Returns the height of a [`UnsignedPolynomial`], taking it by value.
69    ///
70    /// A [`u64`] is [`Copy`], so this is the same work as [`to_height`](Height::to_height); it is
71    /// here so that the two spellings agree across the types that implement [`Height`].
72    ///
73    /// # Worst-case complexity
74    /// $T(n) = O(n)$
75    ///
76    /// $M(n) = O(1)$
77    ///
78    /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients.
79    ///
80    /// # Examples
81    /// ```
82    /// use core::str::FromStr;
83    /// use malachite_base::num::arithmetic::traits::Height;
84    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
85    ///
86    /// assert_eq!(
87    ///     UnsignedPolynomial::<u64>::from_str("x^2+3*x+2")
88    ///         .unwrap()
89    ///         .into_height(),
90    ///     3
91    /// );
92    /// assert_eq!(
93    ///     UnsignedPolynomial::<u64>::from_str("0")
94    ///         .unwrap()
95    ///         .into_height(),
96    ///     0
97    /// );
98    /// ```
99    #[inline]
100    fn into_height(self) -> T {
101        self.to_height()
102    }
103
104    /// Returns the number of significant bits of the height of a [`UnsignedPolynomial`].
105    ///
106    /// Since bit length is monotone, this is the largest of the coefficients' bit lengths, which is
107    /// the bit length of the largest coefficient.
108    ///
109    /// # Worst-case complexity
110    /// $T(n) = O(n)$
111    ///
112    /// $M(n) = O(1)$
113    ///
114    /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients.
115    ///
116    /// # Examples
117    /// ```
118    /// use core::str::FromStr;
119    /// use malachite_base::num::arithmetic::traits::Height;
120    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
121    ///
122    /// assert_eq!(
123    ///     UnsignedPolynomial::<u64>::from_str("x^2+3*x+2")
124    ///         .unwrap()
125    ///         .height_significant_bits(),
126    ///     2
127    /// );
128    /// assert_eq!(
129    ///     UnsignedPolynomial::<u64>::from_str("0")
130    ///         .unwrap()
131    ///         .height_significant_bits(),
132    ///     0
133    /// );
134    /// ```
135    #[inline]
136    fn height_significant_bits(&self) -> u64 {
137        self.to_height().significant_bits()
138    }
139}
malachite_base/unsigned_polynomial/arithmetic/height.rs

malachite_base/unsigned_polynomial/arithmetic/
height.rs
