feanor_math/rings/fraction/
fraction_impl.rs

1use std::fmt::Debug;
2use std::fmt::Formatter;
3
4use crate::algorithms::eea::signed_gcd;
5use crate::algorithms::matmul::StrassenHint;
6use crate::algorithms::convolution::KaratsubaHint;
7use crate::homomorphism::*;
8use crate::divisibility::*;
9use crate::field::Field;
10use crate::homomorphism::Homomorphism;
11use crate::rings::rational::RationalFieldBase;
12use crate::integer::IntegerRing;
13use crate::pid::{EuclideanRing, PrincipalIdealRing};
14use crate::ring::*;
15
16use super::*;
17
18#[stability::unstable(feature = "enable")]
19pub struct FractionFieldImplBase<R>
20    where R: RingStore,
21        R::Type: Domain
22{
23    base_ring: R
24}
25
26///
27/// [`RingStore`] for [`FractionFieldImplBase`].
28/// 
29#[stability::unstable(feature = "enable")]
30pub type FractionFieldImpl<R> = RingValue<FractionFieldImplBase<R>>;
31
32pub struct FractionFieldEl<R>
33    where R: RingStore,
34        R::Type: Domain
35{
36    num: El<R>,
37    den: El<R>
38}
39
40impl<R> FractionFieldImpl<R>
41    where R: RingStore,
42        R::Type: Domain
43{
44    #[stability::unstable(feature = "enable")]
45    pub fn new(base_ring: R) -> Self {
46        assert!(base_ring.get_ring().is_commutative());
47        RingValue::from(FractionFieldImplBase { base_ring })
48    }
49}
50
51impl<R> FractionFieldImplBase<R>
52    where R: RingStore,
53        R::Type: Domain
54{
55    ///
56    /// Partially reduces the fraction; This should be considered only a performance
57    /// optimization, and does not give any reducedness-guarantees (since it only uses
58    /// `balance_factor()` instead of `ideal_gen()`).
59    /// 
60    /// # Implementation rationale
61    /// 
62    /// It seems likely that in many cases, fractions are actually elements of the base
63    /// ring (e.g. after rescaling a polynomial with [`FractionFieldImpl::balance_factor()`]).
64    /// Hence, we completely reduce elements in this case, using `checked_div()`. This should
65    /// still be much faster than a general gcd computation. In all other cases, just use 
66    /// `balance_factor()` of the base ring.
67    /// 
68    fn reduce(&self, el: &mut FractionFieldEl<R>) {
69        if let Some(quo) = self.base_ring.checked_div(&el.num, &el.den) {
70            el.num = quo;
71            el.den = self.base_ring.one();
72        } else if let Some(factor) = <_ as DivisibilityRing>::balance_factor(self.base_ring.get_ring(), [&el.num, &el.den].into_iter()) {
73            el.num = self.base_ring.checked_div(&el.num, &factor).unwrap();
74            el.den = self.base_ring.checked_div(&el.den, &factor).unwrap();
75        }
76    }
77}
78
79impl<R> Debug for FractionFieldEl<R>
80    where R: RingStore,
81        R::Type: Domain,
82        El<R>: Debug
83{
84    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
85        f.debug_struct("FractionFieldEl")
86            .field("num", &self.num)
87            .field("den", &self.den)
88            .finish()
89    }
90}
91
92impl<R> PartialEq for FractionFieldImplBase<R>
93    where R: RingStore,
94        R::Type: Domain
95{
96    fn eq(&self, other: &Self) -> bool {
97        self.base_ring.get_ring() == other.base_ring.get_ring()
98    }
99}
100
101impl<R> Clone for FractionFieldImplBase<R>
102    where R: RingStore + Clone,
103        R::Type: Domain
104{
105    fn clone(&self) -> Self {
106        Self {
107            base_ring: self.base_ring.clone()
108        }
109    }
110}
111
112impl<R> Copy for FractionFieldImplBase<R>
113    where R: RingStore + Copy,
114        R::Type: Domain,
115        El<R>: Copy
116{}
117
118impl<R> Clone for FractionFieldEl<R>
119    where R: RingStore,
120        R::Type: Domain,
121        El<R>: Clone
122{
123    fn clone(&self) -> Self {
124        Self {
125            num: self.num.clone(),
126            den: self.den.clone()
127        }
128    }
129}
130
131impl<R> Copy for FractionFieldEl<R>
132    where R: RingStore,
133        R::Type: Domain,
134        El<R>: Copy
135{}
136
137impl<R> RingBase for FractionFieldImplBase<R>
138    where R: RingStore,
139        R::Type: Domain
140{
141    type Element = FractionFieldEl<R>;
142
143    fn clone_el(&self, val: &Self::Element) -> Self::Element {
144        FractionFieldEl {
145            num: self.base_ring.clone_el(&val.num),
146            den: self.base_ring.clone_el(&val.den)
147        }
148    }
149    
150    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
151        self.base_ring.mul_assign_ref(&mut lhs.num, &rhs.den);
152        self.base_ring.add_assign(&mut lhs.num, self.base_ring.mul_ref(&lhs.den, &rhs.num));
153        self.base_ring.mul_assign_ref(&mut lhs.den, &rhs.den);
154        self.reduce(lhs);
155    }
156
157    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
158        self.base_ring.mul_assign_ref(&mut lhs.num, &rhs.den);
159        self.base_ring.add_assign(&mut lhs.num, self.base_ring.mul_ref_fst(&lhs.den, rhs.num));
160        self.base_ring.mul_assign(&mut lhs.den, rhs.den);
161        self.reduce(lhs);
162    }
163
164    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
165        self.base_ring.mul_assign_ref(&mut lhs.num, &rhs.num);
166        self.base_ring.mul_assign_ref(&mut lhs.den, &rhs.den);
167        self.reduce(lhs);
168    }
169
170    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
171        self.base_ring.mul_assign(&mut lhs.num, rhs.num);
172        self.base_ring.mul_assign(&mut lhs.den, rhs.den);
173        self.reduce(lhs);
174    }
175
176    fn negate_inplace(&self, lhs: &mut Self::Element) {
177        self.base_ring.negate_inplace(&mut lhs.num);
178    }
179
180    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
181        self.base_ring.eq_el(
182            &self.base_ring.mul_ref(&lhs.num, &rhs.den), 
183            &self.base_ring.mul_ref(&rhs.num, &lhs.den)
184        )
185    }
186
187    fn is_zero(&self, value: &Self::Element) -> bool {
188        self.base_ring.is_zero(&value.num)
189    }
190
191    fn is_one(&self, value: &Self::Element) -> bool {
192        self.base_ring.eq_el(&value.num, &value.den)
193    }
194
195    fn is_neg_one(&self, value: &Self::Element) -> bool {
196        self.base_ring.eq_el(&self.base_ring.negate(self.base_ring.clone_el(&value.num)), &value.den)
197    }
198
199    fn is_approximate(&self) -> bool {
200        self.base_ring.get_ring().is_approximate()
201    }
202
203    fn is_commutative(&self) -> bool {
204        // we currently enforce this, see assertion in construction; I'm not
205        // sure if fraction field even works for noncommutative rings
206        true
207    }
208
209    fn is_noetherian(&self) -> bool {
210        true
211    }
212
213    fn from_int(&self, value: i32) -> Self::Element {
214        self.from(self.base_ring.int_hom().map(value))
215    }
216
217    fn dbg_within<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>, env: EnvBindingStrength) -> std::fmt::Result {
218        if let Some(quo) = self.base_ring.checked_div(&value.num, &value.den) {
219            self.base_ring.get_ring().dbg_within(&quo, out, env)
220        } else {
221            if env >= EnvBindingStrength::Product {
222                write!(out, "(")?;
223            }
224            self.base_ring.get_ring().dbg_within(&value.num, out, EnvBindingStrength::Product)?;
225            write!(out, "/")?;
226            self.base_ring.get_ring().dbg_within(&value.den, out, EnvBindingStrength::Product)?;
227            if env >= EnvBindingStrength::Product {
228                write!(out, ")")?;
229            }
230            Ok(())
231        }
232    }
233
234    fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
235        where I::Type: IntegerRing
236    {
237        self.base_ring.characteristic(ZZ)
238    }
239}
240
241impl<R> RingExtension for FractionFieldImplBase<R>
242    where R: RingStore,
243        R::Type: Domain
244{
245    type BaseRing = R;
246
247    fn base_ring<'a>(&'a self) -> &'a Self::BaseRing {
248        &self.base_ring
249    }
250
251    fn from(&self, x: El<Self::BaseRing>) -> Self::Element {
252        FractionFieldEl {
253            num: x,
254            den: self.base_ring.one()
255        }
256    }
257
258    fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>) {
259        self.base_ring.mul_assign_ref(&mut lhs.num, rhs);
260        self.reduce(lhs);
261    }
262}
263
264impl<R> DivisibilityRing for FractionFieldImplBase<R>
265    where R: RingStore,
266        R::Type: Domain
267{
268    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
269        if self.is_zero(lhs) && self.is_zero(rhs) {
270            Some(self.zero())
271        } else if self.is_zero(rhs) {
272            None
273        } else {
274            let mut result = self.clone_el(lhs);
275            self.base_ring.mul_assign_ref(&mut result.num, &rhs.den);
276            self.base_ring.mul_assign_ref(&mut result.den, &rhs.num);
277            self.reduce(&mut result);
278            Some(result)
279        }
280    }
281
282    fn is_unit(&self, x: &Self::Element) -> bool {
283        !self.is_zero(x)
284    }
285
286    fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>
287        where I: Iterator<Item = &'a Self::Element>,
288            Self: 'a
289    {
290        // in general it is hard to get any guarantees, since `balance_factor()` has such
291        // a weak contract; hence, we focus here on the case that `balance_factor()` in the
292        // base ring behaves like gcd, and hope this is reasonable in the general case.
293        // this means we take a denominator such that dividing by this will clear all denominators,
294        // and then remove possible joint factors
295        let mut denominator_lcm = self.base_ring.one();
296        let mut it = elements.map(|x| {
297            let gcd = self.base_ring.get_ring().balance_factor([&denominator_lcm, &x.den].into_iter());
298            self.base_ring.mul_assign_ref(&mut denominator_lcm, &x.den);
299            if let Some(gcd) = gcd {
300                denominator_lcm = self.base_ring.checked_div(&denominator_lcm, &gcd).unwrap();
301            }
302            return &x.num;
303        });
304        let base_balance_factor = self.base_ring.get_ring().balance_factor(it.by_ref());
305        it.for_each(|_| {});
306
307        if let Some(den) = base_balance_factor {
308            return Some(FractionFieldEl {
309                num: den,
310                den: denominator_lcm
311            });
312        } else {
313            return Some(FractionFieldEl {
314                num: self.base_ring.one(),
315                den: denominator_lcm
316            });
317        }
318    }
319}
320
321impl<R> Domain for FractionFieldImplBase<R>
322    where R: RingStore,
323        R::Type: Domain
324{}
325
326impl<R> PrincipalIdealRing for FractionFieldImplBase<R>
327    where R: RingStore,
328        R::Type: Domain
329{
330    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
331        if self.is_zero(lhs) && self.is_zero(rhs) {
332            return Some(self.one());
333        }
334        self.checked_left_div(lhs, rhs)
335    }
336
337    fn extended_ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element, Self::Element) {
338        if self.is_zero(lhs) && self.is_zero(rhs) {
339            return (self.zero(), self.zero(), self.zero());
340        } else if self.is_zero(lhs) {
341            return (self.zero(), self.one(), self.clone_el(rhs));
342        } else {
343            return (self.one(), self.zero(), self.clone_el(lhs));
344        }
345    }
346}
347
348impl<R> EuclideanRing for FractionFieldImplBase<R>
349    where R: RingStore,
350        R::Type: Domain
351{
352    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> {
353        if self.is_zero(val) { Some(0) } else { Some(1) }
354    }
355
356    fn euclidean_div_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
357        assert!(!self.is_zero(rhs));
358        (self.checked_left_div(&lhs, rhs).unwrap(), self.zero())
359    }
360}
361
362impl<R> Field for FractionFieldImplBase<R>
363    where R: RingStore,
364        R::Type: Domain
365{}
366
367impl<R> FractionField for FractionFieldImplBase<R>
368    where R: RingStore,
369        R::Type: Domain
370{
371    fn as_fraction(&self, el: Self::Element) -> (El<Self::BaseRing>, El<Self::BaseRing>) {
372        (el.num, el.den)
373    }
374}
375
376///
377/// We don't have a canonical representation when the base ring is not an integer ring
378/// (even if it is a PID), since we can always multiply numerator/denominator by a unit.
379/// 
380impl<R> HashableElRing for FractionFieldImplBase<R>
381    where R: RingStore,
382        R::Type: Domain + IntegerRing + HashableElRing
383{
384    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
385        let gcd = signed_gcd(self.base_ring.clone_el(&el.den), self.base_ring.clone_el(&el.num), &self.base_ring);
386        self.base_ring.get_ring().hash(&self.base_ring.checked_div(&el.num, &gcd).unwrap(), h);
387        self.base_ring.get_ring().hash(&self.base_ring.checked_div(&el.den, &gcd).unwrap(), h);
388    }
389}
390
391impl<R: RingStore> StrassenHint for FractionFieldImplBase<R>
392    where R: RingStore,
393        R::Type: Domain
394{
395    default fn strassen_threshold(&self) -> usize {
396        usize::MAX
397    }
398}
399
400impl<R: RingStore> KaratsubaHint for FractionFieldImplBase<R>
401    where R: RingStore,
402        R::Type: Domain
403{
404    default fn karatsuba_threshold(&self) -> usize {
405        usize::MAX
406    }
407}
408
409impl<R: RingStore, S: RingStore> CanHomFrom<FractionFieldImplBase<S>> for FractionFieldImplBase<R>
410    where R: RingStore,
411        S: RingStore,
412        R::Type: Domain + CanHomFrom<S::Type>,
413        S::Type: Domain
414{
415    type Homomorphism = <R::Type as CanHomFrom<S::Type>>::Homomorphism;
416
417    fn has_canonical_hom(&self, from: &FractionFieldImplBase<S>) -> Option<Self::Homomorphism> {
418        self.base_ring().get_ring().has_canonical_hom(from.base_ring().get_ring())
419    }
420
421    fn map_in(&self, from: &FractionFieldImplBase<S>, el: <FractionFieldImplBase<S> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
422        self.from_fraction(self.base_ring().get_ring().map_in(from.base_ring().get_ring(), el.num, hom), self.base_ring().get_ring().map_in(from.base_ring().get_ring(), el.den, hom))
423    }
424}
425
426impl<R: RingStore, S: RingStore> CanIsoFromTo<FractionFieldImplBase<S>> for FractionFieldImplBase<R>
427    where R: RingStore,
428        S: RingStore,
429        R::Type: Domain + CanIsoFromTo<S::Type>,
430        S::Type: Domain
431{
432    type Isomorphism = <R::Type as CanIsoFromTo<S::Type>>::Isomorphism;
433
434    fn has_canonical_iso(&self, from: &FractionFieldImplBase<S>) -> Option<Self::Isomorphism> {
435        self.base_ring().get_ring().has_canonical_iso(from.base_ring().get_ring())
436    }
437
438    fn map_out(&self, from: &FractionFieldImplBase<S>, el: Self::Element, iso: &Self::Isomorphism) -> <FractionFieldImplBase<S> as RingBase>::Element {
439        from.from_fraction(self.base_ring().get_ring().map_out(from.base_ring().get_ring(), el.num, iso), self.base_ring().get_ring().map_out(from.base_ring().get_ring(), el.den, iso))
440    }
441}
442
443impl<R: RingStore, I: RingStore> CanHomFrom<RationalFieldBase<I>> for FractionFieldImplBase<R>
444    where R: RingStore,
445        I: RingStore,
446        R::Type: Domain + CanHomFrom<I::Type>,
447        I::Type: IntegerRing
448{
449    type Homomorphism = <R::Type as CanHomFrom<I::Type>>::Homomorphism;
450
451    fn has_canonical_hom(&self, from: &RationalFieldBase<I>) -> Option<Self::Homomorphism> {
452        self.base_ring().get_ring().has_canonical_hom(from.base_ring().get_ring())
453    }
454
455    fn map_in(&self, from: &RationalFieldBase<I>, el: <RationalFieldBase<I> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
456        let (num, den) = from.as_fraction(el);
457        self.from_fraction(self.base_ring().get_ring().map_in(from.base_ring().get_ring(), num, hom), self.base_ring().get_ring().map_in(from.base_ring().get_ring(), den, hom))
458    }
459}
460
461impl<R: RingStore, I: RingStore> CanIsoFromTo<RationalFieldBase<I>> for FractionFieldImplBase<R>
462    where R: RingStore,
463        I: RingStore,
464        R::Type: Domain + CanIsoFromTo<I::Type>,
465        I::Type: IntegerRing
466{
467    type Isomorphism = <R::Type as CanIsoFromTo<I::Type>>::Isomorphism;
468
469    fn has_canonical_iso(&self, from: &RationalFieldBase<I>) -> Option<Self::Isomorphism> {
470        self.base_ring().get_ring().has_canonical_iso(from.base_ring().get_ring())
471    }
472
473    fn map_out(&self, from: &RationalFieldBase<I>, el: Self::Element, iso: &Self::Isomorphism) -> <RationalFieldBase<I> as RingBase>::Element {
474        from.from_fraction(self.base_ring().get_ring().map_out(from.base_ring().get_ring(), el.num, iso), self.base_ring().get_ring().map_out(from.base_ring().get_ring(), el.den, iso))
475    }
476}
477
478#[cfg(test)]
479use crate::primitive_int::StaticRing;
480#[cfg(test)]
481use crate::iters::multi_cartesian_product;
482
483#[test]
484fn test_balance_factor() {
485    let ring = FractionFieldImpl::new(StaticRing::<i64>::RING);
486    let elements = [
487        ring.from_fraction(2 * 11, 3),
488        ring.from_fraction(6 * 11, 3),
489        ring.from_fraction(3 * 11, 18),
490        ring.from_fraction(6 * 11, 2),
491        ring.from_fraction(2 * 11, 6),
492        ring.from_fraction(5 * 11, 7),
493        ring.from_fraction(0, 1),
494        ring.from_fraction(0, 3),
495        ring.from_fraction(0, 12),
496        ring.from_fraction(0, 13)
497    ];
498    assert_el_eq!(&ring, ring.from_fraction(11, 7 * 6), ring.get_ring().balance_factor(elements.iter()).unwrap());
499}
500
501#[test]
502fn test_ring_axioms() {
503    let ring = FractionFieldImpl::new(StaticRing::<i64>::RING);
504    let edge_case_elements = multi_cartesian_product([&[-3, -2, -1, 0, 1, 2, 3][..], &[1, 2, 3][..]].into_iter().map(|list| list.iter().copied()), |data| ring.from_fraction(data[0], data[1]), |_, x| *x);
505    crate::ring::generic_tests::test_ring_axioms(&ring, edge_case_elements);
506}
feanor_math/rings/fraction/fraction_impl.rs

feanor_math/rings/fraction/
fraction_impl.rs
