Добавлена неполная реализация деления

1 files changed, 78 insertions, 1 deletions

diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs
index b9816a3..f305089 100644
--- a/sem2/src/mpn.rs
+++ b/sem2/src/mpn.rs
@@ -1,6 +1,6 @@
 use std::cmp::max;
 use std::fmt;
-use std::ops::{Add, Mul, Sub};
+use std::ops::{Add, Div, Mul, Sub};
 
 pub struct Number {
     radix: usize,
@@ -174,3 +174,80 @@ impl Mul for Number {
         .fix_leading_zeros();
     }
 }
+
+impl Div for Number {
+    type Output = Self;
+
+    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;
+            for i in 0..a.len() {
+                let dig = a[i] * b;
+                c[i] = dig % radix + carry;
+                carry = dig / radix;
+            }
+            *c.last_mut().unwrap() = carry;
+            return c;
+        }
+
+        let n = other.len();
+        let m = self.len() - n;
+        let b = self.radix as u8;
+
+        let v1 = other.digits[other.len() - 1];
+        let d = self.radix as u8 / (v1 + 1);
+
+        let mut u = mul_digit(&self.digits, d, self.radix as u8);
+        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 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 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,
+                digits: Vec::from(u_sub),
+            }
+            .fix_leading_zeros();
+            let qv = Number {
+                radix: other.radix,
+                digits: mul_digit(&v, q, 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 };
+            }
+        }
+
+        // println!("{:?}", quo);
+        quo.reverse();
+        return Number {
+            radix: self.radix,
+            digits: quo,
+        }
+        .fix_leading_zeros();
+    }
+}