malachite_nz/integer_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::integer::Integer;
10use crate::integer_polynomial::{IntegerPolynomial, ZERO};
11use crate::natural::Natural;
12use malachite_base::num::arithmetic::traits::{Height, HeightRef, UnsignedAbs};
13use malachite_base::num::basic::traits::Zero;
14use malachite_base::num::logic::traits::SignificantBits;
15use malachite_base::polynomial::Polynomial;
16
17// The coefficient of largest magnitude, or a reference to zero if there are no coefficients. The
18// `Integer` is returned rather than its magnitude so that both the borrowing and the consuming
19// forms can start here.
20fn largest_coefficient(p: &IntegerPolynomial) -> &Integer {
21 p.coefficients_asc()
22 .iter()
23 .max_by(|x, y| x.unsigned_abs_ref().cmp(y.unsigned_abs_ref()))
24 .unwrap_or(&ZERO)
25}
26
27impl Height for IntegerPolynomial {
28 type Output = Natural;
29
30 /// Returns the height of an [`IntegerPolynomial`]: the largest of the absolute values of its
31 /// coefficients, taking the polynomial by reference and cloning.
32 ///
33 /// The zero polynomial has no coefficients, and its height is 0.
34 ///
35 /// $$
36 /// f(p) = H(p) = \max_i |p_i|.
37 /// $$
38 ///
39 /// # Worst-case complexity
40 /// $T(n) = O(n)$
41 ///
42 /// $M(n) = O(m)$
43 ///
44 /// where $T$ is time, $M$ is additional memory, $n$ is the total number of bits of the
45 /// coefficients, and $m$ is the number of bits of the height.
46 ///
47 /// # Examples
48 /// ```
49 /// use core::str::FromStr;
50 /// use malachite_base::num::arithmetic::traits::Height;
51 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
52 ///
53 /// assert_eq!(
54 /// IntegerPolynomial::from_str("x^2-3*x+2")
55 /// .unwrap()
56 /// .to_height(),
57 /// 3
58 /// );
59 /// assert_eq!(
60 /// IntegerPolynomial::from_str("-x^100").unwrap().to_height(),
61 /// 1
62 /// );
63 /// assert_eq!(IntegerPolynomial::from_str("0").unwrap().to_height(), 0);
64 /// ```
65 ///
66 /// This is `fmpz_poly_height` from `fmpz_poly/norms.c`, FLINT 3.6.0.
67 #[inline]
68 fn to_height(&self) -> Natural {
69 self.height_ref().clone()
70 }
71
72 /// Returns the height of an [`IntegerPolynomial`]: the largest of the absolute values of its
73 /// coefficients, taking the polynomial by value.
74 ///
75 /// The coefficient of largest magnitude is moved out of the polynomial rather than cloned.
76 ///
77 /// # Worst-case complexity
78 /// $T(n) = O(n)$
79 ///
80 /// $M(n) = O(1)$
81 ///
82 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
83 /// coefficients.
84 ///
85 /// # Examples
86 /// ```
87 /// use core::str::FromStr;
88 /// use malachite_base::num::arithmetic::traits::Height;
89 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
90 ///
91 /// assert_eq!(
92 /// IntegerPolynomial::from_str("x^2-3*x+2")
93 /// .unwrap()
94 /// .into_height(),
95 /// 3
96 /// );
97 /// assert_eq!(IntegerPolynomial::from_str("0").unwrap().into_height(), 0);
98 /// ```
99 #[inline]
100 fn into_height(self) -> Natural {
101 self.into_coefficients_asc()
102 .into_iter()
103 .map(Integer::unsigned_abs)
104 .max()
105 .unwrap_or(Natural::ZERO)
106 }
107
108 /// Returns the number of significant bits of the height of an [`IntegerPolynomial`].
109 ///
110 /// Since bit length is monotone, this is the largest of the coefficients' bit lengths, without
111 /// materializing the height.
112 ///
113 /// # Worst-case complexity
114 /// $T(n) = O(n)$
115 ///
116 /// $M(n) = O(1)$
117 ///
118 /// where $T$ is time, $M$ is additional memory, and $n$ is the number of coefficients.
119 ///
120 /// # Examples
121 /// ```
122 /// use core::str::FromStr;
123 /// use malachite_base::num::arithmetic::traits::Height;
124 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
125 ///
126 /// assert_eq!(
127 /// IntegerPolynomial::from_str("x^2-3*x+2")
128 /// .unwrap()
129 /// .height_significant_bits(),
130 /// 2
131 /// );
132 /// assert_eq!(
133 /// IntegerPolynomial::from_str("0")
134 /// .unwrap()
135 /// .height_significant_bits(),
136 /// 0
137 /// );
138 /// ```
139 #[inline]
140 fn height_significant_bits(&self) -> u64 {
141 self.coefficients_asc()
142 .iter()
143 .map(SignificantBits::significant_bits)
144 .max()
145 .unwrap_or(0)
146 }
147}
148
149impl HeightRef for IntegerPolynomial {
150 /// Returns a reference to the height of an [`IntegerPolynomial`]: the largest of the absolute
151 /// values of its coefficients.
152 ///
153 /// An [`Integer`] holds its magnitude as a [`Natural`], so the height is already there to be
154 /// lent and nothing needs to be built. The zero polynomial has no coefficients, and a reference
155 /// to zero is returned for it.
156 ///
157 /// # Worst-case complexity
158 /// $T(n) = O(n)$
159 ///
160 /// $M(n) = O(1)$
161 ///
162 /// where $T$ is time, $M$ is additional memory, and $n$ is the total number of bits of the
163 /// coefficients.
164 ///
165 /// # Examples
166 /// ```
167 /// use core::str::FromStr;
168 /// use malachite_base::num::arithmetic::traits::HeightRef;
169 /// use malachite_nz::integer_polynomial::IntegerPolynomial;
170 ///
171 /// assert_eq!(
172 /// *IntegerPolynomial::from_str("x^2-3*x+2")
173 /// .unwrap()
174 /// .height_ref(),
175 /// 3
176 /// );
177 /// assert_eq!(*IntegerPolynomial::from_str("0").unwrap().height_ref(), 0);
178 /// ```
179 #[inline]
180 fn height_ref(&self) -> &Natural {
181 largest_coefficient(self).unsigned_abs_ref()
182 }
183}