ospf_rust_math/algebra/operator/algorithmic/
gcd_lcm.rs

1use std::ops::{Div, Mul};
2
3use paste::paste;
4
5pub use crate::algebra::ordinary::gcd::*;
6
7pub trait GcdLcm: Sized {
8    type Output;
9
10    fn gcd(self, rhs: Self) -> Self::Output;
11    fn gcd_list(values: &[Self]) -> Self::Output;
12
13    fn lcm(self, rhs: Self) -> Self::Output;
14    fn lcm_list(values: &[Self]) -> Self::Output;
15
16    fn gcd_lcm(self, rhs: Self) -> (Self::Output, Self::Output);
17    fn gcd_lcm_list(values: &[Self]) -> (Self::Output, Self::Output);
18}
19
20pub fn gcd<T: GcdLcm>(lhs: T, rhs: T) -> T::Output {
21    lhs.gcd(rhs)
22}
23
24pub fn gcd_list<T: GcdLcm>(values: &[T]) -> T::Output {
25    T::gcd_list(values)
26}
27
28pub fn lcm<T: GcdLcm>(lhs: T, rhs: T) -> T::Output {
29    lhs.lcm(rhs)
30}
31
32pub fn lcm_list<T: GcdLcm>(values: &[T]) -> T::Output {
33    T::lcm_list(values)
34}
35
36pub fn gcd_lcm<T: GcdLcm>(lhs: T, rhs: T) -> (T::Output, T::Output) {
37    lhs.gcd_lcm(rhs)
38}
39
40pub fn gcd_lcm_list<T: GcdLcm>(values: &[T]) -> (T::Output, T::Output) {
41    T::gcd_lcm_list(values)
42}
43
44macro_rules! gcd_template {
45    ($type:ident, $gcd:ident) => {
46        impl GcdLcm for $type {
47            type Output = $type;
48
49            paste! {
50                fn gcd(self, rhs: $type) -> $type {
51                    [<$gcd "_" $type>](self.clone(), rhs.clone())
52                }
53            }
54
55            fn gcd_list(values: &[$type]) -> $type {
56                todo!()
57            }
58
59            fn lcm(self, rhs: $type) -> $type {
60                let this_gcd = (&self).gcd(&rhs);
61                self * (rhs / this_gcd)
62            }
63
64            fn lcm_list(values: &[$type]) -> $type {
65                let this_gcd = Self::gcd_list(values);
66                let this_lcm = values
67                    .iter()
68                    .fold(this_gcd.clone(), |acc, x| acc * (x / &this_gcd));
69                this_lcm
70            }
71
72            fn gcd_lcm(self, rhs: $type) -> ($type, $type) {
73                let this_gcd = (&self).gcd(&rhs);
74                let this_lcm = self * (rhs / &this_gcd);
75                (this_gcd, this_lcm)
76            }
77
78            fn gcd_lcm_list(values: &[$type]) -> ($type, $type) {
79                let this_gcd = Self::gcd_list(values);
80                let this_lcm = values
81                    .iter()
82                    .fold(this_gcd.clone(), |acc, x| acc * (x / &this_gcd));
83                (this_gcd, this_lcm)
84            }
85        }
86
87        impl GcdLcm for &$type {
88            type Output = $type;
89
90            paste! {
91                fn gcd(self, rhs: &$type) -> $type {
92                    [<$gcd _ $type>]((*self).clone(), (*rhs).clone())
93                }
94            }
95
96            fn gcd_list(values: &[Self]) -> $type {
97                todo!()
98            }
99
100            fn lcm(self, rhs: &$type) -> $type {
101                let this_gcd = self.gcd(rhs);
102                self * (rhs / &this_gcd)
103            }
104
105            fn lcm_list(values: &[Self]) -> $type {
106                let this_gcd = Self::gcd_list(values);
107                let this_lcm = values
108                    .iter()
109                    .fold(this_gcd.clone(), |acc, x| acc * (*x / &this_gcd));
110                this_lcm
111            }
112
113            fn gcd_lcm(self, rhs: &$type) -> ($type, $type) {
114                let this_gcd = self.gcd(rhs);
115                let this_lcm = self * (rhs / &this_gcd);
116                (this_gcd, this_lcm)
117            }
118
119            fn gcd_lcm_list(values: &[Self]) -> ($type, $type) {
120                let this_gcd = Self::gcd_list(values);
121                let this_lcm = values
122                    .iter()
123                    .fold(this_gcd.clone(), |acc, x| acc * (*x / &this_gcd));
124                (this_gcd, this_lcm)
125            }
126        }
127    };
128}
129
130macro_rules! small_gcd_template {
131    ($($type:ident)*) => ($(
132        gcd_template!($type, gcd_euclid);
133    )*)
134}
135small_gcd_template! { i8 i16 i32 u8 u16 u32 }
136
137macro_rules! floating_gcd_template {
138    ($($type:ident)*) => ($(
139        gcd_template!($type, gcd_euclid);
140    )*)
141}
142floating_gcd_template! { f32 f64 }
143
144macro_rules! big_gcd_template {
145    ($($type:ident)*) => ($(
146        gcd_template!($type, gcd_stein);
147    )*)
148}
149big_gcd_template! { i64 i128 isize u64 u128 usize }
150
151#[cfg(test)]
152mod tests {
153    use std::fmt::Debug;
154
155    use crate::algebra::concept::RealNumber;
156
157    use super::*;
158
159    fn test_real<T: RealNumber + GcdLcm<Output=T> + Debug>()
160    where
161            for<'a> &'a T: Mul<&'a T, Output = T> + GcdLcm<Output=T>,
162    {
163        assert_eq!(&(T::TWO.gcd(T::FIVE)), T::ONE);
164        assert_eq!(&(T::TEN.gcd(&(T::TWO * T::TWO))), T::TWO);
165        assert_eq!(&(T::TEN.gcd(&(T::FIVE * T::FIVE))), T::FIVE);
166
167        assert_eq!(&(T::TWO.lcm(T::FIVE)), T::TEN);
168        assert_eq!(&(T::TEN.lcm(&T::TWO)), T::TEN);
169        assert_eq!(&(T::TEN.lcm(&(T::TWO * T::TWO))), &(T::TEN * T::TWO));
170        assert_eq!(&(T::TEN.lcm(&T::FIVE)), T::TEN);
171        assert_eq!(&(T::TWO.lcm(&(T::FIVE * T::FIVE))), &(T::TEN * T::FIVE));
172    }
173
174    #[test]
175    fn test() {
176        test_real::<i8>();
177        test_real::<i16>();
178        test_real::<i32>();
179        test_real::<i64>();
180        test_real::<i128>();
181        test_real::<u8>();
182        test_real::<u16>();
183        test_real::<u32>();
184        test_real::<u64>();
185        test_real::<u128>();
186        test_real::<f32>();
187        test_real::<f64>();
188    }
189}
ospf_rust_math/algebra/operator/algorithmic/gcd_lcm.rs

ospf_rust_math/algebra/operator/algorithmic/
gcd_lcm.rs
