malachite_q/comparison/
cmp_abs.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::comparison::traits::{OrdAbs, PartialOrdAbs};
13
14impl PartialOrdAbs for Rational {
15    /// Compares the absolute values of two [`Rational`]s.
16    ///
17    /// See the documentation for the [`OrdAbs`] implementation.
18    #[inline]
19    fn partial_cmp_abs(&self, other: &Self) -> Option<Ordering> {
20        Some(self.cmp_abs(other))
21    }
22}
23
24impl OrdAbs for Rational {
25    /// Compares the absolute values of two [`Rational`]s.
26    ///
27    /// # Worst-case complexity
28    /// $T(n) = O(n \log n \log\log n)$
29    ///
30    /// $M(n) = O(n \log n)$
31    ///
32    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(self.significant_bits(),
33    /// other.significant_bits())`.
34    ///
35    /// # Examples
36    /// ```
37    /// use malachite_base::num::basic::traits::OneHalf;
38    /// use malachite_base::num::comparison::traits::OrdAbs;
39    /// use malachite_q::Rational;
40    /// use std::cmp::Ordering::*;
41    /// use std::str::FromStr;
42    ///
43    /// assert_eq!(
44    ///     Rational::from_str("2/3")
45    ///         .unwrap()
46    ///         .cmp_abs(&Rational::ONE_HALF),
47    ///     Greater
48    /// );
49    /// assert_eq!(
50    ///     Rational::from_str("-2/3")
51    ///         .unwrap()
52    ///         .cmp_abs(&Rational::ONE_HALF),
53    ///     Greater
54    /// );
55    /// ```
56    fn cmp_abs(&self, other: &Self) -> Ordering {
57        if core::ptr::eq(self, other) {
58            return Equal;
59        }
60        // First check if either value is zero
61        let self_sign = self.numerator_ref().sign();
62        let other_sign = other.numerator_ref().sign();
63        let sign_cmp = self_sign.cmp(&other_sign);
64        if sign_cmp != Equal || self_sign == Equal {
65            return sign_cmp;
66        }
67        // Then check if one is < 1 and the other is > 1
68        let self_cmp_one = self.numerator.cmp(&self.denominator);
69        let other_cmp_one = other.numerator.cmp(&other.denominator);
70        let one_cmp = self_cmp_one.cmp(&other_cmp_one);
71        if one_cmp != Equal {
72            return one_cmp;
73        }
74        // Then compare numerators and denominators
75        let n_cmp = self.numerator.cmp(&other.numerator);
76        let d_cmp = self.denominator.cmp(&other.denominator);
77        if n_cmp == Equal && d_cmp == Equal {
78            return Equal;
79        }
80        let nd_cmp = n_cmp.cmp(&d_cmp);
81        if nd_cmp != Equal {
82            return nd_cmp;
83        }
84        // Then compare floor ∘ log_2 ∘ abs
85        let log_cmp = self
86            .floor_log_base_2_abs()
87            .cmp(&other.floor_log_base_2_abs());
88        if log_cmp != Equal {
89            return log_cmp;
90        }
91        // Finally, cross-multiply.
92        (&self.numerator * &other.denominator).cmp(&(&self.denominator * &other.numerator))
93    }
94}
malachite_q/comparison/cmp_abs.rs

malachite_q/comparison/
cmp_abs.rs
