diff options
Diffstat (limited to 'src/lib.rs')
-rw-r--r-- | src/lib.rs | 124 |
1 files changed, 122 insertions, 2 deletions
@@ -1,3 +1,5 @@ +use std::cmp::Ordering; + pub type Number = f32; pub type Poly = Vec<Number>; @@ -29,13 +31,13 @@ pub fn lp(l: Box<Lerp>) -> Poly { Lerp::Node(a, b) => { let a = lp(a); let b = lp(b); - let c = poly_sub(&b, &a); + let c = sub(&b, &a); skewed_sum(a, c) } } } -fn poly_sub(a: &Poly, b: &Poly) -> Poly { +fn sub(a: &Poly, b: &Poly) -> Poly { let mut r = a.clone(); for i in 0..r.len() { r[i] -= b[i]; @@ -51,3 +53,121 @@ fn skewed_sum(a: Poly, b: Poly) -> Poly { 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]; + } + } + 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() + } else { + gcd(b, &c) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn poly_is_zero() { + let p = vec![0.0; 5]; + assert_eq!(is_zero(&p), true); + } + + #[test] + fn poly_is_not_zero() { + let mut p = vec![0.0; 5]; + p[2] = 8.0; + assert_eq!(is_zero(&p), false); + } + + #[test] + fn degree_is_five() { + let mut p = vec![0.0; 6]; + p[5] = 2.0; + assert_eq!(degree(&p), 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]); + } + + #[test] + fn rem_equal() { + let a = vec![6.0, 7.0, 1.0]; + let b = vec![-6.0, -5.0, 1.0]; + assert_eq!(rem(&a, &b), vec![12.0, 12.0, 0.0]); + } + + #[test] + fn rem_greater() { + let a = vec![-6.0, -5.0, 1.0]; + let b = vec![12.0, 12.0, 0.0]; + assert_eq!(rem(&a, &b), 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]); + } +} |