feanor_math/rings/fraction/
fraction_impl.rs

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

feanor_math/rings/fraction/
fraction_impl.rs
