dashu_cmplx/third_party/
num_order.rs

1//! `NumOrd` / `NumHash` for [`CBig`] (behind the `num-order` feature), mirroring `FBig`'s surface.
2//!
3//! `NumOrd` agrees with the lexicographic [`Ord`](crate::cbig::CBig) (by real, then imaginary).
4//! `NumHash` mirrors the `num-order` crate's `Complex<f32>`/`Complex<f64>` hashing: the number is
5//! treated as `a + b·i` and the per-part residues are combined algebraically into a single field
6//! element `a + bterm` (where `bterm = ∓PROOT²·b²`, sign of `b`), rather than hashing the parts
7//! sequentially. This keeps a `CBig` and a `num-complex` `Complex` of the same value in sync.
8//! Consistency relies on `dashu-float`'s `Repr` residue equalling num-order's `f64` `fhash` for the
9//! same finite value.
10
11use crate::cbig::CBig;
12use crate::cmp::lex_cmp;
13use _num_modular::{FixedMersenneInt, ModularInteger};
14use core::cmp::Ordering;
15use core::hash::Hasher;
16use dashu_float::round::Round;
17use dashu_int::Word;
18use num_order::{NumHash, NumOrd};
19
20/// The *bterm* in num-order's `Complex<f64>` NumHash: `∓PROOT²·b²` (sign of `b`).
21#[inline]
22fn bterm(b: i128) -> i128 {
23    type MInt = FixedMersenneInt<127, 1>;
24    const M127U: u128 = i128::MAX as u128;
25    const PROOT: u128 = i32::MAX as u128;
26
27    if b >= 0 {
28        let pb = MInt::new(b as u128, &M127U) * PROOT;
29        -((pb * pb).residue() as i128)
30    } else {
31        let pb = MInt::new((-b) as u128, &M127U) * PROOT;
32        (pb * pb).residue() as i128
33    }
34}
35
36impl<R1: Round, R2: Round, const B: Word> NumOrd<CBig<R2, B>> for CBig<R1, B> {
37    #[inline]
38    fn num_cmp(&self, other: &CBig<R2, B>) -> Ordering {
39        lex_cmp(&self.re, &self.im, &other.re, &other.im)
40    }
41
42    #[inline]
43    fn num_partial_cmp(&self, other: &CBig<R2, B>) -> Option<Ordering> {
44        Some(self.num_cmp(other))
45    }
46}
47
48impl<R: Round, const B: Word> NumHash for CBig<R, B> {
49    fn num_hash<H: Hasher>(&self, state: &mut H) {
50        // Mirror num-order's `Complex<f64>` NumHash: z = a + b·i, hash(a + bterm).
51        let a = self.re().num_hash_residue();
52        let b = self.im().num_hash_residue();
53        a.wrapping_add(bterm(b)).num_hash(state)
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60    use dashu_float::round::mode;
61
62    type C = CBig<mode::HalfAway, 10>;
63
64    #[test]
65    fn num_ord_agrees_with_ord() {
66        let a = C::from_parts(1.into(), 9.into());
67        let b = C::from_parts(2.into(), 0.into());
68        assert_eq!(a.num_cmp(&b), a.cmp(&b));
69        assert!(a.num_lt(&b));
70    }
71
72    #[test]
73    fn num_hash_consistent_with_eq() {
74        fn hash_of<T: NumHash>(v: &T) -> u64 {
75            use std::hash::DefaultHasher;
76            let mut h = DefaultHasher::new();
77            v.num_hash(&mut h);
78            std::hash::Hasher::finish(&h)
79        }
80        let a = C::from_parts(3.into(), 4.into());
81        let b = C::from_parts(3.into(), 4.into());
82        assert_eq!(hash_of(&a), hash_of(&b));
83    }
84
85    /// i128 residue a `NumHash` impl writes (captured via `Hasher::write_i128`).
86    fn residue<T: NumHash>(v: &T) -> i128 {
87        struct Collector(i128);
88        impl core::hash::Hasher for Collector {
89            fn write_i128(&mut self, v: i128) {
90                self.0 = v;
91            }
92            fn write(&mut self, _: &[u8]) {}
93            fn finish(&self) -> u64 {
94                0
95            }
96        }
97        let mut c = Collector(0);
98        v.num_hash(&mut c);
99        c.0
100    }
101
102    #[test]
103    fn cbig_num_hash_matches_num_complex() {
104        // The base-2 CBig residue must equal num-order's `Complex<f64>` hash. Uses
105        // `num_complex::Complex64` as the live reference — it delegates to num-order's actual
106        // `NumHash` implementation (not a manually-transcribed formula), so if num-order ever
107        // changes the hash algorithm the test automatically tracks it.
108        // Relies on dashu-float's Repr residue equalling f64's `fhash` — see float's
109        // `test_fbig_num_hash_matches_f64`.
110        use dashu_float::FBig;
111        use num_complex_v04::Complex64;
112        type CF = CBig<mode::Zero, 2>;
113
114        for (re, im) in [
115            (3.0_f64, 4.0),
116            (1.0, 0.0),
117            (0.0, 1.0),
118            (-2.0, 0.5),
119            (0.0, 0.0),
120            (1.5, -2.25),
121            (100.0, -0.0625),
122        ] {
123            let z = CF::from_parts(FBig::try_from(re).unwrap(), FBig::try_from(im).unwrap());
124            let expected = residue(&Complex64::new(re, im));
125            assert_eq!(
126                residue(&z),
127                expected,
128                "CBig num_hash disagrees with num-complex hash for {re}+{im}i"
129            );
130        }
131    }
132}
dashu_cmplx/third_party/num_order.rs

dashu_cmplx/third_party/
num_order.rs
