summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lerp.rs8
-rw-r--r--src/main.rs16
-rw-r--r--src/poly.rs203
3 files changed, 78 insertions, 149 deletions
diff --git a/src/lerp.rs b/src/lerp.rs
index 8a33e8f..96506df 100644
--- a/src/lerp.rs
+++ b/src/lerp.rs
@@ -1,5 +1,5 @@
use crate::number::Number;
-use crate::poly::{self, Poly};
+use crate::poly::Poly;
pub enum Lerp {
Node(Box<Lerp>, Box<Lerp>),
@@ -23,12 +23,12 @@ impl Lerp {
pub fn lp(l: Box<Lerp>) -> Poly {
match *l {
- Lerp::Leaf(a, b) => vec![a, b - a],
+ Lerp::Leaf(a, b) => Poly(vec![a, b - a]),
Lerp::Node(a, b) => {
let a = lp(a);
let b = lp(b);
- let c = poly::sub(&b, &a);
- poly::skewed_sum(a, c)
+ let c = &b - &a;
+ &a + &(&c * &Poly(vec![0.0, 1.0]))
}
}
}
diff --git a/src/main.rs b/src/main.rs
index e5e4112..bd7e1a2 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -14,12 +14,10 @@ use sdl2::keyboard::Keycode;
use sdl2::rect::Rect;
fn main() {
- //let a = Lerp::new(vec![2.0, -2.0, 2.0]);
- //let b = Lerp::new(vec![-1.0, 1.0, 2.0]);
- //let pa = lerp::lp(a);
- //let pb = lerp::lp(b);
- let pa = vec![1.0, 5.0, -2.0];
- let pb = vec![5.0, -4.0, 0.0];
+ let a = Lerp::new(vec![2.0, -2.0, 2.0]);
+ let b = Lerp::new(vec![-1.0, 1.0, 2.0]);
+ let pa = lerp::lp(a);
+ let pb = lerp::lp(b);
let p = poly::gcd(&pa, &pb);
let sdl_context = sdl2::init().unwrap();
@@ -49,9 +47,9 @@ fn main() {
let s = -600.0 / 10.0;
let k = 600.0 / 2.0;
for t in -800..800 {
- let x = k + s * poly::eval_poly(&pa, t as Number / 100.0);
- let y = k + s * poly::eval_poly(&pb, t as Number / 100.0);
- let z = k + s * poly::eval_poly(&p, t as Number / 100.0);
+ let x = k + s * pa.eval(t as Number / 100.0);
+ let y = k + s * pb.eval(t as Number / 100.0);
+ let z = k + s * p.eval(t as Number / 100.0);
canvas.set_draw_color(Color::RGB(180, 20, 20));
canvas.fill_rect(Rect::new(400 + t, x as i32, 5, 5)).unwrap();
canvas.set_draw_color(Color::RGB(20, 180, 20));
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(&degree(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]));
}
}