diff options
Diffstat (limited to 'src/poly.rs')
| -rw-r--r-- | src/poly.rs | 203 |
1 files changed, 67 insertions, 136 deletions
diff --git a/src/poly.rs b/src/poly.rs index f6ee63c..9c95796 100644 --- a/src/poly.rs +++ b/src/poly.rs @@ -5,12 +5,12 @@ use iter::Iter; use std::cmp; use std::cmp::Ordering; use std::ops::{Add, Sub, Mul, Rem}; -use std::iter::{Sum, Zip, Take}; +use std::iter::{Zip, Take}; #[derive(PartialEq, Debug)] -pub struct P(Vec<Number>); +pub struct Poly(pub Vec<Number>); -impl P { +impl Poly { fn degree(&self) -> usize { let mut i = self.0.len() - 1; while self.0[i] == 0.0 && i > 0 { @@ -29,28 +29,45 @@ impl P { let b = other.iter().take(deg); a.zip(b) } + + 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); + } + r + } + + fn is_zero(&self) -> bool { + for i in 0..self.0.len() { + if self.0[i] != 0.0 { + return false + } + } + true + } } -impl Add for &P { - type Output = P; +impl Add for &Poly { + type Output = Poly; - fn add(self, other: Self) -> P { - P(self.zip(other).map(|(x, y)| {x + y}).collect()) + fn add(self, other: Self) -> Poly { + Poly(self.zip(other).map(|(x, y)| {x + y}).collect()) } } -impl Sub for &P { - type Output = P; +impl Sub for &Poly { + type Output = Poly; - fn sub(self, other: Self) -> P { - P(self.zip(other).map(|(x, y)| {x - y}).collect()) + fn sub(self, other: Self) -> Poly { + Poly(self.zip(other).map(|(x, y)| {x - y}).collect()) } } -impl Mul for &P { - type Output = P; +impl Mul for &Poly { + type Output = Poly; - fn mul(self, other: Self) -> P { + fn mul(self, other: Self) -> Poly { let mut r = Vec::new(); for i in 0..other.degree() + 1 { let mut prefix = vec![0.0; i]; @@ -59,110 +76,36 @@ impl Mul for &P { .map(|x| {x * other.0[i]}) .collect(); prefix.append(&mut suffix); - r.push(P(prefix)); + r.push(Poly(prefix)); } - r.iter().fold(P(vec![0.0]), |acc, x| &acc + x) + r.iter().fold(Poly(vec![0.0]), |acc, x| &acc + x) } } -impl Rem for &P { - type Output = P; +impl Rem for &Poly { + type Output = Poly; - fn rem(self, other: Self) -> P { + fn rem(self, other: Self) -> Poly { let ad = self.degree(); let bd = other.degree(); let an = self.0[ad]; let bn = other.0[bd]; match ad.cmp(&bd) { - Ordering::Equal => self - &(other * &P(vec![an / bn])), + Ordering::Equal => self - &(other * &Poly(vec![an / bn])), Ordering::Greater => { - let mut qv = vec![0.0; ad]; + let mut qv = vec![0.0; ad + 1]; qv[ad - bd] = an / bn; - self - &(other * &P(qv)) + self - &(other * &Poly(qv)) }, - Ordering::Less => P(vec![0.0]) - } - } -} - -//****************************REFACTORING************************************ - -pub type Poly = Vec<Number>; - -pub fn eval_poly(p: &Poly, t: Number) -> Number { - let mut r = 0.0; - for i in 0..p.len() { - r += p[i] * t.powi(i as i32); - } - r -} - -pub fn sub(a: &Poly, b: &Poly) -> Poly { - let mut r = a.clone(); - for i in 0..r.len() { - r[i] -= b[i]; - } - r -} - -pub fn skewed_sum(a: Poly, b: Poly) -> Poly { - let mut r = a.clone(); - for i in 0..r.len() - 1 { - r[i + 1] += b[i]; - } - r.push(b[b.len() - 1]); - r -} - -fn is_zero(p: &Poly) -> bool { - for i in 0..p.len() { - if p[i] != 0.0 { - return false - } - } - true -} - -fn degree(p: &Poly) -> usize { - let mut i = p.len() - 1; - while p[i] == 0.0 && i > 0 { - i -= 1; - } - i -} - -fn prod(p: &Poly, n: Number) -> Poly { - let mut r = p.clone(); - for i in 0..r.len() { - r[i] *= n; - } - r -} - -fn shift(p: &Poly, amount: usize) -> Poly { - let mut r = vec![0.0; p.len()]; - for i in 0..p.len() { - if i + amount < r.len() { - r[i + amount] = p[i]; + Ordering::Less => Poly(vec![0.0]) } } - r -} - -fn rem(a: &Poly, b: &Poly) -> Poly { - let an = a[degree(a)]; - let bn = b[degree(b)]; - match degree(a).cmp(°ree(b)) { - Ordering::Equal => sub(a, &prod(b, an / bn)), - Ordering::Greater => sub(a, &prod(&shift(b, (degree(a) - degree(b)) as usize), an / bn)), - Ordering::Less => vec![0.0; b.len()] - } } pub fn gcd(a: &Poly, b: &Poly) -> Poly { - let c = rem(a, b); - if is_zero(&c) { - b.clone() + let c = a % b; + if c.is_zero() { + Poly(b.0.clone()) } else { gcd(b, &c) } @@ -174,81 +117,69 @@ mod tests { #[test] fn mul_test() { - let a = P(vec![1.0, 2.0, 3.0]); - let b = P(vec![1.0, 2.0]); - assert_eq!(&a * &b, P(vec![1.0, 4.0, 7.0, 6.0])); + 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])); } #[test] fn add_test() { - let a = P(vec![1.0]); - let b = P(vec![0.0, 0.0, 0.0, 1.0]); - assert_eq!(&a + &b, P(vec![1.0, 0.0, 0.0, 1.0])); + 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])); } #[test] fn sub_test() { - let a = P(vec![1.0, 2.0, 3.0]); - let b = P(vec![1.0]); - assert_eq!(&a - &b, P(vec![0.0, 2.0, 3.0])); + 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])); } #[test] fn poly_is_zero() { - let p = vec![0.0; 5]; - assert_eq!(is_zero(&p), true); + let p = Poly(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!(is_zero(&p), false); + assert_eq!(Poly(p).is_zero(), false); } #[test] fn degree_is_five() { let mut p = vec![0.0; 6]; p[5] = 2.0; - assert_eq!(degree(&p), 5); + assert_eq!(Poly(p).degree(), 5); } #[test] fn degree_is_zero() { - let p = vec![0.0; 6]; - assert_eq!(degree(&p), 0); - } - - #[test] - fn prod_test() { - let p = vec![1.0, 2.0, 3.0, 4.0, 5.0]; - assert_eq!(prod(&p, 2.0), vec![2.0, 4.0, 6.0, 8.0, 10.0]); - } - - #[test] - fn shift_test() { - let p = vec![1.0, 2.0, 3.0, 0.0, 0.0]; - assert_eq!(shift(&p, 2), vec![0.0, 0.0, 1.0, 2.0, 3.0]); + let p = Poly(vec![0.0; 6]); + assert_eq!(p.degree(), 0); } #[test] fn rem_equal() { - let a = P(vec![6.0, 7.0, 1.0]); - let b = P(vec![-6.0, -5.0, 1.0]); - assert_eq!(&a % &b, P(vec![12.0, 12.0, 0.0])); + 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![12.0, 12.0, 0.0])); } #[test] fn rem_greater() { - let a = P(vec![-6.0, -5.0, 1.0]); - let b = P(vec![12.0, 12.0, 0.0]); - assert_eq!(&a % &b, P(vec![-6.0, -6.0, 0.0])); + let a = Poly(vec![-6.0, -5.0, 1.0]); + let b = Poly(vec![12.0, 12.0]); + assert_eq!(&a % &b, Poly(vec![-6.0, -6.0, 0.0])); } #[test] fn gcd_test() { - let a = vec![6.0, 7.0, 1.0]; - let b = vec![-6.0, -5.0, 1.0]; - assert_eq!(gcd(&a, &b), vec![-6.0, -6.0, 0.0]); + let a = Poly(vec![6.0, 7.0, 1.0]); + let b = Poly(vec![-6.0, -5.0, 1.0]); + assert_eq!(gcd(&a, &b), Poly(vec![-6.0, -6.0, 0.0])); } } |