feanor_math/rings/poly/
mod.rs

1use std::collections::HashMap;
2
3use crate::divisibility::*;
4use crate::ring::*;
5use crate::homomorphism::*;
6use crate::wrapper::RingElementWrapper;
7
8///
9/// Contains [`dense_poly::DensePolyRing`], an implementation of univariate polynomials
10/// based on dense coefficient storage.
11/// 
12pub mod dense_poly;
13///
14/// Contains [`sparse_poly::SparsePolyRing`], an implementation of univariate polynomials
15/// based on sparse coefficient storage.
16/// 
17pub mod sparse_poly;
18
19///
20/// Trait for all rings that represent the polynomial ring `R[X]` with
21/// any base ring R.
22/// 
23/// Currently, the two implementations of this type of ring are [`dense_poly::DensePolyRing`]
24/// and [`sparse_poly::SparsePolyRing`].
25/// 
26pub trait PolyRing: RingExtension {
27
28    type TermsIterator<'a>: Iterator<Item = (&'a El<Self::BaseRing>, usize)>
29        where Self: 'a;
30
31    ///
32    /// Returns the indeterminate `X` generating this polynomial ring.
33    /// 
34    fn indeterminate(&self) -> Self::Element;
35
36    ///
37    /// Returns all the nonzero terms of the given polynomial.
38    /// 
39    /// If the base ring is only approximate, it is valid to return "zero" terms,
40    /// whatever that actually means.
41    /// 
42    fn terms<'a>(&'a self, f: &'a Self::Element) -> Self::TermsIterator<'a>;
43    
44    ///
45    /// Adds the given terms to the given polynomial.
46    /// 
47    fn add_assign_from_terms<I>(&self, lhs: &mut Self::Element, rhs: I)
48        where I: IntoIterator<Item = (El<Self::BaseRing>, usize)>
49    {
50        let self_ring = RingRef::new(self);
51        self.add_assign(lhs, self_ring.sum(
52            rhs.into_iter().map(|(c, i)| self.mul(self.from(c), self_ring.pow(self.indeterminate(), i)))
53        ));
54    }
55
56    ///
57    /// Multiplies the given polynomial with `X^rhs_power`.
58    /// 
59    fn mul_assign_monomial(&self, lhs: &mut Self::Element, rhs_power: usize) {
60        self.mul_assign(lhs, RingRef::new(self).pow(self.indeterminate(), rhs_power));
61    }
62
63    ///
64    /// Returns the coefficient of `f` that corresponds to the monomial `X^i`.
65    /// 
66    fn coefficient_at<'a>(&'a self, f: &'a Self::Element, i: usize) -> &'a El<Self::BaseRing>;
67
68    ///
69    /// Returns the degree of the polynomial `f`, i.e. the value `d` such that `f` can be written as
70    /// `f(X) = a0 + a1 * X + a2 * X^2 + ... + ad * X^d`. Returns `None` if `f` is zero.
71    /// 
72    fn degree(&self, f: &Self::Element) -> Option<usize>;
73
74    ///
75    /// Compute the euclidean division by a monic polynomial `rhs`.
76    /// 
77    /// Concretely, if `rhs` is a monic polynomial (polynomial with highest coefficient equal to 1), then
78    /// there exist unique `q, r` such that `lhs = rhs * q + r` and `deg(r) < deg(rhs)`. These are returned.
79    /// This function panics if `rhs` is not monic.
80    /// 
81    fn div_rem_monic(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element);
82    
83    fn map_terms<P, H>(&self, from: &P, el: &P::Element, hom: H) -> Self::Element
84        where P: ?Sized + PolyRing,
85            H: Homomorphism<<P::BaseRing as RingStore>::Type, <Self::BaseRing as RingStore>::Type>
86    {
87        assert!(self.base_ring().get_ring() == hom.codomain().get_ring());
88        assert!(from.base_ring().get_ring() == hom.domain().get_ring());
89        RingRef::new(self).from_terms(from.terms(el).map(|(c, i)| (hom.map_ref(c), i)))
90    }
91    
92    ///
93    /// Possibly divides all coefficients of the polynomial by a common factor,
94    /// in order to make them "smaller". 
95    /// 
96    /// In cases where we mainly care about polynomials up to scaling by non-zero 
97    /// divisors of the base ring, balancing intermediate polynomials can improve performance.
98    /// 
99    /// For more details on balancing, see [`DivisibilityRing::balance_factor()`].
100    /// 
101    #[stability::unstable(feature = "enable")]
102    fn balance_poly(&self, f: &mut Self::Element) -> Option<El<Self::BaseRing>>
103        where <Self::BaseRing as RingStore>::Type: DivisibilityRing
104    {
105        let balance_factor = self.base_ring().get_ring().balance_factor(self.terms(f).map(|(c, _)| c));
106        if let Some(balance_factor) = &balance_factor {
107            *f = RingRef::new(self).from_terms(self.terms(f).map(|(c, i)| (self.base_ring().checked_div(c, &balance_factor).unwrap(), i)));
108        }
109        return balance_factor;
110    }
111
112    ///
113    /// Evaluates the given polynomial at the given values.
114    /// 
115    /// # Example
116    /// ```
117    /// # use feanor_math::ring::*;
118    /// # use feanor_math::rings::poly::*;
119    /// # use feanor_math::primitive_int::*; 
120    /// let ring = dense_poly::DensePolyRing::new(StaticRing::<i32>::RING, "X");
121    /// let x = ring.indeterminate();
122    /// let poly = ring.add(ring.clone_el(&x), ring.pow(x, 2));
123    /// assert_eq!(12, ring.evaluate(&poly, &3, &StaticRing::<i32>::RING.identity()));
124    /// ```
125    /// 
126    fn evaluate<R, H>(&self, f: &Self::Element, value: &R::Element, hom: H) -> R::Element
127        where R: ?Sized + RingBase,
128            H: Homomorphism<<Self::BaseRing as RingStore>::Type, R>
129    {
130        hom.codomain().sum(self.terms(f).map(|(c, i)| {
131            let result = hom.codomain().pow(hom.codomain().clone_el(value), i);
132            hom.mul_ref_snd_map(result, c)
133        }))
134    }
135}
136
137///
138/// [`RingStore`] corresponding to [`PolyRing`].
139/// 
140pub trait PolyRingStore: RingStore
141    where Self::Type: PolyRing
142{
143    delegate!{ PolyRing, fn indeterminate(&self) -> El<Self> }
144    delegate!{ PolyRing, fn degree(&self, f: &El<Self>) -> Option<usize> }
145    delegate!{ PolyRing, fn mul_assign_monomial(&self, lhs: &mut El<Self>, rhs_power: usize) -> () }
146    delegate!{ PolyRing, fn div_rem_monic(&self, lhs: El<Self>, rhs: &El<Self>) -> (El<Self>, El<Self>) }
147
148    ///
149    /// See [`PolyRing::coefficient_at()`].
150    /// 
151    fn coefficient_at<'a>(&'a self, f: &'a El<Self>, i: usize) -> &'a El<<Self::Type as RingExtension>::BaseRing> {
152        self.get_ring().coefficient_at(f, i)
153    }
154
155    ///
156    /// See [`PolyRing::terms()`].
157    /// 
158    fn terms<'a>(&'a self, f: &'a El<Self>) -> <Self::Type as PolyRing>::TermsIterator<'a> {
159        self.get_ring().terms(f)
160    }
161
162    ///
163    /// Computes the polynomial from the given terms.
164    /// 
165    /// If the iterator gives a term for the same monomial `X^i` multiple times,
166    /// the corresponding coefficients will be summed up.
167    /// 
168    fn from_terms<I>(&self, iter: I) -> El<Self>
169        where I: IntoIterator<Item = (El<<Self::Type as RingExtension>::BaseRing>, usize)>,
170    {
171        let mut result = self.zero();
172        self.get_ring().add_assign_from_terms(&mut result, iter);
173        return result;
174    }
175
176    fn try_from_terms<E, I>(&self, iter: I) -> Result<El<Self>, E>
177        where I: IntoIterator<Item = Result<(El<<Self::Type as RingExtension>::BaseRing>, usize), E>>,
178    {
179        let mut result = self.zero();
180        let mut error = None;
181        self.get_ring().add_assign_from_terms(&mut result, iter.into_iter().map(|t| match t {
182            Ok(t) => Some(t),
183            Err(e) => { error = Some(e); None }
184        }).take_while(|t| t.is_some()).map(|t| t.unwrap()));
185        if let Some(e) = error {
186            return Err(e);
187        } else {
188            return Ok(result);
189        }
190    }
191
192    ///
193    /// Returns a reference to the leading coefficient of the given polynomial, or `None` if the
194    /// polynomial is zero.
195    /// 
196    fn lc<'a>(&'a self, f: &'a El<Self>) -> Option<&'a El<<Self::Type as RingExtension>::BaseRing>> {
197        Some(self.coefficient_at(f, self.degree(f)?))
198    }
199    
200    ///
201    /// Divides each coefficient of this polynomial by its leading coefficient, thus making it monic.
202    /// 
203    /// Panics if the leading coefficient is not a unit.
204    /// 
205    /// # Example
206    /// ```
207    /// # use feanor_math::ring::*;
208    /// # use feanor_math::rings::poly::*;
209    /// # use feanor_math::assert_el_eq;
210    /// # use feanor_math::rings::poly::dense_poly::*;
211    /// # use feanor_math::primitive_int::*;
212    /// let P = DensePolyRing::new(StaticRing::<i64>::RING, "X");
213    /// let f = P.from_terms([(6, 0), (3, 1)].into_iter());
214    /// assert_el_eq!(P, P.from_terms([(2, 0), (1, 1)].into_iter()), P.normalize(f));
215    /// ```
216    /// 
217    fn normalize(&self, mut f: El<Self>) -> El<Self>
218        where <<Self::Type as RingExtension>::BaseRing as RingStore>::Type: DivisibilityRing + Domain
219    {
220        if self.is_zero(&f) {
221            return f;
222        } else if let Some(inv_lc) = self.base_ring().invert(self.lc(&f).unwrap()) {
223            self.inclusion().mul_assign_ref_map(&mut f, &inv_lc);
224            return f;
225        } else {
226            let lc = self.lc(&f).unwrap();
227            return self.from_terms(self.terms(&f).map(|(c, i)| (self.base_ring().checked_div(c, &lc).unwrap(), i)));
228        }
229    }
230
231    ///
232    /// See [`PolyRing::evaluate()`].
233    /// 
234    fn evaluate<R, H>(&self, f: &El<Self>, value: &R::Element, hom: H) -> R::Element
235        where R: ?Sized + RingBase,
236            H: Homomorphism<<<Self::Type as RingExtension>::BaseRing as RingStore>::Type, R>
237    {
238        self.get_ring().evaluate(f, value, hom)
239    }
240
241    fn into_lifted_hom<P, H>(self, from: P, hom: H) -> CoefficientHom<P, Self, H>
242        where P: RingStore,
243            P::Type: PolyRing,
244            H: Homomorphism<<<P::Type as RingExtension>::BaseRing as RingStore>::Type, <<Self::Type as RingExtension>::BaseRing as RingStore>::Type>
245    {
246        CoefficientHom {
247            from: from,
248            to: self,
249            hom: hom
250        }
251    }
252
253    fn lifted_hom<'a, P, H>(&'a self, from: P, hom: H) -> CoefficientHom<P, &'a Self, H>
254        where P: RingStore,
255            P::Type: PolyRing,
256            H: Homomorphism<<<P::Type as RingExtension>::BaseRing as RingStore>::Type, <<Self::Type as RingExtension>::BaseRing as RingStore>::Type>
257    {
258        self.into_lifted_hom(from, hom)
259    }
260    
261    ///
262    /// Invokes the function with a wrapped version of the indeterminate of this poly ring.
263    /// Use for convenient creation of polynomials.
264    /// 
265    /// Note however that [`PolyRingStore::from_terms()`] might be more performant.
266    /// 
267    /// # Example
268    /// ```
269    /// use feanor_math::assert_el_eq;
270    /// use feanor_math::ring::*;
271    /// use feanor_math::rings::poly::*;
272    /// use feanor_math::homomorphism::*;
273    /// use feanor_math::rings::zn::zn_64::*;
274    /// use feanor_math::rings::poly::dense_poly::*;
275    /// let base_ring = Zn::new(7);
276    /// let poly_ring = DensePolyRing::new(base_ring, "X");
277    /// let f_version1 = poly_ring.from_terms([(base_ring.int_hom().map(3), 0), (base_ring.int_hom().map(2), 1), (base_ring.one(), 3)].into_iter());
278    /// let f_version2 = poly_ring.with_wrapped_indeterminate_dyn(|x| [3 + 2 * x + x.pow_ref(3)]).into_iter().next().unwrap();
279    /// assert_el_eq!(poly_ring, f_version1, f_version2);
280    /// ```
281    /// 
282    #[stability::unstable(feature = "enable")]
283    fn with_wrapped_indeterminate_dyn<'a, F, T>(&'a self, f: F) -> Vec<El<Self>>
284        where F: FnOnce(&RingElementWrapper<&'a Self>) -> T,
285            T: IntoIterator<Item = RingElementWrapper<&'a Self>>
286    {
287        let wrapped_indet = RingElementWrapper::new(self, self.indeterminate());
288        f(&wrapped_indet).into_iter().map(|f| f.unwrap()).collect()
289    }
290
291    fn with_wrapped_indeterminate<'a, F, const M: usize>(&'a self, f: F) -> [El<Self>; M]
292        where F: FnOnce(&RingElementWrapper<&'a Self>) -> [RingElementWrapper<&'a Self>; M]
293    {
294        let wrapped_indet = RingElementWrapper::new(self, self.indeterminate());
295        let mut result_it = f(&wrapped_indet).into_iter();
296        return std::array::from_fn(|_| result_it.next().unwrap().unwrap());
297    }
298    
299    #[stability::unstable(feature = "enable")]
300    fn balance_poly(&self, f: &mut El<Self>) -> Option<El<<Self::Type as RingExtension>::BaseRing>>
301        where <<Self::Type as RingExtension>::BaseRing as RingStore>::Type: DivisibilityRing
302    {
303        self.get_ring().balance_poly(f)
304    }
305}
306
307pub struct CoefficientHom<PFrom, PTo, H>
308    where PFrom: RingStore,
309        PTo: RingStore,
310        PFrom::Type: PolyRing,
311        PTo::Type: PolyRing,
312        H: Homomorphism<<<PFrom::Type as RingExtension>::BaseRing as RingStore>::Type, <<PTo::Type as RingExtension>::BaseRing as RingStore>::Type>
313{
314    from: PFrom,
315    to: PTo,
316    hom: H
317}
318
319impl<PFrom, PTo, H> Homomorphism<PFrom::Type, PTo::Type> for CoefficientHom<PFrom, PTo, H>
320    where PFrom: RingStore,
321        PTo: RingStore,
322        PFrom::Type: PolyRing,
323        PTo::Type: PolyRing,
324        H: Homomorphism<<<PFrom::Type as RingExtension>::BaseRing as RingStore>::Type, <<PTo::Type as RingExtension>::BaseRing as RingStore>::Type>
325{
326    type DomainStore = PFrom;
327    type CodomainStore = PTo;
328
329    fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
330        &self.to
331    }
332
333    fn domain<'a>(&'a self) -> &'a Self::DomainStore {
334        &self.from
335    }
336
337    fn map(&self, x: <PFrom::Type as RingBase>::Element) -> <PTo::Type as RingBase>::Element {
338        self.map_ref(&x)
339    }
340
341    fn map_ref(&self, x: &<PFrom::Type as RingBase>::Element) -> <PTo::Type as RingBase>::Element {
342        self.to.get_ring().map_terms(self.from.get_ring(), x, &self.hom)
343    }
344}
345
346impl<R: RingStore> PolyRingStore for R
347    where R::Type: PolyRing
348{}
349
350pub fn derive_poly<P>(poly_ring: P, poly: &El<P>) -> El<P>
351    where P: PolyRingStore,
352        P::Type: PolyRing
353{
354    poly_ring.from_terms(poly_ring.terms(poly)
355        .filter(|(_, i)| *i > 0)
356        .map(|(c, i)| (poly_ring.base_ring().int_hom().mul_ref_fst_map(c, i as i32), i - 1))
357    )
358}
359
360pub mod generic_impls {
361    use crate::ring::*;
362    use super::PolyRing;
363    use crate::homomorphism::*;
364
365    #[allow(type_alias_bounds)]
366    #[stability::unstable(feature = "enable")]
367    pub type Homomorphism<P1: PolyRing, P2: PolyRing> = <<P2::BaseRing as RingStore>::Type as CanHomFrom<<P1::BaseRing as RingStore>::Type>>::Homomorphism;
368
369    #[stability::unstable(feature = "enable")]
370    pub fn has_canonical_hom<P1: PolyRing, P2: PolyRing>(from: &P1, to: &P2) -> Option<Homomorphism<P1, P2>> 
371        where <P2::BaseRing as RingStore>::Type: CanHomFrom<<P1::BaseRing as RingStore>::Type>
372    {
373        to.base_ring().get_ring().has_canonical_hom(from.base_ring().get_ring())
374    }
375
376    #[stability::unstable(feature = "enable")]
377    pub fn map_in<P1: PolyRing, P2: PolyRing>(from: &P1, to: &P2, el: P1::Element, hom: &Homomorphism<P1, P2>) -> P2::Element
378        where <P2::BaseRing as RingStore>::Type: CanHomFrom<<P1::BaseRing as RingStore>::Type>
379    {
380        let mut result = to.zero();
381        to.add_assign_from_terms(&mut result, from.terms(&el).map(|(c, i)| (to.base_ring().get_ring().map_in(from.base_ring().get_ring(), from.base_ring().clone_el(c), hom), i)));
382        return result;
383    }
384
385    #[allow(type_alias_bounds)]
386    #[stability::unstable(feature = "enable")]
387    pub type Isomorphism<P1: PolyRing, P2: PolyRing> = <<P2::BaseRing as RingStore>::Type as CanIsoFromTo<<P1::BaseRing as RingStore>::Type>>::Isomorphism;
388
389    #[stability::unstable(feature = "enable")]
390    pub fn map_out<P1: PolyRing, P2: PolyRing>(from: &P1, to: &P2, el: P2::Element, iso: &Isomorphism<P1, P2>) -> P1::Element
391        where <P2::BaseRing as RingStore>::Type: CanIsoFromTo<<P1::BaseRing as RingStore>::Type>
392    {
393        let mut result = from.zero();
394        from.add_assign_from_terms(&mut result, to.terms(&el).map(|(c, i)| (to.base_ring().get_ring().map_out(from.base_ring().get_ring(), to.base_ring().clone_el(c), iso), i)));
395        return result;
396    }
397
398    #[stability::unstable(feature = "enable")]
399    pub fn dbg_poly<P: PolyRing>(ring: &P, el: &P::Element, out: &mut std::fmt::Formatter, unknown_name: &str, env: EnvBindingStrength) -> std::fmt::Result {
400        if env >= EnvBindingStrength::Product {
401            write!(out, "(")?;
402        }
403        let mut terms = ring.terms(el);
404        let print_unknown = |i: usize, out: &mut std::fmt::Formatter| {
405            if i == 0 {
406                // print nothing
407                Ok(())
408            } else if i == 1 {
409                write!(out, "{}", unknown_name)
410            } else {
411                write!(out, "{}^{}", unknown_name, i)
412            }
413        };
414        if let Some((c, i)) = terms.next() {
415            ring.base_ring().get_ring().dbg_within(c, out, if i == 0 { EnvBindingStrength::Sum } else { EnvBindingStrength:: Product })?;
416            print_unknown(i, out)?;
417        } else {
418            write!(out, "0")?;
419        }
420        while let Some((c, i)) = terms.next() {
421            write!(out, " + ")?;
422            ring.base_ring().get_ring().dbg_within(c, out, if i == 0 { EnvBindingStrength::Sum } else { EnvBindingStrength:: Product })?;
423            print_unknown(i, out)?;
424        }
425        if env >= EnvBindingStrength::Product {
426            write!(out, ")")?;
427        }
428        return Ok(());
429    }
430}
431
432pub fn transpose_indeterminates<P1, P2, H>(from: P1, to: P2, base_hom: H) -> impl Homomorphism<P1::Type, P2::Type>
433    where P1: RingStore, P1::Type: PolyRing,
434        P2: RingStore, P2::Type: PolyRing,
435        <<P1::Type as RingExtension>::BaseRing as RingStore>::Type: PolyRing,
436        <<P2::Type as RingExtension>::BaseRing as RingStore>::Type: PolyRing,
437        H: Homomorphism<<<<<P1::Type as RingExtension>::BaseRing as RingStore>::Type as RingExtension>::BaseRing as RingStore>::Type,
438            <<<<P2::Type as RingExtension>::BaseRing as RingStore>::Type as RingExtension>::BaseRing as RingStore>::Type>
439{
440    LambdaHom::new(from, to, move |from, to, x| {
441        let mut result_terms: HashMap<usize, Vec<(_, usize)>> = HashMap::new();
442        for (f, i) in from.terms(x) {
443            for (c, j) in from.base_ring().terms(f) {
444                match result_terms.entry(j) {
445                    std::collections::hash_map::Entry::Occupied(mut e) => { e.get_mut().push((base_hom.map_ref(c), i)); },
446                    std::collections::hash_map::Entry::Vacant(e) => { _ = e.insert(vec![(base_hom.map_ref(c), i)]); }
447                }
448            }
449        }
450        return to.from_terms(result_terms.into_iter().map(|(j, f)| (to.base_ring().from_terms(f.into_iter()), j)));
451    })
452}
453
454#[cfg(any(test, feature = "generic_tests"))]
455pub mod generic_tests {
456    use super::*;
457
458    pub fn test_poly_ring_axioms<R: PolyRingStore, I: Iterator<Item = El<<R::Type as RingExtension>::BaseRing>>>(ring: R, interesting_base_ring_elements: I)
459        where R::Type: PolyRing
460    {    
461        let x = ring.indeterminate();
462        let elements = interesting_base_ring_elements.collect::<Vec<_>>();
463        
464        // test linear independence of X
465        for a in &elements {
466            for b in &elements {
467                for c in &elements {
468                    for d in &elements {
469                        let a_bx = ring.add(ring.inclusion().map_ref(a), ring.mul_ref_snd(ring.inclusion().map_ref(b), &x));
470                        let c_dx = ring.add(ring.inclusion().map_ref(c), ring.mul_ref_snd(ring.inclusion().map_ref(d), &x));
471                        assert!(ring.eq_el(&a_bx, &c_dx) == (ring.base_ring().eq_el(a, c) && ring.base_ring().eq_el(b, d)));
472                    }
473                }
474            }
475        }
476        
477        // elementwise addition follows trivially from the ring axioms
478
479        // technically, convoluted multiplication follows from the ring axioms too, but test it anyway
480        for a in &elements {
481            for b in &elements {
482                for c in &elements {
483                    for d in &elements {
484                        let a_bx = ring.add(ring.inclusion().map_ref(a), ring.mul_ref_snd(ring.inclusion().map_ref(b), &x));
485                        let c_dx = ring.add(ring.inclusion().map_ref(c), ring.mul_ref_snd(ring.inclusion().map_ref(d), &x));
486                        let result = <_ as RingStore>::sum(&ring, [
487                            ring.mul(ring.inclusion().map_ref(a), ring.inclusion().map_ref(c)),
488                            ring.mul(ring.inclusion().map_ref(a), ring.mul_ref_snd(ring.inclusion().map_ref(d), &x)),
489                            ring.mul(ring.inclusion().map_ref(b), ring.mul_ref_snd(ring.inclusion().map_ref(c), &x)),
490                            ring.mul(ring.inclusion().map_ref(b), ring.mul(ring.inclusion().map_ref(d), ring.pow(ring.clone_el(&x), 2)))
491                        ].into_iter());
492                        assert_el_eq!(ring, result, ring.mul(a_bx, c_dx));
493                    }
494                }
495            }
496        }
497
498        // test terms(), from_terms()
499        for a in &elements {
500            for b in &elements {
501                for c in &elements {
502                    let f = <_ as RingStore>::sum(&ring, [
503                        ring.inclusion().map_ref(a),
504                        ring.mul_ref_snd(ring.inclusion().map_ref(b), &x),
505                        ring.mul(ring.inclusion().map_ref(c), ring.pow(ring.clone_el(&x), 3))
506                    ].into_iter());
507                    let actual = ring.from_terms([(ring.base_ring().clone_el(a), 0), (ring.base_ring().clone_el(c), 3), (ring.base_ring().clone_el(b), 1)].into_iter());
508                    assert_el_eq!(ring, f, actual);
509                    assert_el_eq!(ring, f, ring.from_terms(ring.terms(&f).map(|(c, i)| (ring.base_ring().clone_el(c), i))));
510                }
511            }
512        }
513
514        // test div_rem_monic()
515        for a in &elements {
516            for b in &elements {
517                for c in &elements {
518                    let f = ring.from_terms([(ring.base_ring().clone_el(a), 0), (ring.base_ring().clone_el(b), 3)].into_iter());
519                    let g = ring.from_terms([(ring.base_ring().negate(ring.base_ring().clone_el(c)), 0), (ring.base_ring().one(), 1)].into_iter());
520
521                    let (quo, rem) = ring.div_rem_monic(ring.clone_el(&f), &g);
522                    assert_el_eq!(
523                        &ring,
524                        &ring.from_terms([(ring.base_ring().add_ref_fst(a, ring.base_ring().mul_ref_fst(b, ring.base_ring().pow(ring.base_ring().clone_el(c), 3))), 0)].into_iter()),
525                        &rem
526                    );
527                    assert_el_eq!(
528                        &ring,
529                        &f,
530                        &ring.add(rem, ring.mul(quo, g))
531                    );
532                }
533            }
534        }
535
536        // test evaluate()
537        let hom = ring.base_ring().int_hom();
538        let base_ring = hom.codomain();
539        let f = ring.from_terms([(hom.map(1), 0), (hom.map(3), 1), (hom.map(7), 3)].into_iter());
540        for a in &elements {
541            assert_el_eq!(
542                &base_ring,
543                &base_ring.add(base_ring.one(), base_ring.add(base_ring.mul_ref_snd(hom.map(3), a), base_ring.mul(hom.map(7), base_ring.pow(base_ring.clone_el(a), 3)))),
544                &ring.evaluate(&f, a, &base_ring.identity())
545            )
546        }
547    }
548}
feanor_math/rings/poly/mod.rs

feanor_math/rings/poly/
mod.rs
