From ed7f00f4d3833877c1e3336ba2bb85d7e3733112 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Juan=20Manuel=20Tom=C3=A1s?= Date: Thu, 14 Jan 2021 07:02:19 -0300 Subject: Calculate poly degree on new --- src/poly.rs | 109 ++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 59 insertions(+), 50 deletions(-) (limited to 'src/poly.rs') diff --git a/src/poly.rs b/src/poly.rs index 60eb707..90b7b78 100644 --- a/src/poly.rs +++ b/src/poly.rs @@ -5,42 +5,53 @@ use iter::Iter; use std::ops::{Add, Sub, Mul, Div}; #[derive(PartialEq, Debug, Clone)] -pub struct Poly(pub Vec); +pub struct Poly { + data: Vec, + degree: usize +} impl Poly { + pub fn new(data: Vec) -> Poly { + let mut i = data.len() - 1; + while data[i] == 0.0 && i > 0 { + i -= 1; + } + Poly { data, degree : i } + } + fn mono(degree: usize, coefficient: Number) -> Poly { - let mut p = vec![0.0; degree + 1]; - p[degree] = coefficient; - Poly(p) + if coefficient != 0.0 { + let mut p = vec![0.0; degree + 1]; + p[degree] = coefficient; + Poly::new(p) + } else { + Poly::new(vec![0.0]) + } } fn degree(&self) -> usize { - let mut i = self.0.len() - 1; - while self.0[i] == 0.0 && i > 0 { - i -= 1; - } - i + self.degree } fn lc(&self) -> Number { - self.0[self.degree()] + self.data[self.degree()] } fn iter(&self) -> Iter { - Iter::new(self.0.clone(), self.degree()) + Iter::new(self.data.clone(), self.degree()) } pub fn eval(&self, n: Number) -> Number { let mut r = 0.0; - for i in 0..self.0.len() { - r += self.0[i] * n.powi(i as i32); + for i in 0..self.data.len() { + r += self.data[i] * n.powi(i as i32); } r } fn is_zero(&self) -> bool { - for i in 0..self.0.len() { - if self.0[i] != 0.0 { + for i in 0..self.data.len() { + if self.data[i] != 0.0 { return false } } @@ -52,7 +63,7 @@ impl Add for &Poly { type Output = Poly; fn add(self, other: Self) -> Poly { - Poly(self.iter().zip(other.iter()).map(|(x, y)| {x + y}).collect()) + Poly::new(self.iter().zip(other.iter()).map(|(x, y)| {x + y}).collect()) } } @@ -60,7 +71,7 @@ impl Sub for &Poly { type Output = Poly; fn sub(self, other: Self) -> Poly { - Poly(self.iter().zip(other.iter()).map(|(x, y)| {x - y}).collect()) + Poly::new(self.iter().zip(other.iter()).map(|(x, y)| {x - y}).collect()) } } @@ -73,12 +84,12 @@ impl Mul for &Poly { let mut prefix = vec![0.0; i]; let mut suffix: Vec = self.iter() .take(self.degree() + 1) - .map(|x| {x * other.0[i]}) + .map(|x| {x * other.data[i]}) .collect(); prefix.append(&mut suffix); - r.push(Poly(prefix)); + r.push(Poly::new(prefix)); } - r.iter().fold(Poly(vec![0.0]), |acc, x| &acc + x) + r.iter().fold(Poly::new(vec![0.0]), |acc, x| &acc + x) } } @@ -86,7 +97,7 @@ impl Div for &Poly { type Output = (Poly, Poly); fn div(self, divisor: Self) -> (Poly, Poly) { - let mut q = Poly(vec![0.0]); + let mut q = Poly::new(vec![0.0]); let mut r = self.clone(); while !r.is_zero() && r.degree() >= divisor.degree() { let s = Poly::mono(r.degree() - divisor.degree(), r.lc() / divisor.lc()); @@ -112,76 +123,74 @@ mod tests { #[test] fn div_equal() { - let a = Poly(vec![6.0, 7.0, 1.0]); - let b = Poly(vec![-6.0, -5.0, 1.0]); - assert_eq!(&a / &b, (Poly(vec![1.0]), Poly(vec![12.0, 12.0, 0.0]))); + let a = Poly::new(vec![6.0, 7.0, 1.0]); + let b = Poly::new(vec![-6.0, -5.0, 1.0]); + assert_eq!(&a / &b, (Poly::new(vec![1.0]), Poly::new(vec![12.0, 12.0, 0.0]))); } #[test] fn div_greater() { - let a = Poly(vec![-6.0, -5.0, 1.0]); - let b = Poly(vec![12.0, 12.0]); - assert_eq!(&a / &b, (Poly(vec![-0.5, 1.0/12.0]), Poly(vec![0.0, 0.0]))); + let a = Poly::new(vec![-6.0, -5.0, 1.0]); + let b = Poly::new(vec![12.0, 12.0]); + assert_eq!(&a / &b, (Poly::new(vec![-0.5, 1.0/12.0]), Poly::new(vec![0.0, 0.0]))); } #[test] fn div_less() { - let a = Poly(vec![12.0, 12.0]); - let b = Poly(vec![-6.0, -5.0, 1.0]); - assert_eq!(&a / &b, (Poly(vec![0.0]), a)); + let a = Poly::new(vec![12.0, 12.0]); + let b = Poly::new(vec![-6.0, -5.0, 1.0]); + assert_eq!(&a / &b, (Poly::new(vec![0.0]), a)); } #[test] fn mul_test() { - let a = Poly(vec![1.0, 2.0, 3.0]); - let b = Poly(vec![1.0, 2.0]); - assert_eq!(&a * &b, Poly(vec![1.0, 4.0, 7.0, 6.0])); + let a = Poly::new(vec![1.0, 2.0, 3.0]); + let b = Poly::new(vec![1.0, 2.0]); + assert_eq!(&a * &b, Poly::new(vec![1.0, 4.0, 7.0, 6.0])); } #[test] fn add_test() { - let a = Poly(vec![1.0]); - let b = Poly(vec![0.0, 0.0, 0.0, 1.0]); - assert_eq!(&a + &b, Poly(vec![1.0, 0.0, 0.0, 1.0])); + let a = Poly::new(vec![1.0]); + let b = Poly::new(vec![0.0, 0.0, 0.0, 1.0]); + assert_eq!(&a + &b, Poly::new(vec![1.0, 0.0, 0.0, 1.0])); } #[test] fn sub_test() { - let a = Poly(vec![1.0, 2.0, 3.0]); - let b = Poly(vec![1.0, 1.0, 1.0]); - assert_eq!(&a - &b, Poly(vec![0.0, 1.0, 2.0])); + let a = Poly::new(vec![1.0, 2.0, 3.0]); + let b = Poly::new(vec![1.0, 1.0, 1.0]); + assert_eq!(&a - &b, Poly::new(vec![0.0, 1.0, 2.0])); } #[test] fn poly_is_zero() { - let p = Poly(vec![0.0; 5]); + let p = Poly::new(vec![0.0; 5]); assert_eq!(p.is_zero(), true); } #[test] fn poly_is_not_zero() { - let mut p = vec![0.0; 5]; - p[2] = 8.0; - assert_eq!(Poly(p).is_zero(), false); + let p = Poly::mono(5, 8.0); + assert_eq!(p.is_zero(), false); } #[test] fn degree_is_five() { - let mut p = vec![0.0; 6]; - p[5] = 2.0; - assert_eq!(Poly(p).degree(), 5); + let p = Poly::mono(5, 2.0); + assert_eq!(p.degree(), 5); } #[test] fn degree_is_zero() { - let p = Poly(vec![0.0; 6]); + let p = Poly::new(vec![0.0; 6]); assert_eq!(p.degree(), 0); } #[test] fn gcd_test() { - let a = Poly(vec![2.0, -8.0, 8.0]); - let b = Poly(vec![-1.0, 4.0, -1.0]); - assert_eq!(gcd(&a, &b), Poly(vec![-0.0625, 0.0])); + let a = Poly::new(vec![2.0, -8.0, 8.0]); + let b = Poly::new(vec![-1.0, 4.0, -1.0]); + assert_eq!(gcd(&a, &b), Poly::new(vec![-0.0625, 0.0])); } } -- cgit v1.2.3