abstalg/
reduced_fractions.rs

1// Copyright (C) 2020 Miklos Maroti
2// Licensed under the MIT license (see LICENSE)
3
4use crate::*;
5use num::rational::Ratio;
6
7/// The field of rational numbers with arbitrary large values.
8pub const QQ: ReducedFractions<Integers> = ReducedFractions { base: Integers() };
9
10/// The field of fractions over the elements of an Euclidean domain. The
11/// elements are ratios where the numerator and denominator are relative
12/// primes and the denominator is normalized with respect to its associate
13/// class.
14#[derive(Clone, Debug)]
15pub struct ReducedFractions<A>
16where
17    A: EuclideanDomain,
18{
19    base: A,
20}
21
22impl<A> ReducedFractions<A>
23where
24    A: EuclideanDomain,
25{
26    /// Creates a new field of fractions over the given ring. The ring cannot
27    /// be trivial, that is one must be different from zero.
28    pub fn new(base: A) -> Self {
29        assert!(!base.is_zero(&base.one()));
30        Self { base }
31    }
32
33    /// Returns the base ring from which this field was created.
34    pub fn base(&self) -> &A {
35        &self.base
36    }
37
38    /// Takes an arbitrary ratio of elements and turns it into its normal form.
39    pub fn reduce(&self, elem: &Ratio<A::Elem>) -> Ratio<A::Elem> {
40        assert!(!self.base.is_zero(elem.denom()));
41        let gcd = self.base.gcd(elem.numer(), elem.denom());
42        let numer = self.base.quo(elem.numer(), &gcd);
43        let denom = self.base.quo(elem.denom(), &gcd);
44        let coef = self.base.associate_coef(&denom);
45        let (numer, denom) = if !self.base.is_one(&coef) {
46            (self.base.mul(&numer, &coef), self.base.mul(&denom, &coef))
47        } else {
48            (numer, denom)
49        };
50        Ratio::new_raw(numer, denom)
51    }
52}
53
54impl<A> Domain for ReducedFractions<A>
55where
56    A: EuclideanDomain,
57{
58    type Elem = Ratio<A::Elem>;
59
60    fn contains(&self, elem: &Self::Elem) -> bool {
61        self.base.relative_primes(elem.numer(), elem.denom())
62            && self.base.is_one(&self.base.associate_coef(elem.denom()))
63    }
64
65    fn equals(&self, elem1: &Self::Elem, elem2: &Self::Elem) -> bool {
66        self.base.equals(elem1.numer(), elem2.numer())
67            && self.base.equals(elem1.denom(), elem2.denom())
68    }
69}
70
71impl<A> Semigroup for ReducedFractions<A>
72where
73    A: EuclideanDomain,
74{
75    fn mul(&self, elem1: &Self::Elem, elem2: &Self::Elem) -> Self::Elem {
76        let elem = Self::Elem::new_raw(
77            self.base.mul(elem1.numer(), elem2.numer()),
78            self.base.mul(elem1.denom(), elem2.denom()),
79        );
80        self.reduce(&elem)
81    }
82}
83
84impl<A> Monoid for ReducedFractions<A>
85where
86    A: EuclideanDomain,
87{
88    fn one(&self) -> Self::Elem {
89        Self::Elem::new_raw(self.base.one(), self.base.one())
90    }
91
92    fn is_one(&self, elem: &Self::Elem) -> bool {
93        self.base.is_one(elem.numer()) && self.base.is_one(elem.denom())
94    }
95
96    fn try_inv(&self, elem: &Self::Elem) -> Option<Self::Elem> {
97        if self.invertible(elem) {
98            let elem = Self::Elem::new_raw(elem.denom().clone(), elem.numer().clone());
99            Some(self.reduce(&elem))
100        } else {
101            None
102        }
103    }
104
105    fn invertible(&self, elem: &Self::Elem) -> bool {
106        !self.base.is_zero(elem.numer())
107    }
108}
109
110impl<A> CommuntativeMonoid for ReducedFractions<A>
111where
112    A: EuclideanDomain,
113{
114    fn zero(&self) -> Self::Elem {
115        Self::Elem::new_raw(self.base.zero(), self.base.one())
116    }
117
118    fn add(&self, elem1: &Self::Elem, elem2: &Self::Elem) -> Self::Elem {
119        let elem = if self.base.equals(elem1.denom(), elem2.denom()) {
120            Self::Elem::new_raw(
121                self.base.add(elem1.numer(), elem2.numer()),
122                elem1.denom().clone(),
123            )
124        } else {
125            Self::Elem::new_raw(
126                self.base.add(
127                    &self.base.mul(elem1.numer(), elem2.denom()),
128                    &self.base.mul(elem1.denom(), elem2.numer()),
129                ),
130                self.base.mul(elem1.denom(), elem2.denom()),
131            )
132        };
133        self.reduce(&elem)
134    }
135}
136
137impl<A> AbelianGroup for ReducedFractions<A>
138where
139    A: EuclideanDomain,
140{
141    fn neg(&self, elem: &Self::Elem) -> Self::Elem {
142        Self::Elem::new_raw(self.base.neg(elem.numer()), elem.denom().clone())
143    }
144
145    fn times(&self, num: isize, elem: &Self::Elem) -> Self::Elem {
146        let elem = Self::Elem::new_raw(
147            AbelianGroup::times(&self.base, num, elem.numer()),
148            elem.denom().clone(),
149        );
150        self.reduce(&elem)
151    }
152}
153
154impl<A> SemiRing for ReducedFractions<A> where A: EuclideanDomain {}
155
156impl<A> UnitaryRing for ReducedFractions<A> where A: EuclideanDomain {}
157
158impl<A> Field for ReducedFractions<A>
159where
160    A: EuclideanDomain,
161{
162    fn inv(&self, elem: &Self::Elem) -> Self::Elem {
163        assert!(!self.base.is_zero(elem.numer()));
164        let numer = elem.denom();
165        let denom = elem.numer();
166        let coef = self.base.associate_coef(denom);
167        let (numer, denom) = if !self.base.is_one(&coef) {
168            (self.base.mul(numer, &coef), self.base.mul(denom, &coef))
169        } else {
170            (numer.clone(), denom.clone())
171        };
172        Ratio::new_raw(numer, denom)
173    }
174}
175
176#[cfg(test)]
177mod tests {
178    use super::*;
179
180    #[test]
181    fn ops() {
182        let field = ReducedFractions::new(I32);
183        for numer in -20..20 {
184            for denom in -20..20 {
185                if denom == 0 {
186                    continue;
187                }
188                let elem1 = Ratio::<i32>::new_raw(numer, denom);
189                assert_eq!(*elem1.numer(), numer);
190                assert_eq!(*elem1.denom(), denom);
191
192                let elem1 = field.reduce(&elem1);
193                let elem2 = Ratio::<i32>::new(numer, denom);
194                assert_eq!(elem1, elem2);
195
196                let elem2 = Ratio::<i32>::new(-2, 3);
197                assert_eq!(elem1 + elem2, field.add(&elem1, &elem2));
198                assert_eq!(elem1 * elem2, field.mul(&elem1, &elem2));
199                assert_eq!(elem1 / elem2, field.div(&elem1, &elem2));
200                if numer != 0 {
201                    assert_eq!(elem2 / elem1, field.div(&elem2, &elem1));
202                }
203
204                let elem2 = Ratio::<i32>::new(7, 5);
205                assert_eq!(elem1 + elem2, field.add(&elem1, &elem2));
206                assert_eq!(elem1 * elem2, field.mul(&elem1, &elem2));
207                assert_eq!(elem1 / elem2, field.div(&elem1, &elem2));
208                if numer != 0 {
209                    assert_eq!(elem2 / elem1, field.div(&elem2, &elem1));
210                }
211            }
212        }
213    }
214}
abstalg/reduced_fractions.rs

abstalg/
reduced_fractions.rs
