malachite_base/unsigned_polynomial/comparison/
cmp.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::basic::unsigneds::PrimitiveUnsigned;
10use crate::unsigned_polynomial::UnsignedPolynomial;
11use core::cmp::Ordering::{self, *};
12
13impl<T: PrimitiveUnsigned> PartialOrd for UnsignedPolynomial<T> {
14    /// Compares two [`UnsignedPolynomial`]s.
15    ///
16    /// See the documentation for the [`Ord`] implementation.
17    #[inline]
18    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
19        Some(self.cmp(other))
20    }
21}
22
23impl<T: PrimitiveUnsigned> Ord for UnsignedPolynomial<T> {
24    /// Compares two [`UnsignedPolynomial`]s by how they behave for large arguments.
25    ///
26    /// The greater polynomial is the one that is eventually greater: the comparison is the one that
27    /// $p(x)$ and $q(x)$ eventually settle into as $x$ grows. The coefficients are read as the
28    /// numbers they are, so the values being compared are the ones a polynomial over the integers
29    /// would take, not ones reduced by any modulus.
30    ///
31    /// $$
32    /// f(p, q) = \lim_{x \to \infty} \operatorname{cmp}(p(x), q(x)).
33    /// $$
34    ///
35    /// The limit always exists. $p - q$ is a polynomial, so it has finitely many roots, and past
36    /// the largest of them its sign is the sign of its leading coefficient and never changes again.
37    /// That also makes this a total order agreeing with [`Eq`]: the limit is $0$ exactly when $p -
38    /// q$ is the zero polynomial.
39    ///
40    /// Finding it needs no evaluation. A polynomial of higher degree eventually outgrows one of
41    /// lower degree, whatever their coefficients, so the degrees decide first; the zero polynomial,
42    /// having no degree at all, is below every other polynomial. Polynomials of equal degree are
43    /// decided by the highest-degree coefficient at which they differ, since that term eventually
44    /// outgrows the sum of everything below it.
45    ///
46    /// This is the order that makes the polynomials an ordered ring: it is unchanged by adding a
47    /// polynomial to both sides, and by multiplying both sides by a nonzero one. Restricted to the
48    /// constant polynomials it is the order on the `T`s, so the embedding of a number as a
49    /// polynomial preserves comparisons. It is not a well-order, and no order compatible with
50    /// addition can be: $x > x - 1 > x - 2 > \ldots$ descends forever. A well-order on polynomials
51    /// needs to weigh a polynomial's size against its degree, which this order does not do.
52    ///
53    /// # Worst-case complexity
54    /// $T(n) = O(n)$
55    ///
56    /// $M(n) = O(1)$
57    ///
58    /// where $T$ is time, $M$ is additional memory, and $n$ is the smaller of the two polynomials'
59    /// numbers of coefficients. Polynomials of different degrees are compared in constant time.
60    ///
61    /// # Examples
62    /// ```
63    /// use core::str::FromStr;
64    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
65    ///
66    /// // A higher degree wins however small its coefficients: x^2 eventually passes 1000000*x.
67    /// assert!(
68    ///     UnsignedPolynomial::<u64>::from_str("x^2").unwrap()
69    ///         > UnsignedPolynomial::<u64>::from_str("1000000*x").unwrap()
70    /// );
71    ///
72    /// // At equal degrees the leading coefficient decides.
73    /// assert!(
74    ///     UnsignedPolynomial::<u64>::from_str("2*x^2").unwrap()
75    ///         > UnsignedPolynomial::<u64>::from_str("x^2+1000000").unwrap()
76    /// );
77    ///
78    /// // When that ties, the next coefficient down does.
79    /// assert!(
80    ///     UnsignedPolynomial::<u64>::from_str("x^2+3*x").unwrap()
81    ///         > UnsignedPolynomial::<u64>::from_str("x^2+2*x+1000000").unwrap()
82    /// );
83    ///
84    /// // The zero polynomial is below everything else.
85    /// assert!(
86    ///     UnsignedPolynomial::<u64>::from_str("0").unwrap()
87    ///         < UnsignedPolynomial::<u64>::from_str("1").unwrap()
88    /// );
89    ///
90    /// // Constant polynomials compare as the numbers they are.
91    /// assert!(
92    ///     UnsignedPolynomial::<u64>::from_str("123").unwrap()
93    ///         > UnsignedPolynomial::<u64>::from_str("122").unwrap()
94    /// );
95    /// ```
96    fn cmp(&self, other: &Self) -> Ordering {
97        if core::ptr::eq(self, other) {
98            return Equal;
99        }
100        // The coefficients are held with no trailing zero, so the length is the degree plus one,
101        // and 0 for the zero polynomial; comparing lengths is comparing degrees. Once the lengths
102        // agree the iterators have the same length, so comparing them from the leading coefficient
103        // down is exactly the comparison at the highest coefficient where the two differ.
104        self.coefficients
105            .len()
106            .cmp(&other.coefficients.len())
107            .then_with(|| {
108                self.coefficients
109                    .iter()
110                    .rev()
111                    .cmp(other.coefficients.iter().rev())
112            })
113    }
114}
malachite_base/unsigned_polynomial/comparison/cmp.rs

malachite_base/unsigned_polynomial/comparison/
cmp.rs
