malachite_q/comparison/
partial_cmp_abs_natural.rs

1// Copyright © 2025 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::Rational;
10use core::cmp::Ordering::{self, *};
11use malachite_base::num::arithmetic::traits::Sign;
12use malachite_base::num::basic::traits::One;
13use malachite_base::num::comparison::traits::PartialOrdAbs;
14use malachite_base::num::conversion::traits::ExactFrom;
15use malachite_base::num::logic::traits::SignificantBits;
16use malachite_nz::natural::Natural;
17
18impl PartialOrdAbs<Natural> for Rational {
19    /// Compares the absolute values of a [`Rational`] and a [`Natural`].
20    ///
21    /// # Worst-case complexity
22    /// $T(n) = O(n \log n \log\log n)$
23    ///
24    /// $M(n) = O(n \log n)$
25    ///
26    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
27    /// other.significant_bits())`.
28    ///
29    /// # Examples
30    /// ```
31    /// use malachite_base::num::comparison::traits::PartialOrdAbs;
32    /// use malachite_nz::natural::Natural;
33    /// use malachite_q::Rational;
34    /// use std::cmp::Ordering::*;
35    ///
36    /// assert_eq!(
37    ///     Rational::from_signeds(22, 7).partial_cmp_abs(&Natural::from(3u32)),
38    ///     Some(Greater)
39    /// );
40    /// assert_eq!(
41    ///     Rational::from_signeds(-22, 7).partial_cmp_abs(&Natural::from(3u32)),
42    ///     Some(Greater)
43    /// );
44    /// ```
45    fn partial_cmp_abs(&self, other: &Natural) -> Option<Ordering> {
46        // First check if either value is zero
47        let self_sign = self.numerator_ref().sign();
48        let other_sign = other.sign();
49        let sign_cmp = self_sign.cmp(&other_sign);
50        if sign_cmp != Equal || self_sign == Equal {
51            return Some(sign_cmp);
52        }
53        // Then check if one is < 1 and the other is > 1
54        let self_cmp_one = self.numerator.cmp(&self.denominator);
55        let other_cmp_one = other.cmp(&Natural::ONE);
56        let one_cmp = self_cmp_one.cmp(&other_cmp_one);
57        if one_cmp != Equal {
58            return Some(one_cmp);
59        }
60        // Then compare numerators and denominators
61        let n_cmp = self.numerator.cmp(other);
62        let d_cmp = self.denominator.cmp(&Natural::ONE);
63        if n_cmp == Equal && d_cmp == Equal {
64            return Some(Equal);
65        }
66        let nd_cmp = n_cmp.cmp(&d_cmp);
67        if nd_cmp != Equal {
68            return Some(nd_cmp);
69        }
70        // Then compare floor ∘ log_2 ∘ abs
71        let log_cmp = self
72            .floor_log_base_2_abs()
73            .cmp(&i64::exact_from(other.significant_bits() - 1));
74        if log_cmp != Equal {
75            return Some(log_cmp);
76        }
77        // Finally, cross-multiply.
78        Some(self.numerator.cmp(&(&self.denominator * other)))
79    }
80}
81
82impl PartialOrdAbs<Rational> for Natural {
83    /// Compares the absolute values of a [`Natural`] and a [`Rational`].
84    ///
85    /// # Worst-case complexity
86    /// $T(n) = O(n \log n \log\log n)$
87    ///
88    /// $M(n) = O(n \log n)$
89    ///
90    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
91    /// other.significant_bits())`.
92    ///
93    /// # Examples
94    /// ```
95    /// use malachite_base::num::comparison::traits::PartialOrdAbs;
96    /// use malachite_nz::natural::Natural;
97    /// use malachite_q::Rational;
98    /// use std::cmp::Ordering::*;
99    ///
100    /// assert_eq!(
101    ///     Natural::from(3u32).partial_cmp_abs(&Rational::from_signeds(22, 7)),
102    ///     Some(Less)
103    /// );
104    /// assert_eq!(
105    ///     Natural::from(3u32).partial_cmp_abs(&Rational::from_signeds(-22, 7)),
106    ///     Some(Less)
107    /// );
108    /// ```
109    #[inline]
110    fn partial_cmp_abs(&self, other: &Rational) -> Option<Ordering> {
111        other.partial_cmp_abs(self).map(Ordering::reverse)
112    }
113}
malachite_q/comparison/partial_cmp_abs_natural.rs

malachite_q/comparison/
partial_cmp_abs_natural.rs
