polynomial_ring/
ops.rs

1use crate::{polynomial, Polynomial, Sized};
2use auto_impl_ops::auto_ops;
3use num_traits::{One, Zero};
4use ring_algorithm::RingNormalize;
5use std::{
6    iter::{Product, Sum},
7    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Rem, RemAssign, Sub, SubAssign},
8};
9
10// additive monoid
11#[auto_ops]
12impl<M> AddAssign<&Polynomial<M>> for Polynomial<M>
13where
14    M: Sized + Zero + for<'x> AddAssign<&'x M>,
15{
16    fn add_assign(&mut self, other: &Self) {
17        let len = self.len();
18        self.extend(other.len());
19        self.coeff
20            .iter_mut()
21            .zip(other.coeff.iter())
22            .for_each(|(l, r)| *l += r);
23        if len == other.len() {
24            self.trim_zero()
25        }
26    }
27}
28
29impl<M> Zero for Polynomial<M>
30where
31    M: Sized + Zero + for<'x> AddAssign<&'x M>,
32{
33    fn zero() -> Self {
34        Self { coeff: Vec::new() }
35    }
36    fn is_zero(&self) -> bool {
37        self.deg().is_none()
38    }
39}
40
41impl<M> Sum for Polynomial<M>
42where
43    M: Sized + Zero + for<'x> AddAssign<&'x M>,
44{
45    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
46        iter.fold(Self::zero(), Add::add)
47    }
48}
49
50// additive group
51impl<G> Neg for Polynomial<G>
52where
53    G: Sized + Neg<Output = G>,
54{
55    type Output = Self;
56    fn neg(self) -> Self::Output {
57        Polynomial {
58            coeff: self.coeff.into_iter().map(|v| -v).collect(),
59        }
60    }
61}
62
63impl<G> Neg for &Polynomial<G>
64where
65    G: Sized + for<'x> From<<&'x G as Neg>::Output>,
66    for<'x> &'x G: Neg,
67{
68    type Output = Polynomial<G>;
69    fn neg(self) -> Self::Output {
70        Polynomial {
71            coeff: self.coeff.iter().map(|v| G::from(-v)).collect(),
72        }
73    }
74}
75
76#[auto_ops]
77impl<G> SubAssign<&Polynomial<G>> for Polynomial<G>
78where
79    G: Sized + Zero + for<'x> SubAssign<&'x G>,
80{
81    fn sub_assign(&mut self, other: &Self) {
82        let len = self.len();
83        self.extend(other.len());
84        self.coeff
85            .iter_mut()
86            .zip(other.coeff.iter())
87            .for_each(|(l, r)| *l -= r);
88        if len == other.len() {
89            self.trim_zero()
90        }
91    }
92}
93
94// unitary ring
95fn mul_aux<R>(sum: &mut [R], coeff: &R, vec: &[R])
96where
97    R: Sized + Clone + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,
98{
99    sum.iter_mut().zip(vec.iter()).for_each(|(l, r)| {
100        let mut t = coeff.clone();
101        t *= r;
102        *l += &t
103    });
104}
105#[auto_ops]
106impl<R> Mul for &Polynomial<R>
107where
108    R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + for<'x> MulAssign<&'x R>,
109{
110    type Output = Polynomial<R>;
111    fn mul(self, other: Self) -> Self::Output {
112        if self.is_zero() || other.is_zero() {
113            return Polynomial::<R>::zero();
114        }
115        let mut coeff = vec![R::zero(); self.len() + other.len() - 1];
116        self.coeff
117            .iter()
118            .enumerate()
119            .for_each(|(i, c)| mul_aux::<R>(&mut coeff[i..], c, &other.coeff));
120        Polynomial::<R>::new(coeff) // R may not be a domain.
121    }
122}
123
124impl<R> One for Polynomial<R>
125where
126    R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + One + for<'x> MulAssign<&'x R>,
127{
128    fn one() -> Self {
129        polynomial![R::one()]
130    }
131}
132
133impl<R> Product for Polynomial<R>
134where
135    R: Sized + Clone + Zero + for<'x> AddAssign<&'x R> + One + for<'x> MulAssign<&'x R>,
136{
137    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
138        iter.fold(Self::one(), Mul::<Polynomial<R>>::mul)
139    }
140}
141
142// field
143#[auto_ops]
144impl<K> Div for &Polynomial<K>
145where
146    K: Sized
147        + Clone
148        + Zero
149        + for<'x> AddAssign<&'x K>
150        + for<'x> SubAssign<&'x K>
151        + for<'x> MulAssign<&'x K>
152        + for<'x> DivAssign<&'x K>,
153{
154    type Output = Polynomial<K>;
155    fn div(self, other: Self) -> Self::Output {
156        let mut f = self.clone();
157        f.division(other)
158    }
159}
160
161#[auto_ops]
162impl<K> RemAssign<&Polynomial<K>> for Polynomial<K>
163where
164    K: Sized
165        + Clone
166        + Zero
167        + for<'x> AddAssign<&'x K>
168        + for<'x> SubAssign<&'x K>
169        + for<'x> MulAssign<&'x K>
170        + for<'x> DivAssign<&'x K>,
171{
172    fn rem_assign(&mut self, other: &Self) {
173        self.division(other);
174    }
175}
176
177// scalar ops
178#[auto_ops]
179impl<R> MulAssign<&R> for Polynomial<R>
180where
181    R: Sized + Zero + for<'x> MulAssign<&'x R>,
182{
183    fn mul_assign(&mut self, alpha: &R) {
184        self.coeff.iter_mut().for_each(|c| *c *= alpha);
185        self.trim_zero();
186    }
187}
188
189#[auto_ops]
190impl<R> DivAssign<&R> for Polynomial<R>
191where
192    R: Sized + for<'x> DivAssign<&'x R>,
193{
194    fn div_assign(&mut self, alpha: &R) {
195        self.coeff.iter_mut().for_each(|c| *c /= alpha);
196    }
197}
198
199impl<K> RingNormalize for Polynomial<K>
200where
201    K: Sized
202        + Clone
203        + Zero
204        + One
205        + for<'x> AddAssign<&'x K>
206        + for<'x> MulAssign<&'x K>
207        + for<'x> DivAssign<&'x K>,
208{
209    fn leading_unit(&self) -> Self {
210        if let Some(x) = self.lc() {
211            Self::from_monomial(x.clone(), 0)
212        } else {
213            Self::one()
214        }
215    }
216    fn normalize_mut(&mut self) {
217        self.monic();
218    }
219}
polynomial_ring/ops.rs

polynomial_ring/
ops.rs
