malachite_nz/integer/comparison/
cmp_products.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::natural::Natural;
11use core::cmp::Ordering::{self, *};
12use malachite_base::num::comparison::traits::{OrdProducts, OrdProductsNeg};
13
14// Compares `a * b` with `c * d`, or with `-(c * d)` if `negate_right`. The signs settle every case
15// except when both products are nonzero with the same sign, where the absolute values are compared
16// by `Natural::cmp_products`.
17fn cmp_products_helper(
18    a: &Integer,
19    b: &Integer,
20    c: &Integer,
21    d: &Integer,
22    negate_right: bool,
23) -> Ordering {
24    let left_zero = a.abs == 0u32 || b.abs == 0u32;
25    let right_zero = c.abs == 0u32 || d.abs == 0u32;
26    let left_positive = a.sign == b.sign;
27    let right_positive = (c.sign == d.sign) != negate_right;
28    if left_zero {
29        if right_zero {
30            Equal
31        } else if right_positive {
32            Less
33        } else {
34            Greater
35        }
36    } else if left_positive {
37        if right_zero || !right_positive {
38            Greater
39        } else {
40            Natural::cmp_products(&a.abs, &b.abs, &c.abs, &d.abs)
41        }
42    } else if right_zero || right_positive {
43        Less
44    } else {
45        Natural::cmp_products(&c.abs, &d.abs, &a.abs, &b.abs)
46    }
47}
48
49impl OrdProducts for Integer {
50    /// Compares the products of two pairs of [`Integer`]s, computing the products only as a last
51    /// resort.
52    ///
53    /// $$
54    /// f(a, b, c, d) = \operatorname{cmp}(ab, cd).
55    /// $$
56    ///
57    /// The signs decide every case except when both products are nonzero and have the same sign,
58    /// where the absolute values are compared by
59    /// [`Natural::cmp_products`](OrdProducts::cmp_products), which multiplies only as a last
60    /// resort.
61    ///
62    /// # Worst-case complexity
63    /// $T(n) = O(n \log n \log\log n)$
64    ///
65    /// $M(n) = O(n \log n)$
66    ///
67    /// where $T$ is time, $M$ is additional memory, and $n$ is the largest number of significant
68    /// bits of `a`, `b`, `c`, and `d`.
69    ///
70    /// # Examples
71    /// ```
72    /// use core::cmp::Ordering::*;
73    /// use malachite_base::num::comparison::traits::OrdProducts;
74    /// use malachite_nz::integer::Integer;
75    ///
76    /// let z = |x: i32| Integer::from(x);
77    /// assert_eq!(Integer::cmp_products(&z(-3), &z(7), &z(-7), &z(3)), Equal);
78    /// assert_eq!(Integer::cmp_products(&z(-3), &z(7), &z(-4), &z(5)), Less);
79    /// assert_eq!(Integer::cmp_products(&z(3), &z(7), &z(-4), &z(5)), Greater);
80    /// ```
81    ///
82    /// This is equivalent to `compareProducts` from `AzInt/CompareProducts.lean`, Azurite.
83    #[inline]
84    fn cmp_products(a: &Self, b: &Self, c: &Self, d: &Self) -> Ordering {
85        cmp_products_helper(a, b, c, d, false)
86    }
87}
88
89impl OrdProductsNeg for Integer {
90    /// Compares the product of two [`Integer`]s with the negative of the product of two others,
91    /// computing the products only as a last resort and never computing the negative; equivalently,
92    /// the sign of $ab + cd$.
93    ///
94    /// $$
95    /// f(a, b, c, d) = \operatorname{cmp}(ab, -cd).
96    /// $$
97    ///
98    /// The negative is handled by flipping the sign of $cd$, which is read from the signs of $c$
99    /// and $d$, so no value is allocated for it.
100    ///
101    /// # Worst-case complexity
102    /// $T(n) = O(n \log n \log\log n)$
103    ///
104    /// $M(n) = O(n \log n)$
105    ///
106    /// where $T$ is time, $M$ is additional memory, and $n$ is the largest number of significant
107    /// bits of `a`, `b`, `c`, and `d`.
108    ///
109    /// # Examples
110    /// ```
111    /// use core::cmp::Ordering::*;
112    /// use malachite_base::num::comparison::traits::OrdProductsNeg;
113    /// use malachite_nz::integer::Integer;
114    ///
115    /// let z = |x: i32| Integer::from(x);
116    /// assert_eq!(
117    ///     Integer::cmp_products_neg(&z(-3), &z(7), &z(7), &z(3)),
118    ///     Equal
119    /// );
120    /// assert_eq!(Integer::cmp_products_neg(&z(-3), &z(7), &z(4), &z(5)), Less);
121    /// assert_eq!(
122    ///     Integer::cmp_products_neg(&z(3), &z(7), &z(4), &z(5)),
123    ///     Greater
124    /// );
125    /// ```
126    #[inline]
127    fn cmp_products_neg(a: &Self, b: &Self, c: &Self, d: &Self) -> Ordering {
128        cmp_products_helper(a, b, c, d, true)
129    }
130}
malachite_nz/integer/comparison/cmp_products.rs

malachite_nz/integer/comparison/
cmp_products.rs
