malachite_nz/integer/comparison/
cmp_product.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::{OrdProduct, OrdProductNeg};
13
14// Compares `a * b` with the integer whose sign is `c_sign` (`true` for non-negative) and whose
15// absolute value is `c_abs`; `c_sign` is ignored when `c_abs` is zero. The signs settle every case
16// except when `a * b` and `c` are nonzero with the same sign, where the absolute values are
17// compared by `Natural::cmp_product`.
18fn cmp_product_helper(a: &Integer, b: &Integer, c_sign: bool, c_abs: &Natural) -> Ordering {
19    let c_zero = *c_abs == 0u32;
20    if a.abs == 0u32 || b.abs == 0u32 {
21        if c_zero {
22            Equal
23        } else if c_sign {
24            Less
25        } else {
26            Greater
27        }
28    } else if a.sign == b.sign {
29        if c_zero || !c_sign {
30            Greater
31        } else {
32            Natural::cmp_product(&a.abs, &b.abs, c_abs)
33        }
34    } else if c_zero || c_sign {
35        Less
36    } else {
37        Natural::cmp_product(&a.abs, &b.abs, c_abs).reverse()
38    }
39}
40
41impl OrdProduct for Integer {
42    /// Compares the product of two [`Integer`]s with a third, computing the product only as a last
43    /// resort.
44    ///
45    /// $$
46    /// f(a, b, c) = \operatorname{cmp}(ab, c).
47    /// $$
48    ///
49    /// The signs decide every case except when $ab$ and $c$ are nonzero and have the same sign,
50    /// where the absolute values are compared by [`Natural::cmp_product`](OrdProduct::cmp_product),
51    /// which multiplies only as a last resort.
52    ///
53    /// # Worst-case complexity
54    /// $T(n) = O(n \log n \log\log n)$
55    ///
56    /// $M(n) = O(n \log n)$
57    ///
58    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(a.significant_bits(),
59    /// b.significant_bits())`.
60    ///
61    /// # Examples
62    /// ```
63    /// use core::cmp::Ordering::*;
64    /// use malachite_base::num::comparison::traits::OrdProduct;
65    /// use malachite_nz::integer::Integer;
66    ///
67    /// let z = |x: i32| Integer::from(x);
68    /// assert_eq!(Integer::cmp_product(&z(-3), &z(-7), &z(21)), Equal);
69    /// assert_eq!(Integer::cmp_product(&z(-3), &z(7), &z(-20)), Less);
70    /// assert_eq!(Integer::cmp_product(&z(3), &z(7), &z(-21)), Greater);
71    /// ```
72    ///
73    /// This is equivalent to `compareProduct` from `AzInt/CompareProduct.lean`, Azurite.
74    #[inline]
75    fn cmp_product(a: &Self, b: &Self, c: &Self) -> Ordering {
76        cmp_product_helper(a, b, c.sign, &c.abs)
77    }
78}
79
80impl OrdProductNeg for Integer {
81    /// Compares the product of two [`Integer`]s with the negative of a third, computing the product
82    /// only as a last resort and never computing the negative; equivalently, the sign of $ab + c$.
83    ///
84    /// $$
85    /// f(a, b, c) = \operatorname{cmp}(ab, -c).
86    /// $$
87    ///
88    /// The negative is handled by flipping the sign of $c$ as it is read, so no value is allocated
89    /// for it.
90    ///
91    /// # Worst-case complexity
92    /// $T(n) = O(n \log n \log\log n)$
93    ///
94    /// $M(n) = O(n \log n)$
95    ///
96    /// where $T$ is time, $M$ is additional memory, and $n$ is `max(a.significant_bits(),
97    /// b.significant_bits())`.
98    ///
99    /// # Examples
100    /// ```
101    /// use core::cmp::Ordering::*;
102    /// use malachite_base::num::comparison::traits::OrdProductNeg;
103    /// use malachite_nz::integer::Integer;
104    ///
105    /// let z = |x: i32| Integer::from(x);
106    /// assert_eq!(Integer::cmp_product_neg(&z(-3), &z(-7), &z(-21)), Equal);
107    /// assert_eq!(Integer::cmp_product_neg(&z(-3), &z(7), &z(20)), Less);
108    /// assert_eq!(Integer::cmp_product_neg(&z(3), &z(7), &z(21)), Greater);
109    /// ```
110    #[inline]
111    fn cmp_product_neg(a: &Self, b: &Self, c: &Self) -> Ordering {
112        cmp_product_helper(a, b, !c.sign, &c.abs)
113    }
114}
malachite_nz/integer/comparison/cmp_product.rs

malachite_nz/integer/comparison/
cmp_product.rs
