From 9e2e1387375658c3052138c238eb2afcd0b63a1f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Juan=20Manuel=20Tom=C3=A1s?= <jtomas1815@gmail.com>
Date: Tue, 12 Jan 2021 01:28:57 -0300
Subject: Make div return quotient and remainder

---
 src/poly.rs | 67 ++++++++++++++++++++++---------------------------------------
 1 file changed, 24 insertions(+), 43 deletions(-)

diff --git a/src/poly.rs b/src/poly.rs
index 488b0ea..6ffaf7d 100644
--- a/src/poly.rs
+++ b/src/poly.rs
@@ -2,8 +2,7 @@ mod iter;
 
 use crate::number::Number;
 use iter::Iter;
-use std::cmp::Ordering;
-use std::ops::{Add, Sub, Mul, Div, Rem};
+use std::ops::{Add, Sub, Mul, Div};
 
 #[derive(PartialEq, Debug, Clone)]
 pub struct Poly(pub Vec<Number>);
@@ -73,29 +72,10 @@ impl Mul for &Poly {
     }
 }
 
-impl Rem for &Poly {
-    type Output = Poly;
-
-    fn rem(self, other: Self) -> Poly {
-        let mut q = Poly(vec![0.0]);
-        let mut r = self.clone();
-        let d = other.degree();
-        let c = other.0[d];
-        while r.degree() >= d {
-            let mut p = vec![0.0; r.degree() - d + 1];
-            p[r.degree() - d] = r.0[r.degree()] / c;
-            let s = Poly(p);
-            q = &q + &s;
-            r = &r - &(&s * other);
-        }
-        r
-    }
-}
-
 impl Div for &Poly {
-    type Output = Poly;
+    type Output = (Poly, Poly);
 
-    fn div(self, other: Self) -> Poly {
+    fn div(self, other: Self) -> (Poly, Poly) {
         let mut q = Poly(vec![0.0]);
         let mut r = self.clone();
         let d = other.degree();
@@ -107,12 +87,13 @@ impl Div for &Poly {
             q = &q + &s;
             r = &r - &(&s * other);
         }
-        q
+        (q, r)
     }
 }
 
 pub fn gcd(a: &Poly, b: &Poly) -> Poly {
-    let c = a % b;
+    let (_, c) = a / b;
+    println!("a: {:?}, b: {:?}, c: {:?}", a, b, c);
     if c.is_zero() {
         b.clone()
     } else {
@@ -125,10 +106,24 @@ mod tests {
     use super::*;
 
     #[test]
-    fn div_test() {
-        let a = Poly(vec![1.0, 4.0, 7.0, 6.0]);
-        let b = Poly(vec![1.0, 2.0, 3.0]);
-        assert_eq!(&a / &b, Poly(vec![1.0, 2.0]));
+    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])));
+    }
+
+    #[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])));
+    }
+
+    #[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));
     }
 
     #[test]
@@ -178,20 +173,6 @@ mod tests {
         assert_eq!(p.degree(), 0);
     }
 
-    #[test]
-    fn rem_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![12.0, 12.0, 0.0]));
-    }
-
-    #[test]
-    fn rem_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.0, 0.0]));
-    }
-
     #[test]
     fn gcd_test() {
         let a = Poly(vec![6.0, 7.0, 1.0]);
-- 
cgit v1.2.3