Добавлена операция деления, исправлена ошибка при сравнении чисел.

1 files changed, 90 insertions, 29 deletions

diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs
index cd8ecdf..caccc33 100644
--- a/sem2/src/mpn.rs
+++ b/sem2/src/mpn.rs
@@ -1,6 +1,6 @@
 use std::cmp::{max, Ordering};
 use std::fmt;
-use std::ops::{Add, Div, Mul, Sub};
+use std::ops::{Add, Div, Mul, Rem, Sub};
 
 pub struct Number {
     radix: usize,
@@ -184,25 +184,61 @@ impl Mul for Number {
     }
 }
 
-impl Div for Number {
-    type Output = Self;
+impl Number {
+    pub fn div_rem(self, other: Self) -> (Self, Self) {
+        if self < other {
+            return (
+                Number {
+                    radix: self.radix,
+                    digits: vec![0],
+                },
+                self,
+            );
+        }
+
+        fn div_digit(a: &Vec<u8>, b: u8, radix: u8) -> (Vec<u8>, u8) {
+            let mut q = Vec::new();
+            let mut rem = 0;
+            for j in (0..a.len()).rev() {
+                let d = rem as i32 * radix as i32 + a[j] as i32;
+                q.push((d / b as i32) as u8);
+                rem = (d % b as i32) as u8;
+            }
+            q.reverse();
+            return (q, rem);
+        }
+
+        if other.len() == 1 {
+            let (div, rem) = div_digit(&self.digits, other.digits[0], self.radix as u8);
+            return (
+                Number {
+                    radix: self.radix,
+                    digits: div,
+                }
+                .fix_leading_zeros(),
+                Number {
+                    radix: self.radix,
+                    digits: vec![rem],
+                }
+                .fix_leading_zeros(),
+            );
+        }
 
-    fn div(self, other: Self) -> Self::Output {
         fn mul_digit(a: &Vec<u8>, b: u8, radix: u8) -> Vec<u8> {
             let mut c = vec![0; a.len() + 1];
-            let mut carry = 0;
+            let mut carry = 0 as i32;
             for i in 0..a.len() {
-                let dig = a[i] * b;
-                c[i] = dig % radix + carry;
-                carry = dig / radix;
+                let dig = (a[i] as i32 * b as i32) as i32 + carry;
+                c[i] = (dig % radix as i32) as u8;
+                carry = dig / radix as i32;
             }
-            *c.last_mut().unwrap() = carry;
+            *c.last_mut().unwrap() = carry as u8;
             return c;
         }
 
         let n = other.len();
         let m = self.len() - n;
-        let b = self.radix as u8;
+        let b = self.radix as i32;
 
         let v1 = other.digits[other.len() - 1];
         let d = self.radix as u8 / (v1 + 1);
@@ -211,28 +247,22 @@ impl Div for Number {
         let mut v = mul_digit(&other.digits, d, self.radix as u8);
         v.pop();
 
-        // println!("{d} {u:?} {v:?}");
-
         let mut quo = Vec::new();
         for j in 0..=m {
-            // println!("{:?}", u);
-            let uj = u[u.len() - 1 - j];
-            let v1 = v[v.len() - 1];
+            let uj = u[u.len() - 1 - j] as i32;
+            let v1 = v[v.len() - 1] as i32;
             let q = if uj == v1 {
                 b - 1
             } else {
-                let uj1 = u[u.len() - 1 - (j + 1)];
-                let uj2 = u[u.len() - 1 - (j + 2)];
-                let v2 = v[v.len() - 2];
+                let uj1 = u[u.len() - 1 - (j + 1)] as i32;
+                let uj2 = u[u.len() - 1 - (j + 2)] as i32;
+                let v2 = v[v.len() - 2] as i32;
                 let mut qc = (uj * b + uj1) / v1;
                 while v2 * qc > (uj * b + uj1 - qc * v1) * b + uj2 {
                     qc -= 1;
                 }
                 qc
             };
-            // println!("{uj} {v1}");
-            // println!("{q}");
-            quo.push(q);
             let u_sub = &u[u.len() - 1 - (j + n)..=u.len() - 1 - j];
             let u_sub = Number {
                 radix: self.radix,
@@ -241,23 +271,54 @@ impl Div for Number {
             .fix_leading_zeros();
             let qv = Number {
                 radix: other.radix,
-                digits: mul_digit(&v, q, other.radix as u8),
+                digits: mul_digit(&v, q as u8, other.radix as u8),
             }
             .fix_leading_zeros();
-            let p = u_sub - qv;
-            for i in 0..n + 1 {
-                let idx = u.len() - 1 - (j + n - i);
-                u[idx] = if i < p.len() { p.digits[i] } else { 0 };
+            if u_sub >= qv {
+                let p = u_sub - qv;
+                for i in 0..n + 1 {
+                    let idx = u.len() - 1 - (j + n - i);
+                    u[idx] = if i < p.len() { p.digits[i] } else { 0 };
+                }
+                quo.push(q as u8);
+            } else {
+                quo.push((q - 1) as u8);
             }
         }
 
-        // println!("{:?}", quo);
         quo.reverse();
-        return Number {
+        let div = Number {
             radix: self.radix,
             digits: quo,
         }
         .fix_leading_zeros();
+
+        let (rem_digits, _) = div_digit(&u, d, self.radix as u8);
+        let rem = Number {
+            radix: self.radix,
+            digits: rem_digits,
+        }
+        .fix_leading_zeros();
+
+        return (div, rem);
+    }
+}
+
+impl Div for Number {
+    type Output = Self;
+
+    fn div(self, other: Self) -> Self::Output {
+        let (div, _) = self.div_rem(other);
+        return div;
+    }
+}
+
+impl Rem for Number {
+    type Output = Self;
+
+    fn rem(self, other: Self) -> Self::Output {
+        let (_, rem) = self.div_rem(other);
+        return rem;
     }
 }
 
@@ -299,7 +360,7 @@ impl Ord for Number {
             return Ordering::Greater;
         }
 
-        for i in 0..self.len() {
+        for i in (0..self.len()).rev() {
             let l = self.digits[i];
             let r = other.digits[i];
             if l != r {