feanor_math/rings/
rational.rs

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

feanor_math/rings/
rational.rs
