relp_num/rational/small/ops/
mod.rs

1use std::cmp::Ordering;
2use std::iter::Sum;
3use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};
4use std::ops::Neg;
5
6use crate::Negateable;
7use crate::non_zero::NonZero;
8use crate::non_zero::NonZeroSign;
9use crate::rational::small::{Rational128, Rational16, Rational32, Rational64, Rational8, RationalUsize};
10use crate::rational::small::{NonZeroRational128, NonZeroRational16, NonZeroRational32, NonZeroRational64, NonZeroRational8, NonZeroRationalUsize};
11use crate::rational::small::ops::building_blocks::{add128, add16, add32, add64, add8, add_usize};
12use crate::rational::small::ops::building_blocks::{sub128, sub16, sub32, sub64, sub8, sub_usize};
13use crate::rational::small::ops::building_blocks::{mul128, mul16, mul32, mul64, mul8, mul_usize};
14use crate::rational::small::ops::building_blocks::SignChange;
15use crate::sign::Sign;
16
17pub(crate) mod building_blocks;
18mod with_int;
19mod with_one;
20mod with_zero;
21
22#[cfg(test)]
23mod test;
24
25macro_rules! rational {
26    ($name:ident, $add_name:ident, $sub_name:ident, $mul_name:ident) => {
27        impl AddAssign<&$name> for $name {
28            #[inline]
29            fn add_assign(&mut self, rhs: &Self) {
30                match (self.sign, rhs.sign) {
31                    (Sign::Positive, Sign::Positive) | (Sign::Negative, Sign::Negative) => {
32                        $add_name(
33                            &mut self.numerator,
34                            &mut self.denominator,
35                            rhs.numerator,
36                            rhs.denominator,
37                        )
38                    }
39                    (Sign::Positive, Sign::Negative) | (Sign::Negative, Sign::Positive) => {
40                        let sign_change = $sub_name(
41                            &mut self.numerator,
42                            &mut self.denominator,
43                            rhs.numerator,
44                            rhs.denominator,
45                        );
46                        match sign_change {
47                            SignChange::None => {}
48                            SignChange::Flip => self.sign.negate(),
49                            SignChange::Zero => self.sign = Sign::Zero,
50                        }
51                    }
52                    (_, Sign::Zero) => {},
53                    (Sign::Zero, _) => {
54                        *self = Self {
55                            sign: rhs.sign,
56                            numerator: rhs.numerator,
57                            denominator: rhs.denominator,
58                        };
59                    },
60                }
61            }
62        }
63
64        impl SubAssign<&$name> for $name {
65            #[inline]
66            fn sub_assign(&mut self, rhs: &Self) {
67                match (self.sign, rhs.sign) {
68                    (Sign::Positive, Sign::Positive) | (Sign::Negative, Sign::Negative) => {
69                        let sign_change = $sub_name(
70                            &mut self.numerator,
71                            &mut self.denominator,
72                            rhs.numerator,
73                            rhs.denominator,
74                        );
75                        match sign_change {
76                            SignChange::None => {}
77                            SignChange::Flip => self.sign.negate(),
78                            SignChange::Zero => self.sign = Sign::Zero,
79                        }
80                    }
81                    (Sign::Positive, Sign::Negative) | (Sign::Negative, Sign::Positive) => {
82                        $add_name(
83                            &mut self.numerator,
84                            &mut self.denominator,
85                            rhs.numerator,
86                            rhs.denominator,
87                        )
88                    }
89                    (_, Sign::Zero) => {}
90                    (Sign::Zero, _) => {
91                        *self = Self {
92                            sign: !rhs.sign,
93                            numerator: rhs.numerator,
94                            denominator: rhs.denominator,
95                        };
96                    }
97                }
98            }
99        }
100
101        impl Sum for $name {
102            fn sum<I: Iterator<Item=Self>>(mut iter: I) -> Self {
103                let first_value = iter.next();
104                match first_value {
105                    None => <Self as num_traits::Zero>::zero(),
106                    Some(mut total) => {
107
108                        while let Some(next_value) = iter.next() {
109                            total += next_value;
110                        }
111
112                        total
113                    }
114                }
115            }
116        }
117
118        impl MulAssign<&$name> for $name {
119            #[inline]
120            fn mul_assign(&mut self, rhs: &Self) {
121                match (self.sign, rhs.sign) {
122                    (Sign::Positive | Sign::Negative, Sign::Positive | Sign::Negative) => {
123                        self.sign *= rhs.sign;
124                        $mul_name(&mut self.numerator, &mut self.denominator, rhs.numerator, rhs.denominator);
125                    }
126                    (Sign::Zero, _) => {}
127                    (_, Sign::Zero) => <Self as num_traits::Zero>::set_zero(self),
128                }
129            }
130        }
131
132        // The sign of a quotient is the product of the signs, so `*` is correct here.
133        #[allow(clippy::suspicious_arithmetic_impl)]
134        impl Div<$name> for &$name {
135            type Output = $name;
136
137            #[inline]
138            fn div(self, mut rhs: $name) -> Self::Output {
139                match (self.sign, rhs.sign) {
140                    (Sign::Positive | Sign::Negative, Sign::Positive | Sign::Negative) => {
141                        let sign = self.sign * rhs.sign;
142                        $mul_name(&mut rhs.numerator, &mut rhs.denominator, self.denominator, self.numerator);
143                        Self::Output {
144                            sign,
145                            numerator: rhs.denominator,
146                            denominator: rhs.numerator,
147                        }
148                    }
149                    (_, Sign::Zero) => panic!(),
150                    (Sign::Zero, _) => {
151                        <$name as num_traits::Zero>::set_zero(&mut rhs);
152                        rhs
153                    }
154                }
155            }
156        }
157
158        // The sign of a quotient is the product of the signs, so `*` is correct here.
159        #[allow(clippy::suspicious_op_assign_impl)]
160        impl DivAssign<&$name> for $name {
161            #[inline]
162            fn div_assign(&mut self, rhs: &Self) {
163                match (self.sign, rhs.sign) {
164                    (Sign::Positive | Sign::Negative, Sign::Positive | Sign::Negative) => {
165                        self.sign *= rhs.sign;
166                        $mul_name(&mut self.numerator, &mut self.denominator, rhs.denominator, rhs.numerator);
167                    }
168                    (_, Sign::Zero) => panic!(),
169                    (Sign::Zero, _) => {}
170                }
171            }
172        }
173    }
174}
175
176rational!(Rational8, add8, sub8, mul8);
177rational!(Rational16, add16, sub16, mul16);
178rational!(Rational32, add32, sub32, mul32);
179rational!(Rational64, add64, sub64, mul64);
180rational!(Rational128, add128, sub128, mul128);
181rational!(RationalUsize, add_usize, sub_usize, mul_usize);
182
183macro_rules! rational_non_zero {
184    ($name:ident, $add_name:ident, $sub_name:ident, $mul_name:ident) => {
185        impl AddAssign<&$name> for $name {
186            #[inline]
187            fn add_assign(&mut self, rhs: &Self) {
188                match (self.sign, rhs.sign) {
189                    (NonZeroSign::Positive, NonZeroSign::Positive) | (NonZeroSign::Negative, NonZeroSign::Negative) => {
190                        $add_name(
191                            &mut self.numerator,
192                            &mut self.denominator,
193                            rhs.numerator,
194                            rhs.denominator,
195                        )
196                    }
197                    (NonZeroSign::Positive, NonZeroSign::Negative) | (NonZeroSign::Negative, NonZeroSign::Positive) => {
198                        let sign_change = $sub_name(
199                            &mut self.numerator,
200                            &mut self.denominator,
201                            rhs.numerator,
202                            rhs.denominator,
203                        );
204                        match sign_change {
205                            SignChange::None => {}
206                            SignChange::Flip => self.sign.negate(),
207                            // Adding opposite signs subtracts the magnitudes, which can cancel
208                            // exactly. That is not an overflow: the result is zero, which this
209                            // type deliberately cannot represent.
210                            SignChange::Zero => panic!(concat!(
211                                "the result of this addition is zero, which ", stringify!($name),
212                                " cannot represent",
213                            )),
214                        }
215                    }
216                }
217            }
218        }
219        impl SubAssign<&$name> for $name {
220            #[inline]
221            fn sub_assign(&mut self, rhs: &Self) {
222                match (self.sign, rhs.sign) {
223                    (NonZeroSign::Positive, NonZeroSign::Positive) | (NonZeroSign::Negative, NonZeroSign::Negative) => {
224                        let sign_change = $sub_name(
225                            &mut self.numerator,
226                            &mut self.denominator,
227                            rhs.numerator,
228                            rhs.denominator,
229                        );
230                        match sign_change {
231                            SignChange::None => {}
232                            SignChange::Flip => self.sign.negate(),
233                            // Equal values subtract to zero, which this type cannot represent.
234                            SignChange::Zero => panic!(concat!(
235                                "the result of this subtraction is zero, which ", stringify!($name),
236                                " cannot represent",
237                            )),
238                        }
239                    }
240                    (NonZeroSign::Positive, NonZeroSign::Negative) | (NonZeroSign::Negative, NonZeroSign::Positive) => {
241                        $add_name(
242                            &mut self.numerator,
243                            &mut self.denominator,
244                            rhs.numerator,
245                            rhs.denominator,
246                        )
247                    }
248                }
249            }
250        }
251        impl MulAssign<&$name> for $name {
252            #[inline]
253            fn mul_assign(&mut self, rhs: &Self) {
254                self.sign *= rhs.sign;
255                $mul_name(&mut self.numerator, &mut self.denominator, rhs.numerator, rhs.denominator);
256            }
257        }
258        // The sign of a quotient is the product of the signs, so `*` is correct here.
259        #[allow(clippy::suspicious_arithmetic_impl)]
260        impl Div<$name> for &$name {
261            type Output = $name;
262
263            #[inline]
264            fn div(self, mut rhs: $name) -> Self::Output {
265                let sign = self.sign * rhs.sign;
266                $mul_name(&mut rhs.numerator, &mut rhs.denominator, self.denominator, self.numerator);
267                Self::Output {
268                    sign,
269                    numerator: rhs.denominator,
270                    denominator: rhs.numerator,
271                }
272            }
273        }
274        // The sign of a quotient is the product of the signs, so `*` is correct here.
275        #[allow(clippy::suspicious_op_assign_impl)]
276        impl DivAssign<&$name> for $name {
277            #[inline]
278            fn div_assign(&mut self, rhs: &Self) {
279                self.sign *= rhs.sign;
280                $mul_name(&mut self.numerator, &mut self.denominator, rhs.denominator, rhs.numerator);
281            }
282        }
283
284        impl Neg for $name {
285            type Output = Self;
286
287            #[inline]
288            fn neg(mut self) -> Self::Output {
289                self.sign.negate();
290                self
291            }
292        }
293
294        impl Neg for &$name {
295            type Output = $name;
296
297            #[inline]
298            fn neg(self) -> Self::Output {
299                Self::Output {
300                    sign: !self.sign,
301                    numerator: self.numerator,
302                    denominator: self.denominator,
303                }
304            }
305        }
306    }
307}
308rational_non_zero!(NonZeroRational8, add8, sub8, mul8);
309rational_non_zero!(NonZeroRational16, add16, sub16, mul16);
310rational_non_zero!(NonZeroRational32, add32, sub32, mul32);
311rational_non_zero!(NonZeroRational64, add64, sub64, mul64);
312rational_non_zero!(NonZeroRational128, add128, sub128, mul128);
313rational_non_zero!(NonZeroRationalUsize, add_usize, sub_usize, mul_usize);
314
315/// Compare two ratios by cross multiplication.
316///
317/// `$widening_mul` computes the exact product of two magnitudes as a tuple that orders like the
318/// number it represents: the most significant half first. Comparing the two tuples
319/// lexicographically therefore compares `a * d` against `b * c` exactly, which is the comparison
320/// of `a / b` against `c / d` because both denominators are positive.
321macro_rules! rational_ord {
322    ($name:ident, $sign:ident, $widening_mul:expr) => {
323        impl PartialOrd for $name {
324            #[inline]
325            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
326                Some(self.cmp(other))
327            }
328        }
329
330        impl Ord for $name {
331            #[inline]
332            #[allow(unreachable_patterns)]
333            fn cmp(&self, other: &Self) -> Ordering {
334                match self.sign.cmp(&other.sign) {
335                    Ordering::Less => return Ordering::Less,
336                    Ordering::Greater => return Ordering::Greater,
337                    // Both zero, or both nonzero with the same sign; compare the magnitudes.
338                    Ordering::Equal => {}
339                }
340
341                if !self.sign.is_not_zero() {
342                    // Equal signs and the sign is zero, so both values are zero.
343                    return Ordering::Equal;
344                }
345
346                let widening_mul = $widening_mul;
347
348                let ad = widening_mul(self.numerator, other.denominator);
349                let bc = widening_mul(self.denominator, other.numerator);
350
351                match (ad.cmp(&bc), self.sign) {
352                    (Ordering::Less, $sign::Positive) | (Ordering::Greater, $sign::Negative) => Ordering::Less,
353                    (Ordering::Equal, _) => Ordering::Equal,
354                    (Ordering::Greater, $sign::Positive) | (Ordering::Less, $sign::Negative) => Ordering::Greater,
355                    _ => unreachable!("sign was checked to be nonzero"),
356                }
357            }
358        }
359    }
360}
361
362/// Order a ratio by cross multiplying its magnitudes.
363///
364/// The two products are the `(high, low)` pairs [`carrying_mul`](u64::carrying_mul) returns: with
365/// a zero carry it is a widening multiply, which every width has, including the widest one, where
366/// no doubled width integer exists to widen into.
367///
368/// Comparing by the continued fraction expansion of the two ratios would avoid the wide product
369/// altogether, but it costs a division per term of the expansion rather than a single
370/// multiplication, and the number of terms is not bounded by anything better than the width.
371macro_rules! rational_cross_multiplying_ord {
372    ($name:ident, $uty:ty, $sign:ident) => {
373        rational_ord!($name, $sign, |left: $uty, right: $uty| {
374            // `carrying_mul` returns the low half first.
375            let (low, high) = left.carrying_mul(right, 0);
376            (high, low)
377        });
378    }
379}
380
381rational_cross_multiplying_ord!(Rational8, u8, Sign);
382rational_cross_multiplying_ord!(Rational16, u16, Sign);
383rational_cross_multiplying_ord!(Rational32, u32, Sign);
384rational_cross_multiplying_ord!(Rational64, u64, Sign);
385rational_cross_multiplying_ord!(RationalUsize, usize, Sign);
386rational_cross_multiplying_ord!(Rational128, u128, Sign);
387rational_cross_multiplying_ord!(NonZeroRational8, u8, NonZeroSign);
388rational_cross_multiplying_ord!(NonZeroRational16, u16, NonZeroSign);
389rational_cross_multiplying_ord!(NonZeroRational32, u32, NonZeroSign);
390rational_cross_multiplying_ord!(NonZeroRational64, u64, NonZeroSign);
391rational_cross_multiplying_ord!(NonZeroRationalUsize, usize, NonZeroSign);
392rational_cross_multiplying_ord!(NonZeroRational128, u128, NonZeroSign);
393
394macro_rules! rational_forward {
395    ($name:ident) => {
396        impl<'a> Add<&'a $name> for &'a $name {
397            type Output = $name;
398
399            #[inline]
400            fn add(self, rhs: Self) -> Self::Output {
401                Add::add(self.clone(), rhs)
402            }
403        }
404
405        impl Add for $name {
406            type Output = Self;
407
408            #[inline]
409            fn add(mut self, rhs: Self) -> Self::Output {
410                AddAssign::add_assign(&mut self, rhs);
411                self
412            }
413        }
414
415        impl Add<&$name> for $name {
416            type Output = Self;
417
418            #[inline]
419            fn add(mut self, rhs: &Self) -> Self::Output {
420                AddAssign::add_assign(&mut self, rhs);
421                self
422            }
423        }
424
425        impl Add<$name> for &$name {
426            type Output = $name;
427
428            #[inline]
429            fn add(self, rhs: $name) -> Self::Output {
430                Add::add(rhs, self)
431            }
432        }
433
434        impl AddAssign for $name {
435            #[inline]
436            fn add_assign(&mut self, rhs: Self) {
437                AddAssign::add_assign(self, &rhs);
438            }
439        }
440
441        impl Sub for $name {
442            type Output = Self;
443
444            #[inline]
445            fn sub(mut self, rhs: Self) -> Self::Output {
446                SubAssign::sub_assign(&mut self, rhs);
447                self
448            }
449        }
450
451        impl<'a> Sub<&'a $name> for &'a $name {
452            type Output = $name;
453
454            #[inline]
455            fn sub(self, rhs: Self) -> Self::Output {
456                Sub::sub(self.clone(), rhs)
457            }
458        }
459
460        impl Sub<&$name> for $name {
461            type Output = Self;
462
463            #[inline]
464            fn sub(mut self, rhs: &Self) -> Self::Output {
465                SubAssign::sub_assign(&mut self, rhs);
466                self
467            }
468        }
469
470        impl Sub<$name> for &$name {
471            type Output = $name;
472
473            #[inline]
474            fn sub(self, rhs: $name) -> Self::Output {
475                -Sub::sub(rhs, self)
476            }
477        }
478
479        impl SubAssign for $name {
480            #[inline]
481            fn sub_assign(&mut self, rhs: Self) {
482                SubAssign::sub_assign(self, &rhs)
483            }
484        }
485
486        impl Mul<&$name> for $name {
487            type Output = Self;
488
489            #[inline]
490            fn mul(mut self, rhs: &Self) -> Self::Output {
491                MulAssign::mul_assign(&mut self, rhs);
492                self
493            }
494        }
495
496        impl<'a> Mul<&'a $name> for &'a $name {
497            type Output = $name;
498
499            #[inline]
500            fn mul(self, rhs: Self) -> Self::Output {
501                Mul::mul(self.clone(), rhs)
502            }
503        }
504
505        impl Mul for $name {
506            type Output = Self;
507
508            #[inline]
509            fn mul(mut self, rhs: Self) -> Self::Output {
510                MulAssign::mul_assign(&mut self, rhs);
511                self
512            }
513        }
514
515        impl MulAssign for $name {
516            #[inline]
517            fn mul_assign(&mut self, rhs: Self) {
518                MulAssign::mul_assign(self, &rhs);
519            }
520        }
521
522        impl Mul<$name> for &$name {
523            type Output = $name;
524
525            #[inline]
526            fn mul(self, rhs: $name) -> Self::Output {
527                Mul::mul(rhs, self)
528            }
529        }
530
531        impl Div for $name {
532            type Output = Self;
533
534            #[inline]
535            fn div(mut self, rhs: Self) -> Self::Output {
536                DivAssign::div_assign(&mut self, rhs);
537                self
538            }
539        }
540
541        impl Div<&$name> for $name {
542            type Output = Self;
543
544            #[inline]
545            fn div(mut self, rhs: &Self) -> Self::Output {
546                DivAssign::div_assign(&mut self, rhs);
547                self
548            }
549        }
550
551        impl<'a> Div<&'a $name> for &'a $name {
552            type Output = $name;
553
554            #[inline]
555            fn div(self, rhs: Self) -> Self::Output {
556                Div::div(self.clone(), rhs)
557            }
558        }
559
560        impl DivAssign for $name {
561            #[inline]
562            fn div_assign(&mut self, rhs: Self) {
563                DivAssign::div_assign(self, &rhs);
564            }
565        }
566    }
567}
568
569rational_forward!(Rational8);
570rational_forward!(Rational16);
571rational_forward!(Rational32);
572rational_forward!(Rational64);
573rational_forward!(Rational128);
574rational_forward!(RationalUsize);
575rational_forward!(NonZeroRational8);
576rational_forward!(NonZeroRational16);
577rational_forward!(NonZeroRational32);
578rational_forward!(NonZeroRational64);
579rational_forward!(NonZeroRational128);
580rational_forward!(NonZeroRationalUsize);
581
582#[cfg(test)]
583mod order_test {
584    use std::cmp::Ordering;
585
586    use crate::{Field, OrderedField};
587    use crate::non_zero::NonZeroSign;
588    use crate::rational::Ratio;
589    use crate::rational::small::{NonZeroRational128, NonZeroRationalUsize, Rational128, RationalUsize};
590    use crate::sign::Sign;
591
592    /// Build a value directly, to reach magnitudes that the `new` constructors can't take.
593    ///
594    /// The caller is responsible for the invariants: lowest terms, nonzero denominator and a sign
595    /// that is zero exactly when the numerator is.
596    fn ratio128(sign: Sign, numerator: u128, denominator: u128) -> Rational128 {
597        Ratio { sign, numerator, denominator }
598    }
599
600    fn ratio_usize(sign: Sign, numerator: usize, denominator: usize) -> RationalUsize {
601        Ratio { sign, numerator, denominator }
602    }
603
604    /// The widest types used to have no total order, and so were not fields either.
605    #[test]
606    fn test_ordered_field() {
607        fn assert_field<T: Field>() {}
608        fn assert_ordered_field<T: OrderedField>() {}
609        fn assert_ord<T: Ord>() {}
610
611        assert_field::<Rational128>();
612        assert_ordered_field::<Rational128>();
613        assert_field::<RationalUsize>();
614        assert_ordered_field::<RationalUsize>();
615
616        assert_ord::<NonZeroRational128>();
617        assert_ord::<NonZeroRationalUsize>();
618
619        // `Abs` is implemented for ratios that are ordered.
620        assert_eq!(crate::Abs::abs(ratio128(Sign::Negative, u128::MAX, 2)), ratio128(Sign::Positive, u128::MAX, 2));
621        assert_eq!(crate::Abs::abs(ratio_usize(Sign::Negative, usize::MAX, 2)), ratio_usize(Sign::Positive, usize::MAX, 2));
622    }
623
624    /// All pairs and triples of a small range, against an exact `f64` reference.
625    #[test]
626    fn test_order_usize_brute_force() {
627        let mut values = Vec::new();
628        for numerator in -5_isize..=5 {
629            for denominator in 1_usize..=5 {
630                let value = RationalUsize::new(numerator, denominator).unwrap();
631                values.push((value, numerator as f64 / denominator as f64));
632            }
633        }
634
635        for &(left, left_float) in &values {
636            for &(right, right_float) in &values {
637                let expected = left_float.partial_cmp(&right_float).unwrap();
638
639                assert_eq!(left.cmp(&right), expected, "{:?} <=> {:?}", left, right);
640                assert_eq!(left.partial_cmp(&right), Some(expected));
641                // Antisymmetry.
642                assert_eq!(right.cmp(&left), expected.reverse(), "{:?} <=> {:?}", right, left);
643                // Agreement with `PartialEq`.
644                assert_eq!(left == right, expected == Ordering::Equal, "{:?} == {:?}", left, right);
645            }
646        }
647
648        // Transitivity.
649        for &(left, _) in &values {
650            for &(middle, _) in &values {
651                if left > middle {
652                    continue;
653                }
654
655                for &(right, _) in &values {
656                    if middle <= right {
657                        assert!(left <= right, "{:?} <= {:?} <= {:?}", left, middle, right);
658                    }
659                }
660            }
661        }
662    }
663
664    /// Products that don't fit a `usize`, which is why the comparison multiplies into a `u128`.
665    #[test]
666    fn test_order_usize_wide_product() {
667        // `(2 ^ (usize::BITS - 1) + 1) * 2` wraps to `2` in a `usize`, which is less than `1 * 3`,
668        // so a comparison that multiplies at the width of the type gets this pair backwards.
669        let large = ratio_usize(Sign::Positive, (1 << (usize::BITS - 1)) + 1, 1);
670        let small = ratio_usize(Sign::Positive, 3, 2);
671        assert!(large > small);
672        assert!(small < large);
673        assert!(-large < -small);
674
675        // The difference between these two is in the low half of the product.
676        let left = ratio_usize(Sign::Positive, usize::MAX, usize::MAX - 1);
677        let right = ratio_usize(Sign::Positive, usize::MAX - 1, usize::MAX - 2);
678        assert!(left < right);
679        assert!(right > left);
680        assert_eq!(left.cmp(&left), Ordering::Equal);
681        assert_eq!(right.cmp(&right), Ordering::Equal);
682        assert_eq!(left.cmp(&right).reverse(), right.cmp(&left));
683    }
684
685    /// Magnitudes above `u64::MAX`, whose products need more than the 128 bits of a `u128`.
686    #[test]
687    fn test_order_128_above_64_bits() {
688        // `(2 ^ 127 + 1) * 2` wraps to `2` in a `u128`, which is less than `1 * 3`.
689        let large = ratio128(Sign::Positive, (1 << 127) + 1, 1);
690        let small = ratio128(Sign::Positive, 3, 2);
691        assert!(large > small);
692        assert!(small < large);
693        assert!(-large < -small);
694
695        // `1 + 1 / 2 ^ 64` against `1 + 1 / (2 ^ 64 + 1)`; both cross products exceed a `u128`.
696        let left = ratio128(Sign::Positive, (1 << 64) + 1, 1 << 64);
697        let right = ratio128(Sign::Positive, (1 << 64) + 2, (1 << 64) + 1);
698        assert!(left > right);
699        assert!(right < left);
700
701        // The two products are `2 ^ 254 - 2 ^ 128` and `2 ^ 254 - 2 ^ 128 + 1`: they share their
702        // high 128 bits and differ in the last bit of the low half.
703        let left = ratio128(Sign::Positive, 1 << 127, (1 << 127) - 1);
704        let right = ratio128(Sign::Positive, (1 << 127) - 1, (1 << 127) - 2);
705        assert!(left < right);
706        assert!(right > left);
707        assert_eq!(left.cmp(&left), Ordering::Equal);
708        assert_eq!(left.cmp(&right).reverse(), right.cmp(&left));
709
710        // Large values that differ only in the last bit of the numerator.
711        let left = ratio128(Sign::Positive, u128::MAX, 2);
712        let right = ratio128(Sign::Positive, u128::MAX - 2, 2);
713        assert!(left > right);
714        assert!(-left < -right);
715    }
716
717    #[test]
718    fn test_order_128_signs() {
719        let zero = ratio128(Sign::Zero, 0, 1);
720        let positive = ratio128(Sign::Positive, u128::MAX, u128::MAX - 1);
721        let negative = ratio128(Sign::Negative, 1, u128::MAX);
722
723        assert_eq!(zero.cmp(&zero), Ordering::Equal);
724        assert_eq!(zero.cmp(&positive), Ordering::Less);
725        assert_eq!(positive.cmp(&zero), Ordering::Greater);
726        assert_eq!(zero.cmp(&negative), Ordering::Greater);
727        assert_eq!(negative.cmp(&zero), Ordering::Less);
728        assert_eq!(negative.cmp(&positive), Ordering::Less);
729        assert_eq!(positive.cmp(&negative), Ordering::Greater);
730        assert_eq!(positive.cmp(&positive), Ordering::Equal);
731        assert_eq!(negative.cmp(&negative), Ordering::Equal);
732
733        // Negation reverses the order of the magnitudes.
734        let left = ratio128(Sign::Negative, (1 << 100) + 1, (1 << 100) - 1);
735        let right = ratio128(Sign::Negative, (1 << 100) + 3, (1 << 100) - 1);
736        assert!(left > right);
737        assert!(-left < -right);
738    }
739
740    /// Compare `a / b` against `c / d` by their continued fraction expansions.
741    ///
742    /// This never computes a product, so it is independent of the implementation under test.
743    fn euclidean_cmp(mut a: u128, mut b: u128, mut c: u128, mut d: u128) -> Ordering {
744        let mut reversed = false;
745
746        loop {
747            let (left_quotient, left_remainder) = (a / b, a % b);
748            let (right_quotient, right_remainder) = (c / d, c % d);
749
750            let ordering = if left_quotient != right_quotient {
751                left_quotient.cmp(&right_quotient)
752            } else {
753                match (left_remainder == 0, right_remainder == 0) {
754                    (true, true) => Ordering::Equal,
755                    (true, false) => Ordering::Less,
756                    (false, true) => Ordering::Greater,
757                    (false, false) => {
758                        // Recurse on the reciprocals of the remainders, which flips the order.
759                        a = b;
760                        b = left_remainder;
761                        c = d;
762                        d = right_remainder;
763                        reversed = !reversed;
764                        continue;
765                    }
766                }
767            };
768
769            return if reversed { ordering.reverse() } else { ordering };
770        }
771    }
772
773    #[test]
774    fn test_order_128_against_continued_fractions() {
775        fn gcd(mut left: u128, mut right: u128) -> u128 {
776            while right != 0 {
777                let remainder = left % right;
778                left = right;
779                right = remainder;
780            }
781            left
782        }
783
784        // A linear congruential generator, so that the values are reproducible.
785        let mut state = 0x2545_f491_4f6c_dd1d_u64;
786        let mut next = || {
787            let mut value = 0_u128;
788            for _ in 0..2 {
789                state = state.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
790                value = (value << 64) | (state >> 1) as u128;
791            }
792            // Zero magnitudes are not representable in a nonzero ratio.
793            value.max(1)
794        };
795
796        for _ in 0..200 {
797            let (mut a, mut b, mut c, mut d) = (next(), next(), next(), next());
798            let (left_gcd, right_gcd) = (gcd(a, b), gcd(c, d));
799            a /= left_gcd;
800            b /= left_gcd;
801            c /= right_gcd;
802            d /= right_gcd;
803
804            let expected = euclidean_cmp(a, b, c, d);
805            let left = ratio128(Sign::Positive, a, b);
806            let right = ratio128(Sign::Positive, c, d);
807
808            assert_eq!(left.cmp(&right), expected, "{} / {} <=> {} / {}", a, b, c, d);
809            assert_eq!(right.cmp(&left), expected.reverse(), "{} / {} <=> {} / {}", c, d, a, b);
810            assert_eq!((-left).cmp(&-right), expected.reverse());
811            assert_eq!(left == right, expected == Ordering::Equal);
812        }
813    }
814
815    /// Small values of the widest type, against an exact `f64` reference.
816    #[test]
817    fn test_order_128_brute_force() {
818        let mut values = Vec::new();
819        for numerator in -5_i128..=5 {
820            for denominator in 1_u128..=5 {
821                let value = Rational128::new(numerator, denominator).unwrap();
822                values.push((value, numerator as f64 / denominator as f64));
823            }
824        }
825
826        for &(left, left_float) in &values {
827            for &(right, right_float) in &values {
828                let expected = left_float.partial_cmp(&right_float).unwrap();
829
830                assert_eq!(left.cmp(&right), expected, "{:?} <=> {:?}", left, right);
831                assert_eq!(right.cmp(&left), expected.reverse());
832                assert_eq!(left == right, expected == Ordering::Equal);
833            }
834        }
835    }
836
837    #[test]
838    fn test_order_non_zero() {
839        let left: NonZeroRational128 = Ratio { sign: NonZeroSign::Positive, numerator: (1 << 127) + 1, denominator: 1 };
840        let right: NonZeroRational128 = Ratio { sign: NonZeroSign::Positive, numerator: 3, denominator: 2 };
841        assert!(left > right);
842        assert!(-left < -right);
843
844        let left: NonZeroRationalUsize = Ratio { sign: NonZeroSign::Positive, numerator: usize::MAX, denominator: usize::MAX - 1 };
845        let right: NonZeroRationalUsize = Ratio { sign: NonZeroSign::Positive, numerator: usize::MAX - 1, denominator: usize::MAX - 2 };
846        assert!(left < right);
847        assert_eq!(left.cmp(&left), Ordering::Equal);
848        assert!(-left > -right);
849    }
850}
relp_num/rational/small/ops/mod.rs

relp_num/rational/small/ops/
mod.rs
