feanor_math/rings/
rational.rs

1use std::fmt::Debug;
2use std::marker::PhantomData;
3
4use feanor_serde::newtype_struct::{DeserializeSeedNewtypeStruct, SerializableNewtypeStruct};
5use feanor_serde::seq::{DeserializeSeedSeq, SerializableSeq};
6use serde::de::DeserializeSeed;
7use serde::{Deserialize, Deserializer, Serialize, Serializer};
8
9use crate::algorithms::convolution::KaratsubaHint;
10use crate::algorithms::eea::{signed_gcd, signed_lcm};
11use crate::algorithms::matmul::StrassenHint;
12use crate::algorithms::poly_gcd::PolyTFracGCDRing;
13use crate::algorithms::poly_gcd::gcd::poly_gcd_local;
14use crate::algorithms::poly_gcd::squarefree_part::poly_power_decomposition_local;
15use crate::algorithms::resultant::ComputeResultantRing;
16use crate::computation::DontObserve;
17use crate::divisibility::{DivisibilityRing, DivisibilityRingStore, Domain};
18use crate::field::*;
19use crate::homomorphism::*;
20use crate::impl_interpolation_base_ring_char_zero;
21use crate::integer::*;
22use crate::ordered::{OrderedRing, OrderedRingStore};
23use crate::pid::{EuclideanRing, PrincipalIdealRing};
24use crate::ring::*;
25use crate::rings::poly::dense_poly::DensePolyRing;
26use crate::rings::poly::*;
27use crate::serialization::*;
28use crate::specialization::*;
29
30/// An implementation of the rational number `Q`, based on representing them
31/// as a tuple `(numerator, denominator)`.
32///
33/// Be careful when instantiating it with finite-precision integers, like `StaticRing<i64>`,
34/// since by nature of the rational numbers, both numerator and denominator can increase
35/// dramatically, even when the numbers itself are of moderate size.
36///
37/// # Example
38/// ```rust
39/// # use feanor_math::assert_el_eq;
40/// # use feanor_math::ring::*;
41/// # use feanor_math::primitive_int::*;
42/// # use feanor_math::rings::rational::*;
43/// # use feanor_math::homomorphism::Homomorphism;
44/// # use feanor_math::field::FieldStore;
45/// let ZZ = StaticRing::<i64>::RING;
46/// let QQ = RationalField::new(ZZ);
47/// let hom = QQ.can_hom(&ZZ).unwrap();
48/// let one_half = QQ.div(&QQ.one(), &hom.map(2));
49/// assert_el_eq!(QQ, QQ.div(&QQ.one(), &hom.map(4)), QQ.pow(one_half, 2));
50/// ```
51/// You can also retrieve numerator and denominator.
52/// ```rust
53/// # use feanor_math::assert_el_eq;
54/// # use feanor_math::ring::*;
55/// # use feanor_math::primitive_int::*;
56/// # use feanor_math::rings::rational::*;
57/// # use feanor_math::homomorphism::Homomorphism;
58/// # use feanor_math::field::FieldStore;
59/// # let ZZ = StaticRing::<i64>::RING;
60/// # let QQ = RationalField::new(ZZ);
61/// # let hom = QQ.can_hom(&ZZ).unwrap();
62/// # let one_half = QQ.div(&QQ.one(), &hom.map(2));
63/// assert_el_eq!(ZZ, ZZ.int_hom().map(1), QQ.num(&one_half));
64/// assert_el_eq!(ZZ, ZZ.int_hom().map(2), QQ.den(&one_half));
65/// ```
66pub struct RationalFieldBase<I: RingStore>
67where
68    I::Type: IntegerRing,
69{
70    integers: I,
71}
72
73impl<I> Clone for RationalFieldBase<I>
74where
75    I: RingStore + Clone,
76    I::Type: IntegerRing,
77{
78    fn clone(&self) -> Self {
79        Self {
80            integers: self.integers.clone(),
81        }
82    }
83}
84
85impl<I> Copy for RationalFieldBase<I>
86where
87    I: RingStore + Copy,
88    I::Type: IntegerRing,
89    El<I>: Copy,
90{
91}
92
93impl<I> Debug for RationalFieldBase<I>
94where
95    I: RingStore,
96    I::Type: IntegerRing,
97{
98    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "Q") }
99}
100/// [`RingStore`] corresponding to [`RationalFieldBase`]
101pub type RationalField<I> = RingValue<RationalFieldBase<I>>;
102
103/// An element of [`RationalField`], i.e. a fraction of two integers.
104pub struct RationalFieldEl<I>(El<I>, El<I>)
105where
106    I: RingStore,
107    I::Type: IntegerRing;
108
109impl<I> Debug for RationalFieldEl<I>
110where
111    I: RingStore,
112    I::Type: IntegerRing,
113    El<I>: Debug,
114{
115    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
116        f.debug_struct("RationalFieldEl")
117            .field("num", &self.0)
118            .field("den", &self.1)
119            .finish()
120    }
121}
122
123impl<I> Clone for RationalFieldEl<I>
124where
125    I: RingStore,
126    I::Type: IntegerRing,
127    El<I>: Clone,
128{
129    fn clone(&self) -> Self { RationalFieldEl(self.0.clone(), self.1.clone()) }
130}
131
132impl<I> Copy for RationalFieldEl<I>
133where
134    I: RingStore,
135    I::Type: IntegerRing,
136    El<I>: Copy,
137{
138}
139
140impl<I> PartialEq for RationalFieldBase<I>
141where
142    I: RingStore,
143    I::Type: IntegerRing,
144{
145    fn eq(&self, other: &Self) -> bool { self.integers.get_ring() == other.integers.get_ring() }
146}
147
148impl<I> RationalFieldBase<I>
149where
150    I: RingStore,
151    I::Type: IntegerRing,
152{
153    /// The numerator of the fully reduced fraction.
154    ///
155    /// # Example
156    /// ```rust
157    /// # use feanor_math::assert_el_eq;
158    /// # use feanor_math::ring::*;
159    /// # use feanor_math::primitive_int::*;
160    /// # use feanor_math::rings::rational::*;
161    /// # use feanor_math::homomorphism::Homomorphism;
162    /// # use feanor_math::field::FieldStore;
163    /// # let ZZ = StaticRing::<i64>::RING;
164    /// # let QQ = RationalField::new(ZZ);
165    /// assert_el_eq!(
166    ///     ZZ,
167    ///     2,
168    ///     QQ.num(&QQ.div(&QQ.inclusion().map(6), &QQ.inclusion().map(3)))
169    /// );
170    /// ```
171    pub fn num<'a>(&'a self, el: &'a <Self as RingBase>::Element) -> &'a El<I> {
172        debug_assert!(self.base_ring().is_one(&signed_gcd(
173            self.base_ring().clone_el(&el.1),
174            self.base_ring().clone_el(&el.0),
175            self.base_ring()
176        )));
177        &el.0
178    }
179
180    /// The denominator of the fully reduced fraction.
181    ///
182    /// # Example
183    /// ```rust
184    /// # use feanor_math::assert_el_eq;
185    /// # use feanor_math::ring::*;
186    /// # use feanor_math::primitive_int::*;
187    /// # use feanor_math::rings::rational::*;
188    /// # use feanor_math::homomorphism::Homomorphism;
189    /// # use feanor_math::field::FieldStore;
190    /// # let ZZ = StaticRing::<i64>::RING;
191    /// # let QQ = RationalField::new(ZZ);
192    /// assert_el_eq!(
193    ///     ZZ,
194    ///     3,
195    ///     QQ.den(&QQ.div(&QQ.inclusion().map(3), &QQ.inclusion().map(9)))
196    /// );
197    /// ```
198    pub fn den<'a>(&'a self, el: &'a <Self as RingBase>::Element) -> &'a El<I> {
199        debug_assert!(self.base_ring().is_one(&signed_gcd(
200            self.base_ring().clone_el(&el.1),
201            self.base_ring().clone_el(&el.0),
202            self.base_ring()
203        )));
204        &el.1
205    }
206}
207
208impl<I> RationalField<I>
209where
210    I: RingStore,
211    I::Type: IntegerRing,
212{
213    /// Returns the fraction field of the given integer ring.
214    pub const fn new(integers: I) -> Self { RingValue::from(RationalFieldBase { integers }) }
215
216    /// See [`RationalFieldBase::num()`].
217    pub fn num<'a>(&'a self, el: &'a El<Self>) -> &'a El<I> { self.get_ring().num(el) }
218
219    /// See [`RationalFieldBase::den()`].
220    pub fn den<'a>(&'a self, el: &'a El<Self>) -> &'a El<I> { self.get_ring().den(el) }
221}
222
223impl<I> RationalFieldBase<I>
224where
225    I: RingStore,
226    I::Type: IntegerRing,
227{
228    fn reduce(&self, value: (&mut El<I>, &mut El<I>)) {
229        // take the denominator first, as in this case gcd will have the same sign, and the final
230        // denominator will be positive
231        let gcd = signed_gcd(
232            self.integers.clone_el(&*value.1),
233            self.integers.clone_el(&*value.0),
234            &self.integers,
235        );
236        *value.0 = self.integers.checked_div(&*value.0, &gcd).unwrap();
237        *value.1 = self.integers.checked_div(&*value.1, &gcd).unwrap();
238    }
239
240    fn mul_assign_raw(&self, lhs: &mut <Self as RingBase>::Element, rhs: (&El<I>, &El<I>)) {
241        self.integers.mul_assign_ref(&mut lhs.0, rhs.0);
242        self.integers.mul_assign_ref(&mut lhs.1, rhs.1);
243        self.reduce((&mut lhs.0, &mut lhs.1));
244    }
245}
246
247impl<I> RingBase for RationalFieldBase<I>
248where
249    I: RingStore,
250    I::Type: IntegerRing,
251{
252    type Element = RationalFieldEl<I>;
253
254    fn add_assign(&self, lhs: &mut Self::Element, mut rhs: Self::Element) {
255        if self.integers.is_one(&lhs.1) && self.integers.is_one(&rhs.1) {
256            self.integers.add_assign(&mut lhs.0, rhs.0);
257        } else {
258            self.integers.mul_assign_ref(&mut lhs.0, &rhs.1);
259            self.integers.mul_assign_ref(&mut rhs.0, &lhs.1);
260            self.integers.mul_assign(&mut lhs.1, rhs.1);
261            self.integers.add_assign(&mut lhs.0, rhs.0);
262            self.reduce((&mut lhs.0, &mut lhs.1));
263        }
264    }
265
266    fn clone_el(&self, val: &Self::Element) -> Self::Element {
267        RationalFieldEl(self.integers.clone_el(&val.0), self.integers.clone_el(&val.1))
268    }
269
270    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
271        if self.integers.is_one(&lhs.1) && self.integers.is_one(&rhs.1) {
272            self.integers.add_assign_ref(&mut lhs.0, &rhs.0);
273        } else {
274            self.integers.mul_assign_ref(&mut lhs.0, &rhs.1);
275            self.integers
276                .add_assign(&mut lhs.0, self.integers.mul_ref(&lhs.1, &rhs.0));
277            self.integers.mul_assign_ref(&mut lhs.1, &rhs.1);
278            self.reduce((&mut lhs.0, &mut lhs.1));
279        }
280    }
281
282    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
283        self.mul_assign_raw(lhs, (&rhs.0, &rhs.1))
284    }
285
286    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
287        self.integers.mul_assign(&mut lhs.0, rhs.0);
288        self.integers.mul_assign(&mut lhs.1, rhs.1);
289        self.reduce((&mut lhs.0, &mut lhs.1));
290    }
291
292    fn negate_inplace(&self, lhs: &mut Self::Element) { self.integers.negate_inplace(&mut lhs.0); }
293
294    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
295        self.integers.eq_el(
296            &self.integers.mul_ref(&lhs.0, &rhs.1),
297            &self.integers.mul_ref(&lhs.1, &rhs.0),
298        )
299    }
300
301    fn is_zero(&self, value: &Self::Element) -> bool { self.integers.is_zero(&value.0) }
302
303    fn is_one(&self, value: &Self::Element) -> bool { self.integers.eq_el(&value.0, &value.1) }
304
305    fn is_neg_one(&self, value: &Self::Element) -> bool {
306        self.integers
307            .eq_el(&value.0, &self.integers.negate(self.integers.clone_el(&value.1)))
308    }
309
310    fn is_approximate(&self) -> bool { false }
311
312    fn is_commutative(&self) -> bool { true }
313
314    fn is_noetherian(&self) -> bool { true }
315
316    fn characteristic<J: RingStore + Copy>(&self, ZZ: J) -> Option<El<J>>
317    where
318        J::Type: IntegerRing,
319    {
320        Some(ZZ.zero())
321    }
322
323    fn dbg_within<'a>(
324        &self,
325        value: &Self::Element,
326        out: &mut std::fmt::Formatter<'a>,
327        env: EnvBindingStrength,
328    ) -> std::fmt::Result {
329        if self.base_ring().is_one(&value.1) {
330            write!(out, "{}", self.integers.format(&value.0))
331        } else {
332            if env > EnvBindingStrength::Product {
333                write!(
334                    out,
335                    "({}/{})",
336                    self.integers.format(&value.0),
337                    self.integers.format(&value.1)
338                )
339            } else {
340                write!(
341                    out,
342                    "{}/{}",
343                    self.integers.format(&value.0),
344                    self.integers.format(&value.1)
345                )
346            }
347        }
348    }
349
350    fn from_int(&self, value: i32) -> Self::Element {
351        RationalFieldEl(self.integers.get_ring().from_int(value), self.integers.one())
352    }
353}
354
355impl<I: RingStore> HashableElRing for RationalFieldBase<I>
356where
357    I::Type: IntegerRing + HashableElRing,
358{
359    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
360        let gcd = signed_gcd(
361            self.integers.clone_el(&el.1),
362            self.integers.clone_el(&el.0),
363            &self.integers,
364        );
365        self.integers
366            .get_ring()
367            .hash(&self.integers.checked_div(&el.0, &gcd).unwrap(), h);
368        self.integers
369            .get_ring()
370            .hash(&self.integers.checked_div(&el.1, &gcd).unwrap(), h);
371    }
372}
373
374impl<I: RingStore> StrassenHint for RationalFieldBase<I>
375where
376    I::Type: IntegerRing,
377{
378    default fn strassen_threshold(&self) -> usize { usize::MAX }
379}
380
381impl<I: RingStore> KaratsubaHint for RationalFieldBase<I>
382where
383    I::Type: IntegerRing,
384{
385    default fn karatsuba_threshold(&self) -> usize { usize::MAX }
386}
387
388impl<I> RingExtension for RationalFieldBase<I>
389where
390    I: RingStore,
391    I::Type: IntegerRing,
392{
393    type BaseRing = I;
394
395    fn base_ring(&self) -> &Self::BaseRing { &self.integers }
396
397    fn from(&self, x: El<Self::BaseRing>) -> Self::Element { RationalFieldEl(x, self.integers.one()) }
398
399    fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>) {
400        self.integers.mul_assign_ref(&mut lhs.0, rhs);
401        self.reduce((&mut lhs.0, &mut lhs.1));
402    }
403}
404
405impl<I> Serialize for RationalFieldBase<I>
406where
407    I: RingStore + Serialize,
408    I::Type: IntegerRing,
409{
410    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
411    where
412        S: Serializer,
413    {
414        SerializableNewtypeStruct::new("RationalField", self.base_ring()).serialize(serializer)
415    }
416}
417
418impl<'de, I> Deserialize<'de> for RationalFieldBase<I>
419where
420    I: RingStore + Deserialize<'de>,
421    I::Type: IntegerRing,
422{
423    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
424    where
425        D: Deserializer<'de>,
426    {
427        DeserializeSeedNewtypeStruct::new("RationalField", PhantomData::<I>)
428            .deserialize(deserializer)
429            .map(|base_ring| RationalFieldBase { integers: base_ring })
430    }
431}
432
433impl<I> SerializableElementRing for RationalFieldBase<I>
434where
435    I: RingStore,
436    I::Type: IntegerRing + SerializableElementRing,
437{
438    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
439    where
440        D: Deserializer<'de>,
441    {
442        DeserializeSeedNewtypeStruct::new(
443            "Rational",
444            DeserializeSeedSeq::new(
445                std::iter::repeat_n(DeserializeWithRing::new(self.base_ring()), 3),
446                (None, None),
447                |mut current, next| {
448                    if current.0.is_none() {
449                        current.0 = Some(next);
450                    } else if current.1.is_none() {
451                        current.1 = Some(next);
452                    } else {
453                        unreachable!();
454                    }
455                    return current;
456                },
457            ),
458        )
459        .deserialize(deserializer)
460        .map(|res| self.from_fraction(res.0.unwrap(), res.1.unwrap()))
461    }
462
463    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
464    where
465        S: Serializer,
466    {
467        SerializableNewtypeStruct::new(
468            "Rational",
469            SerializableSeq::new_with_len(
470                [
471                    SerializeWithRing::new(&el.0, self.base_ring()),
472                    SerializeWithRing::new(&el.1, self.base_ring()),
473                ]
474                .iter(),
475                2,
476            ),
477        )
478        .serialize(serializer)
479    }
480}
481
482impl<I, J> CanHomFrom<RationalFieldBase<J>> for RationalFieldBase<I>
483where
484    I: RingStore,
485    I::Type: IntegerRing,
486    J: RingStore,
487    J::Type: IntegerRing,
488{
489    type Homomorphism = ();
490
491    fn has_canonical_hom(&self, _from: &RationalFieldBase<J>) -> Option<Self::Homomorphism> { Some(()) }
492
493    fn map_in(
494        &self,
495        from: &RationalFieldBase<J>,
496        el: <RationalFieldBase<J> as RingBase>::Element,
497        (): &Self::Homomorphism,
498    ) -> Self::Element {
499        RationalFieldEl(
500            int_cast(el.0, self.base_ring(), from.base_ring()),
501            int_cast(el.1, self.base_ring(), from.base_ring()),
502        )
503    }
504}
505
506impl<I, J> CanIsoFromTo<RationalFieldBase<J>> for RationalFieldBase<I>
507where
508    I: RingStore,
509    I::Type: IntegerRing,
510    J: RingStore,
511    J::Type: IntegerRing,
512{
513    type Isomorphism = ();
514
515    fn has_canonical_iso(&self, _from: &RationalFieldBase<J>) -> Option<Self::Isomorphism> { Some(()) }
516
517    fn map_out(
518        &self,
519        from: &RationalFieldBase<J>,
520        el: Self::Element,
521        (): &Self::Homomorphism,
522    ) -> <RationalFieldBase<J> as RingBase>::Element {
523        RationalFieldEl(
524            int_cast(el.0, from.base_ring(), self.base_ring()),
525            int_cast(el.1, from.base_ring(), self.base_ring()),
526        )
527    }
528}
529
530impl<I, J> CanHomFrom<J> for RationalFieldBase<I>
531where
532    I: RingStore,
533    I::Type: IntegerRing,
534    J: IntegerRing,
535{
536    type Homomorphism = ();
537
538    fn has_canonical_hom(&self, _from: &J) -> Option<Self::Homomorphism> { Some(()) }
539
540    fn map_in(&self, from: &J, el: <J as RingBase>::Element, (): &Self::Homomorphism) -> Self::Element {
541        RationalFieldEl(int_cast(el, self.base_ring(), &RingRef::new(from)), self.integers.one())
542    }
543}
544
545impl<I> DivisibilityRing for RationalFieldBase<I>
546where
547    I: RingStore,
548    I::Type: IntegerRing,
549{
550    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
551        if self.is_zero(lhs) && self.is_zero(rhs) {
552            Some(self.zero())
553        } else if self.is_zero(rhs) {
554            None
555        } else {
556            let mut result = self.clone_el(lhs);
557            self.mul_assign_raw(&mut result, (&rhs.1, &rhs.0));
558            Some(result)
559        }
560    }
561
562    fn is_unit(&self, x: &Self::Element) -> bool { !self.is_zero(x) }
563
564    fn balance_factor<'a, J>(&self, elements: J) -> Option<Self::Element>
565    where
566        J: Iterator<Item = &'a Self::Element>,
567        Self: 'a,
568    {
569        let (num, den) = elements.fold((self.integers.zero(), self.integers.one()), |x, y| {
570            (
571                signed_gcd(x.0, self.base_ring().clone_el(self.num(y)), self.base_ring()),
572                signed_lcm(x.1, self.base_ring().clone_el(self.den(y)), self.base_ring()),
573            )
574        });
575        return Some(RationalFieldEl(num, den));
576    }
577}
578
579impl_interpolation_base_ring_char_zero! { <{I}> InterpolationBaseRing for RationalFieldBase<I> where I: RingStore, I::Type: IntegerRing + ComputeResultantRing }
580
581impl<I> PrincipalIdealRing for RationalFieldBase<I>
582where
583    I: RingStore,
584    I::Type: IntegerRing,
585{
586    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
587        if self.is_zero(lhs) && self.is_zero(rhs) {
588            return Some(self.one());
589        }
590        self.checked_left_div(lhs, rhs)
591    }
592
593    fn extended_ideal_gen(
594        &self,
595        lhs: &Self::Element,
596        rhs: &Self::Element,
597    ) -> (Self::Element, Self::Element, Self::Element) {
598        if self.is_zero(lhs) && self.is_zero(rhs) {
599            return (self.zero(), self.zero(), self.zero());
600        } else if self.is_zero(lhs) {
601            return (self.zero(), self.one(), self.clone_el(rhs));
602        } else {
603            return (self.one(), self.zero(), self.clone_el(lhs));
604        }
605    }
606}
607
608impl<I> EuclideanRing for RationalFieldBase<I>
609where
610    I: RingStore,
611    I::Type: IntegerRing,
612{
613    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> { if self.is_zero(val) { Some(0) } else { Some(1) } }
614
615    fn euclidean_div_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
616        assert!(!self.is_zero(rhs));
617        (self.checked_left_div(&lhs, rhs).unwrap(), self.zero())
618    }
619}
620
621impl<I> Domain for RationalFieldBase<I>
622where
623    I: RingStore,
624    I::Type: IntegerRing,
625{
626}
627
628impl<I> PerfectField for RationalFieldBase<I>
629where
630    I: RingStore,
631    I::Type: IntegerRing,
632{
633}
634
635impl<I> Field for RationalFieldBase<I>
636where
637    I: RingStore,
638    I::Type: IntegerRing,
639{
640}
641
642impl<I> FiniteRingSpecializable for RationalFieldBase<I>
643where
644    I: RingStore,
645    I::Type: IntegerRing,
646{
647    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output { op.fallback() }
648}
649
650impl<I> FractionField for RationalFieldBase<I>
651where
652    I: RingStore,
653    I::Type: IntegerRing,
654{
655    fn as_fraction(&self, el: Self::Element) -> (El<Self::BaseRing>, El<Self::BaseRing>) { (el.0, el.1) }
656}
657
658impl<I> OrderedRing for RationalFieldBase<I>
659where
660    I: RingStore,
661    I::Type: IntegerRing,
662{
663    fn cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> std::cmp::Ordering {
664        assert!(self.integers.is_pos(&lhs.1) && self.integers.is_pos(&rhs.1));
665        self.integers.cmp(
666            &self.integers.mul_ref(&lhs.0, &rhs.1),
667            &self.integers.mul_ref(&rhs.0, &lhs.1),
668        )
669    }
670}
671
672impl<I> PolyTFracGCDRing for RationalFieldBase<I>
673where
674    I: RingStore,
675    I::Type: IntegerRing,
676{
677    fn power_decomposition<P>(poly_ring: P, poly: &El<P>) -> Vec<(El<P>, usize)>
678    where
679        P: RingStore + Copy,
680        P::Type: PolyRing,
681        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
682    {
683        assert!(!poly_ring.is_zero(poly));
684        let QQX = &poly_ring;
685        let QQ = QQX.base_ring();
686        let ZZ = QQ.base_ring();
687
688        let den_lcm = QQX
689            .terms(poly)
690            .map(|(c, _)| QQ.get_ring().den(c))
691            .fold(ZZ.one(), |a, b| signed_lcm(a, ZZ.clone_el(b), ZZ));
692
693        let ZZX = DensePolyRing::new(ZZ, "X");
694        let f = ZZX.from_terms(QQX.terms(poly).map(|(c, i)| {
695            (
696                ZZ.checked_div(&ZZ.mul_ref(&den_lcm, QQ.get_ring().num(c)), QQ.get_ring().den(c))
697                    .unwrap(),
698                i,
699            )
700        }));
701        let power_decomp = poly_power_decomposition_local(&ZZX, f, DontObserve);
702        let ZZX_to_QQX = QQX.lifted_hom(&ZZX, QQ.inclusion());
703
704        return power_decomp
705            .into_iter()
706            .map(|(f, k)| (QQX.normalize(ZZX_to_QQX.map(f)), k))
707            .collect();
708    }
709
710    fn gcd<P>(poly_ring: P, lhs: &El<P>, rhs: &El<P>) -> El<P>
711    where
712        P: RingStore + Copy,
713        P::Type: PolyRing,
714        <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
715    {
716        if poly_ring.is_zero(lhs) {
717            return poly_ring.clone_el(rhs);
718        } else if poly_ring.is_zero(rhs) {
719            return poly_ring.clone_el(lhs);
720        }
721        let QQX = &poly_ring;
722        let QQ = QQX.base_ring();
723        let ZZ = QQ.base_ring();
724
725        let den_lcm_lhs = QQX
726            .terms(lhs)
727            .map(|(c, _)| QQ.get_ring().den(c))
728            .fold(ZZ.one(), |a, b| signed_lcm(a, ZZ.clone_el(b), ZZ));
729        let den_lcm_rhs = QQX
730            .terms(rhs)
731            .map(|(c, _)| QQ.get_ring().den(c))
732            .fold(ZZ.one(), |a, b| signed_lcm(a, ZZ.clone_el(b), ZZ));
733
734        let ZZX = DensePolyRing::new(ZZ, "X");
735        let lhs = ZZX.from_terms(QQX.terms(lhs).map(|(c, i)| {
736            (
737                ZZ.checked_div(&ZZ.mul_ref(&den_lcm_lhs, QQ.get_ring().num(c)), QQ.get_ring().den(c))
738                    .unwrap(),
739                i,
740            )
741        }));
742        let rhs = ZZX.from_terms(QQX.terms(rhs).map(|(c, i)| {
743            (
744                ZZ.checked_div(&ZZ.mul_ref(&den_lcm_rhs, QQ.get_ring().num(c)), QQ.get_ring().den(c))
745                    .unwrap(),
746                i,
747            )
748        }));
749        let result = poly_gcd_local(&ZZX, lhs, rhs, DontObserve);
750        let ZZX_to_QQX = QQX.lifted_hom(&ZZX, QQ.inclusion());
751
752        return QQX.normalize(ZZX_to_QQX.map(result));
753    }
754}
755
756use super::fraction::FractionField;
757use super::poly::PolyRing;
758#[cfg(test)]
759use crate::homomorphism::Homomorphism;
760#[cfg(test)]
761use crate::primitive_int::StaticRing;
762
763#[cfg(test)]
764fn edge_case_elements() -> impl Iterator<Item = El<RationalField<StaticRing<i64>>>> {
765    let ring = RationalField::new(StaticRing::<i64>::RING);
766    let incl = ring.into_int_hom();
767    (-6..8).flat_map(move |x| {
768        (-2..5)
769            .filter(|y| *y != 0)
770            .map(move |y| ring.checked_div(&incl.map(x), &incl.map(y)).unwrap())
771    })
772}
773
774#[test]
775fn test_ring_axioms() {
776    let ring = RationalField::new(StaticRing::<i64>::RING);
777
778    let half = ring
779        .checked_div(&ring.int_hom().map(1), &ring.int_hom().map(2))
780        .unwrap();
781    assert!(!ring.is_one(&half));
782    assert!(!ring.is_zero(&half));
783    assert_el_eq!(ring, ring.one(), ring.add_ref(&half, &half));
784    crate::ring::generic_tests::test_ring_axioms(ring, edge_case_elements());
785}
786
787#[test]
788fn test_divisibility_axioms() {
789    let ring = RationalField::new(StaticRing::<i64>::RING);
790    crate::divisibility::generic_tests::test_divisibility_axioms(ring, edge_case_elements());
791}
792
793#[test]
794fn test_principal_ideal_ring_axioms() {
795    let ring = RationalField::new(StaticRing::<i64>::RING);
796    crate::pid::generic_tests::test_euclidean_ring_axioms(ring, edge_case_elements());
797    crate::pid::generic_tests::test_principal_ideal_ring_axioms(ring, edge_case_elements());
798}
799
800#[test]
801fn test_int_hom_axioms() {
802    let ring = RationalField::new(StaticRing::<i64>::RING);
803    crate::ring::generic_tests::test_hom_axioms(&StaticRing::<i64>::RING, ring, -16..15);
804}
805
806#[test]
807fn test_serialization() {
808    let ring = RationalField::new(StaticRing::<i64>::RING);
809    crate::serialization::generic_tests::test_serialization(ring, edge_case_elements());
810}
811
812#[test]
813fn test_serialize_deserialize() {
814    crate::serialization::generic_tests::test_serialize_deserialize(RationalField::new(StaticRing::<i64>::RING).into());
815    crate::serialization::generic_tests::test_serialize_deserialize(RationalField::new(BigIntRing::RING).into());
816}
817
818#[test]
819fn test_serialize_postcard() {
820    let ring: RingValue<RationalFieldBase<RingValue<crate::primitive_int::StaticRingBase<i64>>>> =
821        RationalField::new(StaticRing::<i64>::RING);
822    let serialized = postcard::to_allocvec(&SerializeWithRing::new(&ring.int_hom().map(42), &ring)).unwrap();
823    let result = DeserializeWithRing::new(&ring)
824        .deserialize(&mut postcard::Deserializer::from_flavor(
825            postcard::de_flavors::Slice::new(&serialized),
826        ))
827        .unwrap();
828
829    assert_el_eq!(&ring, ring.int_hom().map(42), result);
830}
feanor_math/rings/rational.rs

feanor_math/rings/
rational.rs
