yui_core/abst/
euc_ring.rs

1// Euclidean Rings
2
3use std::ops::{Div, DivAssign, Rem, RemAssign};
4use crate::{Ring, RingOps};
5
6pub trait EucRingOps<T = Self>: 
7    RingOps<T> + 
8    Div<T, Output = T> +
9    for<'a> Div<&'a T, Output = T> +
10    Rem<T, Output = T> +
11    for<'a> Rem<&'a T, Output = T> +
12{}
13
14pub trait EucRing: 
15    Ring + 
16    EucRingOps + 
17    DivAssign +
18    for<'a> DivAssign<&'a Self> +
19    RemAssign + 
20    for<'a> RemAssign<&'a Self>
21where 
22    for<'a> &'a Self: EucRingOps<Self>,
23{
24    fn divides(&self, y: &Self) -> bool { 
25        !self.is_zero() && (y % self).is_zero()
26    }
27
28    fn gcd(x: &Self, y: &Self) -> Self {
29        if x.is_zero() && y.is_zero() { return Self::zero() }
30        if x.divides(y) { return x.clone() }
31        if y.divides(x) { return y.clone() }
32
33        let (mut x, mut y) = (x.clone(), y.clone());
34
35        while !y.is_zero() {
36            let r = &x % &y;
37            (x, y) = (y, r);
38        }
39
40        x.into_normalized()
41    }
42
43    fn gcdx(x: &Self, y: &Self) -> (Self, Self, Self) {
44        if x.is_zero() && y.is_zero() { return (Self::zero(), Self::zero(), Self::zero()) }
45        if x.divides(y) { return (x.clone(), Self::one(), Self::zero()) }
46        if y.divides(x) { return (y.clone(), Self::zero(), Self::one()) }
47
48        let (mut x,  mut y)  = (x.clone(), y.clone());
49        let (mut s0, mut s1) = (Self::one(),  Self::zero());
50        let (mut t0, mut t1) = (Self::zero(), Self::one() );
51
52        while !y.is_zero() {
53            let q = &x / &y;
54            let r = &x % &y;
55
56            (x, y) = (y, r);
57            (s1, s0) = (s0 - &q * &s1, s1);
58            (t1, t0) = (t0 - &q * &t1, t1);
59        }
60
61        let (d, s, t) = (x, s0, t0);
62        
63        let u = d.normalizing_unit();
64        match u.is_one() { 
65            true  => (d, s, t),
66            false => (d * &u, s * &u, t * &u)
67        }
68    }
69
70    fn lcm(x: &Self, y: &Self) -> Self { 
71        let g = Self::gcd(x, y);
72        let m = x * (y / g);
73        m.into_normalized()
74    }
75}
yui_core/abst/euc_ring.rs

yui_core/abst/
euc_ring.rs
