use zip_fill;
use std::ops::{Add, Div, Mul, Neg, Rem, Sub};
use crate::{complex::Complex, fft, Abs, Const, Cos, Inv, NumCast, One, Poly, Sin, Zero};
impl<T: Clone + Neg<Output = T>> Neg for &Poly<T> {
type Output = Poly<T>;
fn neg(self) -> Self::Output {
let c: Vec<_> = self.coeffs.iter().map(|i| -i.clone()).collect();
Poly { coeffs: c }
}
}
impl<T: Clone + Neg<Output = T>> Neg for Poly<T> {
type Output = Self;
fn neg(mut self) -> Self::Output {
for c in &mut self.coeffs {
*c = Neg::neg(c.clone());
}
self
}
}
impl<T: Add<Output = T> + Clone + PartialEq + Zero> Add for Poly<T> {
type Output = Self;
fn add(mut self, mut rhs: Self) -> Self {
let result = if self.degree() < rhs.degree() {
for (i, c) in self.coeffs.iter().enumerate() {
rhs[i] = rhs[i].clone() + c.clone();
}
rhs
} else {
for (i, c) in rhs.coeffs.iter().enumerate() {
self[i] = self[i].clone() + c.clone();
}
self
};
result.trim()
}
}
impl<'a, T> Add<&'a Poly<T>> for Poly<T>
where
T: Add<&'a T, Output = T> + Clone + PartialEq + Zero,
{
type Output = Self;
fn add(mut self, rhs: &'a Poly<T>) -> Self {
if self.degree() < rhs.degree() {
for (i, c) in self.coeffs.iter_mut().enumerate() {
*c = c.clone() + &rhs[i];
}
let l = self.len();
self.coeffs.extend_from_slice(&rhs.coeffs[l..]);
} else {
for (i, c) in rhs.coeffs.iter().enumerate() {
self[i] = self[i].clone() + c;
}
};
self.trim()
}
}
impl<T: Add<Output = T> + Clone + PartialEq + Zero> Add for &Poly<T> {
type Output = Poly<T>;
fn add(self, rhs: &Poly<T>) -> Poly<T> {
let zero = T::zero();
let result = zip_fill::zip_longest_with(&self.coeffs, &rhs.coeffs, &zero, |x, y| {
x.clone() + y.clone()
});
Poly::new_from_coeffs_iter(result)
}
}
impl<T: Add<Output = T> + Clone> Add<T> for Poly<T> {
type Output = Self;
fn add(mut self, rhs: T) -> Self {
self[0] = self[0].clone() + rhs;
self
}
}
impl<'a, T: Add<&'a T, Output = T> + Clone> Add<&'a T> for Poly<T> {
type Output = Self;
fn add(mut self, rhs: &'a T) -> Self {
self[0] = self[0].clone() + rhs;
self
}
}
impl<T: Add<Output = T> + Clone> Add<T> for &Poly<T> {
type Output = Poly<T>;
fn add(self, rhs: T) -> Self::Output {
self.clone().add(rhs)
}
}
macro_rules! impl_add_for_poly {
(
$(#[$meta:meta])*
$f:ty
) => {
$(#[$meta])*
impl Add<Poly<$f>> for $f {
type Output = Poly<Self>;
fn add(self, rhs: Poly<Self>) -> Poly<Self> {
rhs + self
}
}
$(#[$meta])*
impl Add<&Poly<$f>> for $f {
type Output = Poly<Self>;
fn add(self, rhs: &Poly<Self>) -> Poly<Self> {
rhs + self
}
}
};
}
impl_add_for_poly!(
f32
);
impl_add_for_poly!(
f64
);
impl_add_for_poly!(
i8
);
impl_add_for_poly!(
u8
);
impl_add_for_poly!(
i16
);
impl_add_for_poly!(
u16
);
impl_add_for_poly!(
i32
);
impl_add_for_poly!(
u32
);
impl_add_for_poly!(
i64
);
impl_add_for_poly!(
u64
);
impl_add_for_poly!(
i128
);
impl_add_for_poly!(
u128
);
impl_add_for_poly!(
isize
);
impl_add_for_poly!(
usize
);
impl<T: Clone + PartialEq + Sub<Output = T> + Zero> Sub for Poly<T> {
type Output = Self;
fn sub(mut self, mut rhs: Self) -> Self {
let result = if self.len() < rhs.len() {
for (i, c) in rhs.coeffs.iter_mut().enumerate() {
*c = self.coeffs.get(i).unwrap_or(&T::zero()).clone() - c.clone();
}
rhs
} else {
for (i, c) in rhs.coeffs.iter().enumerate() {
self[i] = self[i].clone() - c.clone();
}
self
};
result.trim()
}
}
impl<T: Clone + PartialEq + Sub<Output = T> + Zero> Sub for &Poly<T> {
type Output = Poly<T>;
fn sub(self, rhs: Self) -> Poly<T> {
let zero = T::zero();
let result = zip_fill::zip_longest_with(&self.coeffs, &rhs.coeffs, &zero, |x, y| {
x.clone() - y.clone()
});
Poly::new_from_coeffs_iter(result)
}
}
impl<T: Clone + Sub<Output = T>> Sub<T> for Poly<T> {
type Output = Self;
fn sub(mut self, rhs: T) -> Self {
self[0] = self[0].clone() - rhs;
self
}
}
impl<T: Clone + Sub<Output = T>> Sub<T> for &Poly<T> {
type Output = Poly<T>;
fn sub(self, rhs: T) -> Self::Output {
self.clone().sub(rhs)
}
}
macro_rules! impl_sub_for_poly {
(
$(#[$meta:meta])*
$f:ty
) => {
$(#[$meta])*
impl Sub<Poly<$f>> for $f {
type Output = Poly<Self>;
fn sub(self, rhs: Poly<Self>) -> Poly<Self> {
rhs.neg().add(self)
}
}
$(#[$meta])*
impl Sub<&Poly<$f>> for $f {
type Output = Poly<Self>;
fn sub(self, rhs: &Poly<Self>) -> Poly<Self> {
self.sub(rhs.clone())
}
}
};
}
impl_sub_for_poly!(
f32
);
impl_sub_for_poly!(
f64
);
impl_sub_for_poly!(
i8
);
impl_sub_for_poly!(
i16
);
impl_sub_for_poly!(
i32
);
impl_sub_for_poly!(
i64
);
impl_sub_for_poly!(
i128
);
impl_sub_for_poly!(
isize
);
impl<T: Add<Output = T> + Clone + Mul<Output = T> + PartialEq + Zero> Mul for &Poly<T> {
type Output = Poly<T>;
#[allow(clippy::suspicious_arithmetic_impl)]
fn mul(self, rhs: Self) -> Poly<T> {
if self.is_zero() || rhs.is_zero() {
return Poly::zero();
}
let new_length = self.len() + rhs.len() - 1;
debug_assert!(new_length > 0);
let mut new_coeffs: Vec<T> = vec![T::zero(); new_length];
for i in 0..self.len() {
for j in 0..rhs.len() {
let a = self.coeffs[i].clone();
let b = rhs.coeffs[j].clone();
let index = i + j;
new_coeffs[index] = new_coeffs[index].clone() + a * b;
}
}
Poly { coeffs: new_coeffs }
}
}
impl<T: Add<Output = T> + Clone + Mul<Output = T> + PartialEq + Zero> Mul for Poly<T> {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
Mul::mul(&self, &rhs)
}
}
impl<T: Add<Output = T> + Clone + Mul<Output = T> + PartialEq + Zero> Mul<&Poly<T>> for Poly<T> {
type Output = Self;
fn mul(self, rhs: &Poly<T>) -> Self {
Mul::mul(&self, rhs)
}
}
impl<T: Clone + Mul<Output = T> + PartialEq + Zero> Mul<T> for Poly<T> {
type Output = Self;
fn mul(mut self, rhs: T) -> Self {
if rhs.is_zero() {
Self::zero()
} else {
for c in &mut self.coeffs {
*c = c.clone() * rhs.clone();
}
self
}
}
}
impl<T: Clone + Mul<Output = T> + PartialEq + Zero> Mul<&T> for Poly<T> {
type Output = Self;
fn mul(mut self, rhs: &T) -> Self {
if rhs.is_zero() {
Self::zero()
} else {
for c in &mut self.coeffs {
*c = c.clone() * rhs.clone();
}
self
}
}
}
impl<T: Clone + Mul<Output = T> + PartialEq + Zero> Mul<T> for &Poly<T> {
type Output = Poly<T>;
fn mul(self, rhs: T) -> Self::Output {
self.clone().mul(rhs)
}
}
impl<T: Clone + Mul<Output = T> + PartialEq + Zero> Mul<&T> for &Poly<T> {
type Output = Poly<T>;
fn mul(self, rhs: &T) -> Self::Output {
self.clone().mul(rhs)
}
}
macro_rules! impl_mul_for_poly {
(
$(#[$meta:meta])*
$f:ty
) => {
$(#[$meta])*
impl Mul<Poly<$f>> for $f {
type Output = Poly<Self>;
fn mul(self, rhs: Poly<Self>) -> Poly<Self> {
rhs * self
}
}
$(#[$meta])*
impl Mul<&Poly<$f>> for $f {
type Output = Poly<Self>;
fn mul(self, rhs: &Poly<Self>) -> Poly<Self> {
rhs * self
}
}
};
}
impl_mul_for_poly!(
f32
);
impl_mul_for_poly!(
f64
);
impl_mul_for_poly!(
i8
);
impl_mul_for_poly!(
u8
);
impl_mul_for_poly!(
i16
);
impl_mul_for_poly!(
u16
);
impl_mul_for_poly!(
i32
);
impl_mul_for_poly!(
u32
);
impl_mul_for_poly!(
i64
);
impl_mul_for_poly!(
u64
);
impl_mul_for_poly!(
i128
);
impl_mul_for_poly!(
u128
);
impl_mul_for_poly!(
isize
);
impl_mul_for_poly!(
usize
);
impl<T> Poly<T>
where
T: Abs
+ Add<Output = T>
+ Clone
+ Const
+ Cos
+ Div<Output = T>
+ Inv
+ Mul<Output = T>
+ Neg<Output = T>
+ NumCast
+ One
+ PartialEq
+ PartialOrd
+ Sin
+ Sub<Output = T>
+ Zero,
{
#[must_use]
pub fn mul_fft(mut self, mut rhs: Self) -> Self {
if self.is_zero() || rhs.is_zero() {
return Self::zero();
}
if self.is_one() {
return rhs;
} else if rhs.is_one() {
return self;
}
let res_length = self.len() + rhs.len() - 1;
let res_degree = res_length - 1;
self.extend(res_degree);
rhs.extend(res_degree);
let a: Vec<Complex<T>> = self
.coeffs
.iter()
.map(move |x| Complex::new(x.clone(), T::zero()))
.collect();
let b: Vec<Complex<T>> = rhs
.coeffs
.iter()
.map(move |x| Complex::new(x.clone(), T::zero()))
.collect();
let a_fft = fft::fft(&a);
let b_fft = fft::fft(&b);
let y_fft: Vec<_> = a_fft.into_iter().zip(&b_fft).map(|(a, b)| a * b).collect();
let y = fft::ifft(&y_fft);
let coeffs = y.iter().map(|c| c.re.x.clone()).take(res_length);
Poly {
coeffs: coeffs.collect(),
}
}
}
impl<T: Clone + Div<Output = T> + PartialEq + Zero> Div<T> for Poly<T> {
type Output = Self;
fn div(mut self, rhs: T) -> Self {
for c in &mut self.coeffs {
*c = c.clone() / rhs.clone();
}
self.trim()
}
}
impl<T: Clone + Div<Output = T> + PartialEq + Zero> Div<T> for &Poly<T> {
type Output = Poly<T>;
fn div(self, rhs: T) -> Self::Output {
let result = self.coeffs.iter().map(|x| x.clone() / rhs.clone());
Poly::new_from_coeffs_iter(result)
}
}
impl<'a, T> Div<&'a T> for &'a Poly<T>
where
T: Clone + PartialEq + Zero,
&'a T: Div<Output = T>,
{
type Output = Poly<T>;
fn div(self, rhs: &'a T) -> Self::Output {
let result = self.coeffs.iter().map(|x| x / rhs);
Poly::new_from_coeffs_iter(result)
}
}
impl<T> Div for &Poly<T>
where
T: Clone + Inv + Mul<Output = T> + One + PartialEq + Sub<Output = T> + Zero,
{
type Output = Poly<T>;
fn div(self, rhs: &Poly<T>) -> Self::Output {
poly_div_impl(self.clone(), rhs).0
}
}
impl<T> Div for Poly<T>
where
T: Clone + Inv + Mul<Output = T> + One + PartialEq + Sub<Output = T> + Zero,
{
type Output = Self;
fn div(self, rhs: Self) -> Self::Output {
poly_div_impl(self, &rhs).0
}
}
impl<T> Rem for &Poly<T>
where
T: Clone + Inv + Mul<Output = T> + One + PartialEq + Sub<Output = T> + Zero,
{
type Output = Poly<T>;
fn rem(self, rhs: &Poly<T>) -> Self::Output {
poly_div_impl(self.clone(), rhs).1
}
}
impl<T> Rem for Poly<T>
where
T: Clone + Inv + Mul<Output = T> + One + PartialEq + Sub<Output = T> + Zero,
{
type Output = Self;
fn rem(self, rhs: Self) -> Self::Output {
poly_div_impl(self, &rhs).1
}
}
#[allow(clippy::many_single_char_names)]
fn poly_div_impl<T>(mut u: Poly<T>, v: &Poly<T>) -> (Poly<T>, Poly<T>)
where
T: Clone + Inv + Mul<Output = T> + One + PartialEq + Sub<Output = T> + Zero,
{
let (m, n) = match (u.degree(), v.degree()) {
(_, None) => panic!("Division by zero polynomial"),
(None, _) => return (Poly::zero(), Poly::zero()),
(Some(m), Some(n)) if m < n => return (Poly::zero(), u),
(Some(m), Some(n)) => (m, n),
};
let vn_rec = v.leading_coeff().inv();
let mut q = Poly {
coeffs: vec![T::zero(); m - n + 1],
};
for k in (0..=m - n).rev() {
q[k] = u[n + k].clone() * vn_rec.clone();
for j in (k..n + k).rev() {
u[j] = u[j].clone() - q[k].clone() * v[j - k].clone();
}
}
u.coeffs.truncate(n);
u.trim_mut();
(q, u)
}
impl<T: Clone + Div<Output = T> + PartialEq + Zero> Poly<T> {
pub fn div_mut(&mut self, d: &T) {
for c in &mut self.coeffs {
*c = c.clone() / d.clone();
}
self.trim_mut();
}
}
impl<T: Add<Output = T> + Clone + Mul<Output = T> + One + PartialEq + Zero> Poly<T> {
#[must_use]
pub fn powi(&self, exp: u32) -> Self {
let mut n = exp;
let mut y = Self::one();
let mut z = (*self).clone();
while n > 0 {
if n % 2 == 1 {
y = &y * &z;
}
z = &z * &z;
n /= 2;
}
y
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::poly;
#[test]
fn poly_neg() {
let p1 = poly!(1., 2.34, -4.2229);
let p2 = -&p1;
assert_eq!(p1, -p2);
}
#[test]
fn poly_add() {
assert_eq!(poly!(4., 4., 4.), poly!(1., 2., 3.) + poly!(3., 2., 1.));
assert_eq!(poly!(4., 4., 3.), poly!(1., 2., 3.) + poly!(3., 2.));
assert_eq!(poly!(4., 4., 1.), poly!(1., 2.) + poly!(3., 2., 1.));
assert_eq!(poly!(4., 4.), poly!(1., 2., 3.) + poly!(3., 2., -3.));
assert_eq!(poly!(-2., 2., 3.), poly!(1., 2., 3.) + -3.);
assert_eq!(poly!(0, 2, 3), 2 + poly!(1, 2, 3) + -3);
assert_eq!(poly!(9.0_f32, 2., 3.), 3. + poly!(1.0_f32, 2., 3.) + 5.);
let p = poly!(-2, 2, 3);
let p2 = &p + &p;
let p3 = &p2 + &p;
assert_eq!(poly!(-6, 6, 9), p3);
}
#[test]
fn poly_add_real_number() {
assert_eq!(poly!(5, 4, 3), 1 + &poly!(4, 4, 3));
assert_eq!(poly!(6, 4, 3), &poly!(5, 4, 3) + 1);
}
#[test]
fn poly_add_ref() {
let p1: Poly<i32>;
{
let p2 = poly!(1, 2);
p1 = poly!(1) + &p2;
}
let p3 = p1 + &poly!(0, 0, 2);
assert_eq!(poly!(2, 2, 2), p3);
let p4 = p3 + &poly!(3);
assert_eq!(poly!(5, 2, 2), p4);
}
#[test]
#[allow(clippy::eq_op)]
fn poly_sub() {
assert_eq!(poly!(-2., 0., 2.), poly!(1., 2., 3.) - poly!(3., 2., 1.));
assert_eq!(poly!(-2., 0., 3.), poly!(1., 2., 3.) - poly!(3., 2.));
assert_eq!(poly!(-2., 0., -1.), poly!(1., 2.) - poly!(3., 2., 1.));
assert_eq!(poly!(-2., 0., 6.), poly!(1., 2., 3.) - poly!(3., 2., -3.));
let p = poly!(1., 1.);
assert_eq!(Poly::zero(), &p - &p);
assert_eq!(poly!(-10., 1.), poly!(2., 1.) - 12.);
assert_eq!(poly!(-1., -1.), 1. - poly!(2., 1.));
assert_eq!(poly!(-1_i8, -1), 1_i8 - poly!(2, 1));
assert_eq!(poly!(-10, 1), poly!(2, 1) - 12);
}
#[test]
fn poly_sub_real_number() {
assert_eq!(poly!(-3, -4, -3), 1 - &poly!(4, 4, 3));
assert_eq!(poly!(4, 4, 3), &poly!(5, 4, 3) - 1);
}
#[test]
#[should_panic]
fn poly_sub_panic() {
let p = poly!(1, 2, 3) - 3_u32;
assert_eq!(p.coeffs, vec![]);
}
#[test]
#[allow(clippy::erasing_op)]
fn poly_mul() {
assert_eq!(
poly!(0., 0., -1., 0., -1.),
poly!(1., 0., 1.) * poly!(0., 0., -1.)
);
assert_eq!(Poly::zero(), poly!(1., 0., 1.) * Poly::zero());
assert_eq!(poly!(1., 0., 1.), poly!(1., 0., 1.) * Poly::one());
assert_eq!(poly!(-3., 0., -3.), poly!(1., 0., 1.) * poly!(-3.));
let p = poly!(-3., 0., -3.);
assert_eq!(poly!(9., 0., 18., 0., 9.), &p * &p);
assert_eq!(
poly!(-266.07_f32, 0., -266.07),
4.9 * poly!(1.0_f32, 0., 1.) * -54.3
);
assert_eq!(Poly::zero(), 0. * poly!(1., 0., 1.));
assert_eq!(Poly::zero(), poly!(1, 0, 1) * 0);
assert_eq!(Poly::zero(), &poly!(1, 0, 1) * 0);
assert_eq!(poly!(3, 0, 3), &poly!(1, 0, 1) * 3);
}
#[test]
#[allow(clippy::identity_op)]
fn poly_mul_real_number_value() {
assert_eq!(poly!(4, 4, 3), 1 * &poly!(4, 4, 3));
assert_eq!(poly!(10, 8, 6), &poly!(5, 4, 3) * 2);
}
#[test]
#[allow(clippy::op_ref)]
fn poly_mul_real_number_ref() {
assert_eq!(poly!(0), poly!(4, 4, 3) * &0);
assert_eq!(poly!(10, 8, 6), poly!(5, 4, 3) * &2);
let p = poly!(5, 4, 3);
assert_eq!(poly!(10, 8, 6), &p * &2);
}
#[test]
fn multiply_fft() {
let a = poly![1., 0., 3.];
let b = poly![1., 0., 3.];
let expected = &a * &b;
let actual = a.mul_fft(b);
assert_eq!(expected, actual);
}
#[test]
fn multiply_fft_one() {
let a = poly![1., 0., 3.];
let b = Poly::one();
let actual = a.clone().mul_fft(b);
assert_eq!(a, actual);
let c = Poly::one();
let d = poly![1., 0., 3.];
let actual = c.mul_fft(d.clone());
assert_eq!(d, actual);
}
#[test]
fn multiply_fft_zero() {
let a = poly![1., 0., 3.];
let b = Poly::zero();
let actual = a.mul_fft(b);
assert_eq!(Poly::zero(), actual);
}
#[test]
fn poly_div() {
assert_eq!(poly!(0.5, 0., 0.5), poly!(1., 0., 1.) / 2.0);
assert_eq!(poly!(4, 0, 5), poly!(8, 1, 11) / 2);
let inf = std::f32::INFINITY;
assert!((poly!(1., 0., 1.) / inf).is_zero());
assert_eq!(poly!(inf, -inf, inf), poly!(1., -2.3, 1.) / 0.);
}
#[allow(clippy::op_ref)]
#[test]
fn poly_div_ref() {
let p1 = poly!(21, 34, -98);
assert_eq!(poly!(10, 17, -49), &p1 / 2);
assert_eq!(poly!(10, 17, -49), &p1 / &2);
assert!((&p1 / &100).is_zero());
}
#[test]
fn poly_mutable_div() {
let mut p = poly!(3, 4, 5);
p.div_mut(&2);
assert_eq!(poly!(1, 2, 2), p);
}
#[test]
#[should_panic]
fn div_panic() {
let _res = poly_div_impl(poly!(6., 5., 1.), &poly!(0.));
}
#[test]
fn poly_division_impl() {
let d1 = poly_div_impl(poly!(6., 5., 1.), &poly!(2., 1.));
assert_eq!(poly!(3., 1.), d1.0);
assert_eq!(poly!(0.), d1.1);
let d2 = poly_div_impl(poly!(5., 3., 1.), &poly!(4., 6., 2.));
assert_eq!(poly!(0.5), d2.0);
assert_eq!(poly!(3.), d2.1);
let d3 = poly_div_impl(poly!(3., 1.), &poly!(4., 6., 2.));
assert_eq!(poly!(0.), d3.0);
assert_eq!(poly!(3., 1.), d3.1);
let d4 = poly_div_impl(poly!(0.), &poly!(4., 6., 2.));
assert_eq!(poly!(0.), d4.0);
assert_eq!(poly!(0.), d4.1);
let d5 = poly_div_impl(poly!(4., 6., 2.), &poly!(2.));
assert_eq!(poly!(2., 3., 1.), d5.0);
assert_eq!(poly!(0.), d5.1);
}
#[test]
fn two_poly_div() {
let q = poly!(-1., 0., 0., 0., 1.) / poly!(1., 0., 1.);
assert_eq!(poly!(-1., 0., 1.), q);
}
#[test]
fn two_poly_div_ref() {
let q = &poly!(-1., 0., 0., 0., 1.) / &poly!(1., 0., 1.);
assert_eq!(poly!(-1., 0., 1.), q);
}
#[test]
fn two_poly_rem() {
let r = poly!(-4., 0., -2., 1.) % poly!(-3., 1.);
assert_eq!(poly!(5.), r);
}
#[test]
fn two_poly_rem_ref() {
let r = &poly!(-4., 0., -2., 1.) % &poly!(-3., 1.);
assert_eq!(poly!(5.), r);
}
#[test]
fn poly_pow() {
let p = poly!(0, 0, 1);
let pow = p.powi(4);
assert_eq!(poly!(0, 0, 0, 0, 0, 0, 0, 0, 1), pow);
let p2 = poly!(1, 1);
let pow2 = p2.powi(5);
assert_eq!(poly!(1, 5, 10, 10, 5, 1), pow2);
}
}