relp_num/rational/small/
gcd.rs

1//! # The greatest common divisor of two fixed width rationals
2//!
3//! The denominator of the answer is the least common multiple of the two denominators, which is
4//! larger than either of them, so this is the one place where a fixed width answer can fail to
5//! exist. It is reported rather than wrapped.
6use crate::rational::Ratio;
7use crate::rational::small::ops::building_blocks::{
8    gcd8, gcd16, gcd32, gcd64, gcd128, gcd_usize,
9};
10use crate::sign::Sign;
11use crate::traits::Gcd;
12use crate::{
13    Rational8, Rational16, Rational32, Rational64, Rational128, RationalUsize,
14};
15
16macro_rules! gcd_small {
17    ($($name:ty => $unsigned:ty, $gcd:ident);+ $(;)?) => {$(
18        impl Gcd for $name {
19            fn gcd(&self, other: &Self) -> Option<Self> {
20                // The routine below refuses one as an operand, which costs it an allocation in the
21                // arbitrary precision case and is answered here rather than there.
22                fn divisor(left: $unsigned, right: $unsigned) -> $unsigned {
23                    if left == 1 || right == 1 { 1 } else { $gcd(left, right) }
24                }
25
26                Some(match (self.sign, other.sign) {
27                    (Sign::Zero, Sign::Zero) => Ratio {
28                        sign: Sign::Zero,
29                        numerator: 0,
30                        denominator: 1,
31                    },
32                    // Zero is an integer multiple of every value, so the other one divides the
33                    // pair. Only its magnitude does the dividing.
34                    (Sign::Zero, _) => Ratio { sign: Sign::Positive, ..*other },
35                    (_, Sign::Zero) => Ratio { sign: Sign::Positive, ..*self },
36                    _ => {
37                        let shared = divisor(self.denominator, other.denominator);
38                        Ratio {
39                            sign: Sign::Positive,
40                            numerator: divisor(self.numerator, other.numerator),
41                            denominator: (self.denominator / shared)
42                                .checked_mul(other.denominator)?,
43                        }
44                    }
45                })
46            }
47        }
48    )+}
49}
50
51gcd_small!(
52    Rational8 => u8, gcd8;
53    Rational16 => u16, gcd16;
54    Rational32 => u32, gcd32;
55    Rational64 => u64, gcd64;
56    Rational128 => u128, gcd128;
57    RationalUsize => usize, gcd_usize;
58);
59
60#[cfg(test)]
61mod test {
62    use crate::{Gcd, Rational8, R8, R64};
63
64    #[test]
65    fn the_same_answers_as_the_wide_type() {
66        assert_eq!(R8!(4).gcd(&R8!(6)), Some(R8!(2)));
67        assert_eq!(R8!(1, 2).gcd(&R8!(1, 3)), Some(R8!(1, 6)));
68        assert_eq!(R8!(3, 4).gcd(&R8!(5, 6)), Some(R8!(1, 12)));
69        assert_eq!(R8!(-4).gcd(&R8!(6)), Some(R8!(2)));
70        assert_eq!(R8!(0).gcd(&R8!(0)), Some(R8!(0)));
71        assert_eq!(R8!(0).gcd(&R8!(-6)), Some(R8!(6)));
72        assert_eq!(R64!(9, 10).gcd(&R64!(6, 25)), Some(R64!(3, 50)));
73    }
74
75    /// The one case the wide type does not have.
76    #[test]
77    fn a_result_that_does_not_fit_is_reported() {
78        // 1/200 and 1/3 have 600 as the least common multiple of their denominators.
79        assert_eq!(R8!(1, 200).gcd(&R8!(1, 3)), None);
80        // The same pair fits once there is room for it.
81        assert_eq!(R64!(1, 200).gcd(&R64!(1, 3)), Some(R64!(1, 600)));
82    }
83
84    #[test]
85    fn dividing_by_it_leaves_coprime_integers() {
86        for (left, right) in [
87            (R8!(1, 2), R8!(1, 3)),
88            (R8!(3, 4), R8!(5, 6)),
89            (R8!(9), R8!(6)),
90        ] {
91            let divisor: Rational8 = left.gcd(&right).unwrap();
92            let one = left / divisor;
93            let other = right / divisor;
94
95            assert_eq!(one * divisor, left);
96            assert_eq!(other * divisor, right);
97            assert_eq!(one.gcd(&other), Some(R8!(1)));
98        }
99    }
100}
relp_num/rational/small/gcd.rs

relp_num/rational/small/
gcd.rs
