yui_core/conc/poly/
poly.rs

1//! Polynomial: a linear combination of monomials over a ring `R`.
2//!
3//! The base type [`PolyBase<X, R>`] is parameterized by the monomial type `X`
4//! (any [`Mono`]) and the coefficient ring `R`. Concrete aliases cover the
5//! common cases:
6//!
7//! | Variables | Ordinary             | Laurent              |
8//! |-----------|----------------------|----------------------|
9//! | 1         | [`Poly<X, R>`]       | [`LPoly<X, R>`]      |
10//! | 2         | [`Poly2<X, Y, R>`]   | [`LPoly2<X, Y, R>`]  |
11//! | 3         | [`Poly3<X, Y, Z, R>`]| [`LPoly3<X, Y, Z, R>`] |
12//! | n (indexed `Xᵢ`) | [`PolyN<X, R>`]      | [`LPolyN<X, R>`]     |
13//!
14//! See: <https://en.wikipedia.org/wiki/Polynomial_ring>,
15//! <https://en.wikipedia.org/wiki/Laurent_polynomial>
16
17use std::fmt::{Display, Debug};
18use std::ops::{Add, AddAssign, Sub, SubAssign, Mul, MulAssign, Neg, DivAssign, RemAssign, Div, Rem};
19use std::str::FromStr;
20use delegate::delegate;
21use num_traits::{Zero, One, Pow};
22use auto_impl_ops::auto_ops;
23
24use crate::abst::{MathType, AddMon, AddMonOps, AddGrp, AddGrpOps, Mon, MonOps, Ring, RingOps, EucRing, EucRingOps, Field, FieldOps};
25use crate::lc::Lc;
26use crate::util::parse_err::ParseErr;
27use super::{MultiDeg, Var, Var2, Var3,MultiVar, Mono, MonoOrd};
28
29/// Univariate polynomial `R[X]`.
30pub type Poly  <const X: char, R> = PolyBase<Var<X, usize>, R>;
31/// Univariate Laurent polynomial `R[X, X⁻¹]`.
32pub type LPoly <const X: char, R> = PolyBase<Var<X, isize>, R>;
33
34/// Bivariate polynomial `R[X, Y]`.
35pub type Poly2 <const X: char, const Y: char, R> = PolyBase<Var2<X, Y, usize>, R>;
36/// Bivariate Laurent polynomial `R[X, X⁻¹, Y, Y⁻¹]`.
37pub type LPoly2<const X: char, const Y: char, R> = PolyBase<Var2<X, Y, isize>, R>;
38
39/// Trivariate polynomial `R[X, Y, Z]`.
40pub type Poly3 <const X: char, const Y: char, const Z: char, R> = PolyBase<Var3<X, Y, Z, usize>, R>;
41/// Trivariate Laurent polynomial.
42pub type LPoly3<const X: char, const Y: char, const Z: char, R> = PolyBase<Var3<X, Y, Z, isize>, R>;
43
44/// Multivariate polynomial in indexed variables `X₀, X₁, …`.
45pub type PolyN <const X: char, R> = PolyBase<MultiVar<X, usize>, R>;
46/// Multivariate Laurent polynomial in indexed variables `X₀, X₁, …`.
47pub type LPolyN<const X: char, R> = PolyBase<MultiVar<X, isize>, R>;
48
49/// A polynomial: a linear combination of monomials `X` with coefficients in `R`.
50///
51/// Internally a [`Lc<X, R>`](crate::lc::Lc) — a sparse map from monomial to coefficient.
52#[derive(Clone, PartialEq, Eq, Default)]
53#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
54#[cfg_attr(feature = "serde", serde(transparent))]
55pub struct PolyBase<X, R>
56where
57    X: Mono,
58    R: Ring, for<'x> &'x R: RingOps<R>
59{
60    data: Lc<X, R>,
61    #[cfg_attr(feature = "serde", serde(skip))]
62    zero: (X, R)
63}
64
65impl<X, R> PolyBase<X, R>
66where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
67    fn new(data: Lc<X, R>) -> Self {
68        Self { data, zero: (X::one(), R::zero()) }
69    }
70
71    pub fn from_const(r: R) -> Self {
72        Self::from((X::one(), r))
73    }
74
75    pub fn inner(&self) -> &Lc<X, R> {
76        &self.data
77    }
78
79    delegate! {
80        to self.data {
81            pub fn nterms(&self) -> usize;
82            pub fn any_term(&self) -> Option<(&X, &R)>;
83            #[call(is_singleton)] pub fn is_mono(&self) -> bool;
84            #[call(as_singleton)] pub fn as_mono(&self) -> Option<X>;
85            pub fn coeff(&self, x: &X) -> &R;
86            pub fn iter(&self) -> impl Iterator<Item = (&X, &R)>;
87        }
88    }
89
90    pub fn coeff_for(&self, i: X::Deg) -> &R {
91        self.data.coeff(&X::from(i))
92    }
93
94    pub fn is_const(&self) -> bool {
95        self.iter().all(|(x, _)| x.is_one())
96    }
97
98    pub fn const_term(&self) -> &R {
99        self.coeff(&X::one())
100    }
101
102    pub fn lead_term(&self) -> (&X, &R) {
103        self.iter().max_by(|t1, t2| MonoOrd::cmp_grlex(t1.0, t2.0))
104            .unwrap_or((&self.zero.0, &self.zero.1))
105    }
106
107    pub fn lead_coeff(&self) -> &R {
108        self.lead_term().1
109    }
110
111    pub fn lead_deg(&self) -> X::Deg {
112        self.lead_term().0.deg()
113    }
114
115    pub fn sort_terms_by<F>(&self, cmp: F) -> impl Iterator<Item = (&X, &R)>
116    where F: Fn(&X, &X) -> std::cmp::Ordering {
117        self.data.sort_terms_by(cmp)
118    }
119
120    pub fn to_string_by<F>(&self, cmp: F, descending: bool) -> String
121    where F: Fn(&X, &X) -> std::cmp::Ordering {
122        self.data.to_string_by(cmp, descending)
123    }
124}
125
126macro_rules! impl_var_specific {
127    ($I:ty) => {
128        // Univar
129        impl<const X: char, R> PolyBase<Var<X, $I>, R>
130        where R: Ring, for<'x> &'x R: RingOps<R> {
131            pub fn variable() -> Self {
132                Self::from(Self::mono(1))
133            }
134
135            pub fn mono(i: $I) -> Var<X, $I> {
136                Var::from(i)
137            }
138
139            pub fn eval(&self, x: &R) -> R
140            where for<'x> &'x R: Pow<$I, Output = R> {
141                R::sum(self.iter().map(|(i, r)| {
142                    r * i.eval(x)
143                }))
144            }
145        }
146
147        // Bivar
148        impl<const X: char, const Y: char, R> PolyBase<Var2<X, Y, $I>, R>
149        where R: Ring, for<'x> &'x R: RingOps<R> {
150            pub fn variable(i: usize) -> Self {
151                assert!(i < 2);
152                let d = if i == 0 { (1, 0) } else { (0, 1) };
153                Self::from(Var2::from(d))
154            }
155
156            pub fn mono(i: $I, j: $I) -> Var2<X, Y, $I> {
157                Var2::from((i, j))
158            }
159
160            pub fn eval(&self, x: &R, y: &R) -> R
161            where for<'x> &'x R: Pow<$I, Output = R> {
162                R::sum(self.iter().map(|(i, r)| {
163                    r * i.eval(x, y)
164                }))
165            }
166        }
167
168        // Trivar
169        impl<const X: char, const Y: char, const Z: char, R> PolyBase<Var3<X, Y, Z, $I>, R>
170        where R: Ring, for<'x> &'x R: RingOps<R> {
171            pub fn variable(i: usize) -> Self {
172                assert!(i < 3);
173                let d = match i {
174                    0 => (1, 0, 0),
175                    1 => (0, 1, 0),
176                    2 => (0, 0, 1),
177                    _ => panic!()
178                };
179                Self::from(Var3::from(d))
180            }
181
182            pub fn mono(i: $I, j: $I, k: $I) -> Var3<X, Y, Z, $I> {
183                Var3::from((i, j, k))
184            }
185
186            pub fn eval(&self, x: &R, y: &R, z: &R) -> R
187            where for<'x> &'x R: Pow<$I, Output = R> {
188                R::sum(self.iter().map(|(i, r)| {
189                    r * i.eval(x, y, z)
190                }))
191            }
192        }
193
194        // MultiVar
195        impl<const X: char, R> PolyBase<MultiVar<X, $I>, R>
196        where R: Ring, for<'x> &'x R: RingOps<R> {
197            pub fn variable(i: usize) -> Self {
198                let d = MultiDeg::from((i, 1));
199                Self::from(MultiVar::from(d)) // x^1
200            }
201
202            pub fn mono<const N: usize>(degs: [$I; N]) -> MultiVar<X, $I> {
203                MultiVar::from(degs)
204            }
205
206            pub fn lead_term_for(&self, k: usize) -> Option<(&MultiVar<X, $I>, &R)> {
207                self.iter()
208                    .filter(|(x, _)| x.deg_for(k) > 0)
209                    .max_by(|(x, _), (y, _)|
210                        Ord::cmp( &x.deg_for(k), &y.deg_for(k))
211                        .then_with(||
212                            MultiVar::cmp_grlex(&x, &y)
213                        )
214                    )
215            }
216        }
217    };
218}
219
220impl_var_specific!(usize);
221impl_var_specific!(isize);
222
223impl<X, R> From<X> for PolyBase<X, R>
224where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
225    fn from(x: X) -> Self {
226        Self::from((x, R::one()))
227    }
228}
229
230impl<X, R> From<(X, R)> for PolyBase<X, R>
231where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
232    fn from(pair: (X, R)) -> Self {
233        let t = Lc::from(pair);
234        Self::from(t)
235    }
236}
237
238impl<X, R> FromIterator<(X, R)> for PolyBase<X, R>
239where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
240    fn from_iter<T: IntoIterator<Item = (X, R)>>(iter: T) -> Self {
241        Self::from(Lc::from_iter(iter))
242    }
243}
244
245impl<X, R> From<Lc<X, R>> for PolyBase<X, R>
246where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
247    fn from(data: Lc<X, R>) -> Self {
248        Self::new(data)
249    }
250}
251
252impl<X, R> From<PolyBase<X, R>> for Lc<X, R>
253where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
254    fn from(poly: PolyBase<X, R>) -> Self {
255        poly.data
256    }
257}
258
259impl<X, R> FromStr for PolyBase<X, R>
260where X: Mono + FromStr, R: Ring + FromStr, for<'x> &'x R: RingOps<R> {
261    type Err = ParseErr;
262
263    fn from_str(s: &str) -> Result<Self, Self::Err> {
264        if let Ok(r) = R::from_str(s) {
265            Ok(Self::from_const(r))
266        } else if let Ok(x) = X::from_str(s) {
267            Ok(Self::from(x))
268        } else {
269            // TODO support more complex format.
270            Err(ParseErr::invalid(s, &Self::math_symbol()))
271        }
272    }
273}
274
275impl<X, R> IntoIterator for PolyBase<X, R>
276where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
277    type Item = (X, R);
278    type IntoIter = <Lc<X, R> as IntoIterator>::IntoIter;
279
280    fn into_iter(self) -> Self::IntoIter {
281        self.data.into_iter()
282    }
283}
284
285impl<X, R> Display for PolyBase<X, R>
286where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
287    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
288        f.write_str(&self.to_string_by(X::cmp, true))
289    }
290}
291
292impl<X, R> Debug for PolyBase<X, R>
293where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
294    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
295        Display::fmt(self, f)
296    }
297}
298
299impl<X, R> Zero for PolyBase<X, R>
300where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
301    fn zero() -> Self {
302        Self::from(Lc::zero())
303    }
304
305    fn is_zero(&self) -> bool {
306        self.data.is_zero()
307    }
308}
309
310impl<X, R> One for PolyBase<X, R>
311where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
312    fn one() -> Self {
313        Self::from((X::one(), R::one()))
314    }
315
316    fn is_one(&self) -> bool {
317        self.is_const() && self.const_term().is_one()
318    }
319}
320
321impl<X, R> Neg for PolyBase<X, R>
322where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
323    type Output = Self;
324    fn neg(self) -> Self::Output {
325        Self::from(-self.data)
326    }
327}
328
329impl<X, R> Neg for &PolyBase<X, R>
330where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
331    type Output = PolyBase<X, R>;
332    fn neg(self) -> Self::Output {
333        PolyBase::from(-&self.data)
334    }
335}
336
337macro_rules! impl_assop {
338    ($trait:ident, $method:ident) => {
339        #[auto_ops]
340        impl<X, R> $trait<&PolyBase<X, R>> for PolyBase<X, R>
341        where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
342            fn $method(&mut self, rhs: &PolyBase<X, R>) {
343                self.data.$method(&rhs.data)
344            }
345        }
346    };
347}
348
349impl_assop!(AddAssign, add_assign);
350impl_assop!(SubAssign, sub_assign);
351
352#[auto_ops]
353impl<X, R> MulAssign<&R> for PolyBase<X, R>
354where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
355    fn mul_assign(&mut self, rhs: &R) {
356        self.data *= rhs
357    }
358}
359
360#[auto_ops]
361impl<X, R> MulAssign<&PolyBase<X, R>> for PolyBase<X, R>
362where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
363    fn mul_assign(&mut self, rhs: &PolyBase<X, R>) {
364        if rhs.is_one() {
365            // do nothing
366        } else if rhs.is_const() {
367            *self *= rhs.const_term()
368        } else if self.is_const() {
369            *self = rhs * self.const_term()
370        } else {
371            self.data *= &rhs.data
372        }
373    }
374}
375
376macro_rules! impl_pow_unsigned {
377    ($t:ty) => {
378        impl<X, R> Pow<$t> for &PolyBase<X, R>
379        where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
380            type Output = PolyBase<X, R>;
381            fn pow(self, n: $t) -> Self::Output {
382                let mut res = PolyBase::one();
383                for _ in 0..n {
384                    res *= self
385                }
386                res
387            }
388        }
389    };
390}
391
392impl_pow_unsigned!(u32);
393impl_pow_unsigned!(u64);
394impl_pow_unsigned!(usize);
395
396macro_rules! impl_pow_signed {
397    ($t:ty) => {
398        impl<X, R> Pow<$t> for &PolyBase<X, R>
399        where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
400            type Output = PolyBase<X, R>;
401            fn pow(self, n: $t) -> Self::Output {
402                if n >= 0 {
403                    self.pow(n as usize)
404                } else {
405                    let inv = self.inv().unwrap();
406                    (&inv).pow(-n as usize)
407                }
408            }
409        }
410    }
411}
412
413impl_pow_signed!(i32);
414impl_pow_signed!(i64);
415impl_pow_signed!(isize);
416
417macro_rules! impl_alg_op {
418    ($trait:ident) => {
419        impl<X, R> $trait<Self> for PolyBase<X, R>
420        where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {}
421
422        impl<X, R> $trait<PolyBase<X, R>> for &PolyBase<X, R>
423        where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {}
424    };
425}
426
427impl_alg_op!(AddMonOps);
428impl_alg_op!(AddGrpOps);
429impl_alg_op!(MonOps);
430impl_alg_op!(RingOps);
431
432impl<X, R> MathType for PolyBase<X, R>
433where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
434    fn math_symbol() -> String {
435        format!("{}[{}]", R::math_symbol(), X::math_symbol())
436    }
437}
438
439impl<X, R> AddMon for PolyBase<X, R>
440where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {}
441
442impl<X, R> AddGrp for PolyBase<X, R>
443where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {}
444
445impl<X, R> Mon for PolyBase<X, R>
446where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {}
447
448impl<X, R> Ring for PolyBase<X, R>
449where X: Mono, R: Ring, for<'x> &'x R: RingOps<R> {
450    fn inv(&self) -> Option<Self> {
451        if self.nterms() != 1 {
452            return None
453        }
454
455        let (x, a) = self.any_term()?; // (a x^i)^{-1} = a^{-1} x^{-i}
456        let (xinv, ainv) = (x.inv()?, a.inv()?);
457        let inv = Self::from((xinv, ainv));
458        Some(inv)
459    }
460
461    fn is_unit(&self) -> bool {
462        if self.nterms() == 1 {
463            let (x, a) = self.any_term().unwrap();
464            x.is_unit() && a.is_unit()
465        } else {
466            false
467        }
468    }
469
470    fn normalizing_unit(&self) -> Self {
471        let u = self.lead_coeff().normalizing_unit();
472        Self::from_const(u)
473    }
474}
475
476// UPoly over R: Field
477
478impl<const X: char, R> Poly<X, R>
479where R: Field, for<'x> &'x R: FieldOps<R> {
480    pub fn div_rem(&self, rhs: &Self) -> (Self, Self) {
481        let iter = |f: Self, g: &Self| -> (Self, Self) {
482            if f.lead_deg() < g.lead_deg() {
483                return (Self::zero(), f)
484            }
485
486            let (i, a) = f.lead_term(); // ax^i
487            let (j, b) = g.lead_term(); // bx^j
488
489            let k = i.deg() - j.deg(); // >= 0
490            let c = a / b;
491            let x = Var::from(k);
492            let q = Poly::from((x, c));   // cx^k = (a/b) x^{i-j}.
493            let r = f - &q * g;
494
495            (q, r)
496        };
497
498        let mut q = Self::zero();
499        let mut r = self.clone();
500
501        let i = self.lead_deg();
502        let j =  rhs.lead_deg();
503
504        for _ in j ..= i { // passes if j > i.
505            let (q1, r1) = iter(r, rhs);
506            q += q1;
507            r = r1;
508        }
509
510        (q, r)
511    }
512}
513
514#[auto_ops]
515impl<const X: char, R> Div<&Poly<X, R>> for Poly<X, R>
516where R: Field, for<'x> &'x R: FieldOps<R> {
517    type Output = Self;
518
519    fn div(self, rhs: &Poly<X, R>) -> Self {
520        self.div_rem(rhs).0
521    }
522}
523
524#[auto_ops]
525impl<const X: char, R> Rem<&Poly<X, R>> for Poly<X, R>
526where R: Field, for<'x> &'x R: FieldOps<R> {
527    type Output = Self;
528
529    fn rem(self, rhs: &Poly<X, R>) -> Self::Output {
530        self.div_rem(rhs).1
531    }
532}
533
534impl<const X: char, R> EucRingOps<Poly<X, R>> for Poly<X, R>
535where R: Field, for<'x> &'x R: FieldOps<R> {}
536
537impl<const X: char, R> EucRingOps<Poly<X, R>> for &Poly<X, R>
538where R: Field, for<'x> &'x R: FieldOps<R> {}
539
540impl<const X: char, R> EucRing for Poly<X, R>
541where R: Field, for<'x> &'x R: FieldOps<R> {}
542
543mod tex {
544    use crate::util::tex::TeX;
545    use super::*;
546
547    impl<X, R> TeX for PolyBase<X, R>
548    where X: Mono + TeX, R: Ring + TeX, for<'x> &'x R: RingOps<R> {
549        fn tex_math_symbol() -> String {
550            format!("{}[{}]", R::tex_math_symbol(), X::tex_math_symbol())
551        }
552
553        fn tex_string(&self) -> String {
554            use crate::util::format::lc;
555            let terms = self.sort_terms_by(|x, y| X::cmp_lex(x, y).reverse()).map(|(x, r)|
556                (x.tex_string(), r.tex_string())
557            );
558            lc(terms)
559        }
560    }
561}
562
563#[cfg(test)]
564mod tests {
565    use crate::num::Ratio;
566    use super::*;
567
568    #[test]
569    fn init() {
570        type P = Poly::<'x', i32>;
571
572        let x = P::mono;
573        let f = P::from_iter([(x(0), 1), (x(1), 2), (x(2), -3)]);
574        assert_eq!(f.data.coeff(&x(0)), &1);
575        assert_eq!(f.data.coeff(&x(1)), &2);
576        assert_eq!(f.data.coeff(&x(2)), &-3);
577        assert_eq!(f.data.coeff(&x(3)), &0);
578    }
579
580    #[test]
581    fn display_poly() {
582        type P = Poly::<'x', i32>;
583
584        let x = P::mono;
585        let f = P::from_iter([(x(0), 1), (x(1), 2), (x(2), -3)]);
586        assert_eq!(&f.to_string(), "-3x² + 2x + 1");
587    }
588
589    #[test]
590    fn display_lpoly() {
591        type P = LPoly::<'x', i32>;
592
593        let x = P::mono;
594        let f = P::from_iter([(x(-1), 4), (x(0), 2), (x(2), 3)]);
595        assert_eq!(&f.to_string(), "3x² + 2 + 4x⁻¹");
596    }
597
598    #[test]
599    fn display_poly2() {
600        type P = Poly2::<'x', 'y', i32>;
601
602        let xy = P::mono;
603        let f = P::from_iter([(xy(0, 0), 3), (xy(1, 0), 2), (xy(2, 3), 3)]);
604        assert_eq!(&f.to_string(), "3x²y³ + 2x + 3");
605    }
606
607    #[test]
608    fn display_mpoly() {
609        type P = PolyN::<'x', i32>;
610
611        let xn = P::mono;
612        let f = P::from_iter([
613            (xn([0,0,0]),  3),
614            (xn([1,0,0]), -1),
615            (xn([3,0,2]),  2),
616        ]);
617        assert_eq!(&f.to_string(), "2x₀³x₂² - x₀ + 3");
618    }
619
620    #[test]
621    fn display_mlpoly() {
622        type P = LPolyN::<'x', i32>;
623
624        let xn = P::mono;
625        let f = P::from_iter([
626            (xn([ 0,0,0]), 3),
627            (xn([ 1,0,0]), 1),
628            (xn([-3,1,3]), 2),
629        ]);
630        assert_eq!(&f.to_string(), "x₀ + 3 + 2x₀⁻³x₁x₂³");
631    }
632
633    #[test]
634    fn zero() {
635        type P = Poly::<'x', i32>;
636
637        let z = P::zero();
638        assert_eq!(z, P::from_iter([]));
639        assert!(z.is_zero());
640    }
641
642    #[test]
643    fn one() {
644        type P = Poly::<'x', i32>;
645
646        let x = P::mono;
647        let p = P::one();
648        assert_eq!(p, P::from_iter([(x(0), 1)]));
649    }
650
651    #[test]
652    fn variable() {
653        type P = Poly::<'x', i32>;
654
655        let x = P::mono;
656        let p = P::variable();
657        assert_eq!(p, P::from_iter([(x(1), 1)]));
658    }
659
660    #[test]
661    fn variable_bivar() {
662        type P = Poly2::<'x', 'y', i32>;
663
664        let xy = P::mono;
665        let p = P::variable(0);
666        let q = P::variable(1);
667        assert_eq!(p, P::from_iter([(xy(1, 0), 1)]));
668        assert_eq!(q, P::from_iter([(xy(0, 1), 1)]));
669    }
670
671    #[test]
672    fn variable_mvar() {
673        type P = PolyN::<'x', i32>;
674
675        let xn = P::mono;
676        let p = P::variable(0);
677        let q = P::variable(1);
678        assert_eq!(p, P::from_iter([(xn([1, 0]), 1)]));
679        assert_eq!(q, P::from_iter([(xn([0, 1]), 1)]));
680    }
681
682    #[test]
683    fn coeff() {
684        type P = Poly::<'x', i32>;
685
686        let x = P::mono;
687        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
688
689        assert_eq!(f.coeff_for(0), &2);
690        assert_eq!(f.coeff_for(1), &3);
691        assert_eq!(f.coeff_for(2), &-4);
692        assert_eq!(f.coeff_for(3), &0);
693    }
694
695    #[test]
696    fn const_term() {
697        type P = Poly::<'x', i32>;
698        let x = P::mono;
699        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
700        assert_eq!(f.const_term(), &2);
701
702        let f = P::from_iter([(x(1), 3), (x(2), -4)]);
703        assert_eq!(f.const_term(), &0);
704    }
705
706    #[test]
707    fn lead_term() {
708        type P = Poly::<'x', i32>;
709
710        let x = P::mono;
711        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
712        let (m, a) = f.lead_term();
713
714        assert_eq!(m.deg(), 2);
715        assert_eq!(a, &-4);
716
717        let f = P::zero();
718        let (m, a) = f.lead_term();
719        assert_eq!(m.deg(), 0);
720        assert_eq!(a, &0);
721    }
722
723    #[test]
724    fn add() {
725        type P = Poly::<'x', i32>;
726
727        let x = P::mono;
728        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
729        let g = P::from_iter([(x(0), -3), (x(1), -3), (x(3), 5)]);
730
731        assert_eq!(f + g, P::from_iter([(x(0), -1), (x(1), 0), (x(2), -4), (x(3), 5)]));
732    }
733
734    #[test]
735    fn neg() {
736        type P = Poly::<'x', i32>;
737
738        let x = P::mono;
739        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
740
741        assert_eq!(-f, P::from_iter([(x(0), -2), (x(1), -3), (x(2), 4)]));
742    }
743
744    #[test]
745    fn sub() {
746        type P = Poly::<'x', i32>;
747        let x = P::mono;
748        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
749        let g = P::from_iter([(x(0), -3), (x(1), -3), (x(3), 5)]);
750        assert_eq!(f - g, P::from_iter([(x(0), 5), (x(1), 6), (x(2), -4), (x(3), -5)]));
751    }
752
753    #[test]
754    fn mul() {
755        type P = Poly::<'x', i32>;
756
757        let x = P::mono;
758        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
759        let g = P::from_iter([(x(0), -3), (x(1), -3), (x(3), 5)]);
760
761        assert_eq!(f * g, P::from_iter([(x(0), -6), (x(1), -15), (x(2), 3), (x(3), 22), (x(4), 15), (x(5), -20)]));
762    }
763
764    #[test]
765    fn mul_const() {
766        type P = Poly::<'x', i32>;
767
768        let x = P::mono;
769        let f = P::from_iter([(x(0), 2), (x(1), 3), (x(2), -4)]);
770        let g = P::from_const(3);
771
772        assert_eq!(&f * &g, P::from_iter([(x(0), 6), (x(1), 9), (x(2), -12)]));
773        assert_eq!(&g * &f, P::from_iter([(x(0), 6), (x(1), 9), (x(2), -12)]));
774    }
775
776    #[test]
777    fn pow() {
778        type P = Poly::<'x', i32>;
779
780        let x = P::mono;
781        let f = P::from_iter([(x(0), 3), (x(1), 2)]);
782
783        assert_eq!(f.pow(0), P::one());
784        assert_eq!(f.pow(1), f);
785        assert_eq!(f.pow(0), P::one());
786        assert_eq!(f.pow(2), P::from_iter([(x(0), 9), (x(1), 12), (x(2), 4)]));
787    }
788
789    #[test]
790    fn pow_laurent() {
791        type P = LPoly::<'x', i32>;
792
793        let x = P::mono;
794        let f = P::variable();
795
796        assert_eq!(f.pow(0), P::one());
797        assert_eq!(f.pow(-1), P::from((x(-1), 1)));
798        assert_eq!(f.pow(0), P::one());
799        assert_eq!(f.pow(-2), P::from((x(-2), 1)));
800    }
801
802    #[test]
803    fn inv() {
804        type P = Poly::<'x', i32>;
805
806        let x = P::mono;
807        let f = P::from_const(1);
808        assert!(f.is_unit());
809        assert_eq!(f.inv(), Some(P::from_const(1)));
810
811        let f = P::from_const(0);
812        assert!(!f.is_unit());
813        assert_eq!(f.inv(), None);
814
815        let f = P::from_const(2);
816        assert!(!f.is_unit());
817        assert_eq!(f.inv(), None);
818
819        let f = P::variable();
820        assert!(!f.is_unit());
821        assert_eq!(f.inv(), None);
822
823        let f = P::from_iter([(x(0), 1), (x(1), 1)]);
824        assert!(!f.is_unit());
825        assert_eq!(f.inv(), None);
826    }
827
828    #[test]
829    fn inv_rat() {
830        type R = Ratio<i32>;
831        type P = Poly::<'x', R>;
832
833        let x = P::mono;
834        let f = P::from_const(R::from(1));
835
836        assert!(f.is_unit());
837        assert_eq!(f.inv(), Some(P::from_const(R::from(1))));
838
839        let f = P::from_const(R::zero());
840        assert!(!f.is_unit());
841        assert_eq!(f.inv(), None);
842
843        let f = P::from_const(R::from(2));
844        assert!(f.is_unit());
845        assert_eq!(f.inv(), Some(P::from_const(R::new(1, 2))));
846
847        let f = P::variable();
848        assert!(!f.is_unit());
849        assert_eq!(f.inv(), None);
850
851        let f = P::from_iter([(x(0), R::one()), (x(1), R::one())]);
852        assert!(!f.is_unit());
853        assert_eq!(f.inv(), None);
854    }
855
856    #[test]
857    fn inv_laurent() {
858        type P = LPoly::<'x', i32>;
859
860        let x = P::mono;
861        let f = P::from_const(1);
862        assert!(f.is_unit());
863        assert_eq!(f.inv(), Some(P::from_const(1)));
864
865        let f = P::from_const(0);
866        assert!(!f.is_unit());
867        assert_eq!(f.inv(), None);
868
869        let f = P::from_const(2);
870        assert!(!f.is_unit());
871        assert_eq!(f.inv(), None);
872
873        let f = P::variable();
874        assert!(f.is_unit());
875        assert_eq!(f.inv(), Some(P::from((x(-1), 1))));
876
877        let f = P::from((x(1), 2));
878        assert!(!f.is_unit());
879        assert_eq!(f.inv(), None);
880
881        let f = P::from_iter([(x(0), 1), (x(1), 1)]);
882        assert!(!f.is_unit());
883        assert_eq!(f.inv(), None);
884    }
885
886    #[test]
887    fn inv_laurent_rat() {
888        type R = Ratio<i32>;
889        type P = LPoly::<'x', R>;
890
891        let x = P::mono;
892        let f = P::from_const(R::from(1));
893        assert!(f.is_unit());
894        assert_eq!(f.inv(), Some(P::from_const(R::from(1))));
895
896        let f = P::from_const(R::zero());
897        assert!(!f.is_unit());
898        assert_eq!(f.inv(), None);
899
900        let f = P::from_const(R::from(2));
901        assert!(f.is_unit());
902        assert_eq!(f.inv(), Some(P::from_const(R::new(1, 2))));
903
904        let f = P::variable();
905        assert!(f.is_unit());
906        assert_eq!(f.inv(), Some(P::from((x(-1), R::one()))));
907
908        let f = P::from((x(1), R::from(2)));
909        assert!(f.is_unit());
910        assert_eq!(f.inv(), Some(P::from((x(-1), R::new(1, 2)))));
911
912        let f = P::from_iter([(x(0), R::one()), (x(1), R::one())]);
913        assert!(!f.is_unit());
914        assert_eq!(f.inv(), None);
915    }
916
917    #[test]
918    fn div_rem() {
919        type R = Ratio<i32>;
920        type P = Poly::<'x', R>;
921
922        let x = P::mono;
923        let f = P::from_iter([(x(0), R::from(1)), (x(1), R::from(2)), (x(2), R::from(1))]);
924        let g = P::from_iter([(x(0), R::from(3)), (x(1), R::from(2))]);
925        let (q, r) = f.div_rem(&g);
926
927        assert_eq!(q, P::from_iter([(x(0), R::new(1, 4)), (x(1), R::new(1, 2))]));
928        assert_eq!(r, P::from_const( R::new(1, 4)) );
929        assert_eq!(f, q * &g + r);
930
931        let (q, r) = g.div_rem(&f);
932        assert_eq!(q, P::zero());
933        assert_eq!(r, g);
934    }
935
936    #[test]
937    fn from_str() {
938        type P = Poly::<'x', i32>;
939
940        assert_eq!(P::from_str("-3"), Ok(P::from_const(-3)));
941        assert_eq!(P::from_str("x"), Ok(P::variable()));
942
943        // the error names both the input and the target ring.
944        let e = P::from_str("y").unwrap_err();
945        assert_eq!(e.to_string(), "cannot parse \"y\" as Z[x]");
946
947        // TODO support more complex types
948    }
949
950    #[test]
951    fn eval_bivar() {
952        type P = Poly2::<'x', 'y', i32>;
953
954        let xy = P::mono;
955        let p = P::from_iter([(xy(0,0),3), (xy(1,0),2), (xy(0,1),-1), (xy(1,1),4)]);
956        let v = p.eval(&2, &3); // 3 + 2(2) - 1(3) + 4(2*3)
957        assert_eq!(v, 28);
958    }
959
960    #[test]
961    fn lead_term_for() {
962        type P = PolyN::<'x', i32>;
963
964        let xn = P::mono;
965        let f = P::from_iter([
966            (xn([1,2,3]), 1),
967            (xn([2,1,3]), 2),
968            (xn([0,2,4]), 3),
969            (xn([5,5,5]), 0), // should be ignored
970        ]);
971        assert_eq!(f.lead_term_for(0), Some((&xn([2,1,3]), &2)));
972        assert_eq!(f.lead_term_for(1), Some((&xn([1,2,3]), &1)));
973        assert_eq!(f.lead_term_for(2), Some((&xn([0,2,4]), &3)));
974        assert_eq!(f.lead_term_for(3), None);
975    }
976
977    #[test]
978    #[cfg(feature = "serde")]
979    fn serialize_univar() {
980        type P = Poly::<'x', i32>;
981
982        let x = P::mono;
983        let f = P::from_iter([(x(0), 1), (x(1), 2), (x(2), -3)]);
984
985        let ser = serde_json::to_string(&f).unwrap();
986        let des = serde_json::from_str(&ser).unwrap();
987        assert_eq!(f, des);
988    }
989
990    #[test]
991    #[cfg(feature = "serde")]
992    fn serialize_bivar() {
993        type P = LPoly2::<'x', 'y', i32>;
994
995        let xy = P::mono;
996        let f = P::from_iter([
997            (xy(0, 0), 3),
998            (xy(1, 0), 1),
999            (xy(-2, 13), -3)
1000        ]);
1001
1002        let ser = serde_json::to_string(&f).unwrap();
1003        dbg!(&ser);
1004        let des = serde_json::from_str(&ser).unwrap();
1005        assert_eq!(f, des);
1006    }
1007
1008    #[test]
1009    #[cfg(feature = "serde")]
1010    fn serialize_mvar() {
1011        type P = LPolyN::<'x', i32>;
1012
1013        let xn = P::mono;
1014        let f = P::from_iter([
1015            (xn([0,0,0]),  3),
1016            (xn([1,0,0]), -1),
1017            (xn([12,0,-2]),  12),
1018        ]);
1019
1020        let ser = serde_json::to_string(&f).unwrap();
1021        let des = serde_json::from_str(&ser).unwrap();
1022        assert_eq!(f, des);
1023    }
1024
1025    #[test]
1026    fn tex() {
1027        use crate::util::tex::TeX;
1028        type P = LPolyN::<'x', i32>;
1029
1030        assert_eq!(P::tex_math_symbol(), "\\mathbb{Z}[x_1,\\ldots]");
1031
1032        let xn = P::mono;
1033        let f = P::from_iter([
1034            (xn([ 0,0,0]),   3),
1035            (xn([ 3,0,1]),  -1),
1036            (xn([-2,1,3]), -2),
1037        ]);
1038
1039        assert_eq!(f.tex_string(), "-x_0^3x_2 + 3 - 2x_0^{-2}x_1x_2^3");
1040    }
1041}
yui_core/conc/poly/poly.rs

yui_core/conc/poly/
poly.rs
