dashu_ratio/third_party/
num_order.rs

1use crate::{
2    cmp::{repr_cmp_ibig, repr_cmp_ubig},
3    rbig::RBig,
4    repr::Repr,
5    Relaxed,
6};
7use _num_modular::{FixedMersenneInt, ModularInteger};
8use core::cmp::Ordering;
9use dashu_base::{BitTest, FloatEncoding, Sign, Signed};
10use dashu_int::{IBig, UBig};
11use num_order::{NumHash, NumOrd};
12
13macro_rules! impl_ord_between_ratio {
14    ($t1:ty, $t2:ty) => {
15        impl NumOrd<$t2> for $t1 {
16            #[inline]
17            fn num_eq(&self, other: &$t2) -> bool {
18                self.0.eq(&other.0)
19            }
20            #[inline]
21            fn num_partial_cmp(&self, other: &$t2) -> Option<Ordering> {
22                Some(self.0.cmp(&other.0))
23            }
24            #[inline]
25            fn num_cmp(&self, other: &$t2) -> Ordering {
26                self.0.cmp(&other.0)
27            }
28        }
29    };
30}
31impl_ord_between_ratio!(RBig, Relaxed);
32impl_ord_between_ratio!(Relaxed, RBig);
33
34impl NumOrd<UBig> for Repr {
35    #[inline]
36    fn num_cmp(&self, other: &UBig) -> Ordering {
37        repr_cmp_ubig::<false>(self, other)
38    }
39    #[inline]
40    fn num_partial_cmp(&self, other: &UBig) -> Option<Ordering> {
41        Some(repr_cmp_ubig::<false>(self, other))
42    }
43}
44
45impl NumOrd<IBig> for Repr {
46    #[inline]
47    fn num_cmp(&self, other: &IBig) -> Ordering {
48        repr_cmp_ibig::<false>(self, other)
49    }
50    #[inline]
51    fn num_partial_cmp(&self, other: &IBig) -> Option<Ordering> {
52        Some(repr_cmp_ibig::<false>(self, other))
53    }
54}
55
56macro_rules! forward_num_ord_to_repr {
57    ($R:ty, $T:ty) => {
58        impl NumOrd<$T> for $R {
59            #[inline]
60            fn num_cmp(&self, other: &$T) -> Ordering {
61                self.0.num_cmp(other)
62            }
63            #[inline]
64            fn num_partial_cmp(&self, other: &$T) -> Option<Ordering> {
65                self.0.num_partial_cmp(other)
66            }
67        }
68        impl NumOrd<$R> for $T {
69            #[inline]
70            fn num_cmp(&self, other: &$R) -> Ordering {
71                other.0.num_cmp(self).reverse()
72            }
73            #[inline]
74            fn num_partial_cmp(&self, other: &$R) -> Option<Ordering> {
75                other.0.num_partial_cmp(self).map(|ord| ord.reverse())
76            }
77        }
78    };
79}
80forward_num_ord_to_repr!(RBig, UBig);
81forward_num_ord_to_repr!(Relaxed, UBig);
82forward_num_ord_to_repr!(RBig, IBig);
83forward_num_ord_to_repr!(Relaxed, IBig);
84
85impl NumHash for Repr {
86    fn num_hash<H: core::hash::Hasher>(&self, state: &mut H) {
87        // 2^127 - 1 is used in the num-order crate
88        type MInt = FixedMersenneInt<127, 1>;
89        const M127: i128 = i128::MAX;
90        const M127U: u128 = M127 as u128;
91        const HASH_INF: i128 = i128::MAX;
92        const HASH_NEGINF: i128 = i128::MIN + 1;
93
94        let ub = (&self.denominator) % M127U; // denom is always positive in Ratio
95        let binv = if ub != 0 {
96            MInt::new(ub, &M127U).inv().unwrap()
97        } else {
98            // no modular inverse, use INF or NEGINF as the result
99            return if self.numerator.is_positive() {
100                HASH_INF.num_hash(state)
101            } else {
102                HASH_NEGINF.num_hash(state)
103            };
104        };
105
106        let ua = (&self.numerator) % M127;
107        let ua = binv.convert(ua.unsigned_abs());
108        let ab = (ua * binv).residue() as i128;
109        (self.numerator.sign() * ab).num_hash(state)
110    }
111}
112
113impl NumHash for RBig {
114    #[inline]
115    fn num_hash<H: core::hash::Hasher>(&self, state: &mut H) {
116        self.0.num_hash(state)
117    }
118}
119
120impl NumHash for Relaxed {
121    #[inline]
122    fn num_hash<H: core::hash::Hasher>(&self, state: &mut H) {
123        self.0.num_hash(state)
124    }
125}
126
127#[cfg(feature = "dashu-float")]
128mod with_float {
129    use super::*;
130    use crate::cmp::with_float::repr_cmp_fbig;
131    use dashu_float::{round::Round, FBig, Repr as FloatRepr};
132    use dashu_int::Word;
133
134    impl<const B: Word> NumOrd<FloatRepr<B>> for Repr {
135        #[inline]
136        fn num_cmp(&self, other: &FloatRepr<B>) -> Ordering {
137            repr_cmp_fbig::<B, false>(self, other)
138        }
139        #[inline]
140        fn num_partial_cmp(&self, other: &FloatRepr<B>) -> Option<Ordering> {
141            Some(repr_cmp_fbig::<B, false>(self, other))
142        }
143    }
144
145    impl<R: Round, const B: Word> NumOrd<FBig<R, B>> for RBig {
146        #[inline]
147        fn num_cmp(&self, other: &FBig<R, B>) -> Ordering {
148            self.0.num_cmp(other.repr())
149        }
150        #[inline]
151        fn num_partial_cmp(&self, other: &FBig<R, B>) -> Option<Ordering> {
152            self.0.num_partial_cmp(other.repr())
153        }
154    }
155
156    impl<R: Round, const B: Word> NumOrd<FBig<R, B>> for Relaxed {
157        #[inline]
158        fn num_cmp(&self, other: &FBig<R, B>) -> Ordering {
159            self.0.num_cmp(other.repr())
160        }
161        #[inline]
162        fn num_partial_cmp(&self, other: &FBig<R, B>) -> Option<Ordering> {
163            self.0.num_partial_cmp(other.repr())
164        }
165    }
166
167    impl<R: Round, const B: Word> NumOrd<RBig> for FBig<R, B> {
168        #[inline]
169        fn num_cmp(&self, other: &RBig) -> Ordering {
170            other.0.num_cmp(self.repr()).reverse()
171        }
172        #[inline]
173        fn num_partial_cmp(&self, other: &RBig) -> Option<Ordering> {
174            Some(self.num_cmp(other))
175        }
176    }
177
178    impl<R: Round, const B: Word> NumOrd<Relaxed> for FBig<R, B> {
179        #[inline]
180        fn num_cmp(&self, other: &Relaxed) -> Ordering {
181            other.0.num_cmp(self.repr()).reverse()
182        }
183        #[inline]
184        fn num_partial_cmp(&self, other: &Relaxed) -> Option<Ordering> {
185            Some(self.num_cmp(other))
186        }
187    }
188}
189
190macro_rules! impl_num_ord_with_unsigned {
191    ($($t:ty)*) => {$(
192        impl NumOrd<$t> for Repr {
193            #[inline]
194            fn num_cmp(&self, other: &$t) -> Ordering {
195                repr_cmp_ubig::<false>(self, &UBig::from(*other))
196            }
197            #[inline]
198            fn num_partial_cmp(&self, other: &$t) -> Option<Ordering> {
199                Some(repr_cmp_ubig::<false>(self, &UBig::from(*other)))
200            }
201        }
202        forward_num_ord_to_repr!(RBig, $t);
203        forward_num_ord_to_repr!(Relaxed, $t);
204    )*};
205}
206impl_num_ord_with_unsigned!(u8 u16 u32 u64 u128 usize);
207
208macro_rules! impl_num_ord_with_signed {
209    ($($t:ty)*) => {$(
210        impl NumOrd<$t> for Repr {
211            #[inline]
212            fn num_cmp(&self, other: &$t) -> Ordering {
213                repr_cmp_ibig::<false>(self, &IBig::from(*other))
214            }
215            #[inline]
216            fn num_partial_cmp(&self, other: &$t) -> Option<Ordering> {
217                Some(repr_cmp_ibig::<false>(self, &IBig::from(*other)))
218            }
219        }
220        forward_num_ord_to_repr!(RBig, $t);
221        forward_num_ord_to_repr!(Relaxed, $t);
222    )*};
223}
224impl_num_ord_with_signed!(i8 i16 i32 i64 i128 isize);
225
226macro_rules! impl_num_ord_with_float {
227    ($($t:ty)*) => {$(
228        impl NumOrd<$t> for Repr {
229            fn num_partial_cmp(&self, other: &$t) -> Option<Ordering> {
230                // step 1: compare with nan/inf/0
231                if other.is_nan() {
232                    return None;
233                } else if other.is_infinite() {
234                    return match other.sign() {
235                        Sign::Positive => Some(Ordering::Less),
236                        Sign::Negative => Some(Ordering::Greater),
237                    };
238                } else if *other == 0. {
239                    return match self.numerator.is_zero() {
240                        true => Some(Ordering::Equal),
241                        false => Some(self.numerator.sign() * Ordering::Greater)
242                    };
243                }
244
245                // step 2: compare sign
246                let sign = match (self.numerator.sign(), other.sign()) {
247                    (Sign::Positive, Sign::Positive) => Sign::Positive,
248                    (Sign::Positive, Sign::Negative) => return Some(Ordering::Greater),
249                    (Sign::Negative, Sign::Positive) => return Some(Ordering::Less),
250                    (Sign::Negative, Sign::Negative) => Sign::Negative,
251                };
252
253                // step 3: test if the number is bigger than the max float value
254                // Here we don't use EstimatedLog2, since a direct comparison is not that expensive.
255                // We just need a quick way to determine if one number is much larger than the other.
256                // The bit length (essentially ⌊log2(x)⌋ + 1) is used instead here.
257                let self_log2 = self.numerator.bit_len() as isize - self.denominator.bit_len() as isize;
258                let (self_log2_lb, self_log2_ub) = (self_log2 - 1, self_log2 + 1);
259                if self_log2_lb > (<$t>::MANTISSA_DIGITS as isize + <$t>::MAX_EXP as isize) {
260                    return Some(sign * Ordering::Greater);
261                }
262
263                // step 4: decode the float and compare the bits
264                let (other_man, other_exp) = other.decode().unwrap();
265                let other_log2 = other_man.bit_len() as isize + other_exp as isize - 1;
266                if self_log2_lb > other_log2 {
267                    return Some(sign * Ordering::Greater);
268                } else if self_log2_ub < other_log2 {
269                    return Some(sign * Ordering::Less);
270                }
271
272                // step 5: compare the exact values
273                let (other_man, other_exp) = other.decode().unwrap();
274                let (mut lhs, mut rhs) = (self.numerator.clone(), IBig::from(other_man) * &self.denominator);
275                if other_exp < 0 {
276                    lhs <<= -other_exp as usize;
277                } else {
278                    rhs <<= other_exp as usize;
279                }
280
281                Some(lhs.cmp(&rhs))
282            }
283        }
284    )*};
285}
286impl_num_ord_with_float!(f32 f64);
287forward_num_ord_to_repr!(RBig, f32);
288forward_num_ord_to_repr!(Relaxed, f32);
289forward_num_ord_to_repr!(RBig, f64);
290forward_num_ord_to_repr!(Relaxed, f64);
dashu_ratio/third_party/num_order.rs

dashu_ratio/third_party/
num_order.rs
