From f954fb5741d6ee0115a118ed81c3fcaee03d6fbc Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Fri, 17 Mar 2023 01:56:44 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?=
 =?UTF-8?q?=20=D0=BD=D0=B5=D0=BF=D0=BE=D0=BB=D0=BD=D0=B0=D1=8F=20=D1=80?=
 =?UTF-8?q?=D0=B5=D0=B0=D0=BB=D0=B8=D0=B7=D0=B0=D1=86=D0=B8=D1=8F=20=D0=B4?=
 =?UTF-8?q?=D0=B5=D0=BB=D0=B5=D0=BD=D0=B8=D1=8F?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 sem2/src/main.rs |  2 +-
 sem2/src/mpn.rs  | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 79 insertions(+), 2 deletions(-)

(limited to 'sem2')

diff --git a/sem2/src/main.rs b/sem2/src/main.rs
index 658bf51..2fea2b1 100644
--- a/sem2/src/main.rs
+++ b/sem2/src/main.rs
@@ -63,7 +63,7 @@ fn main() {
     };
 
     let mpn_mul_start = Instant::now();
-    let mpn_mul = a * b;
+    let mpn_mul = a / b;
     let mpn_mul_elapsed = mpn_mul_start.elapsed();
 
     let rug_mul_start = Instant::now();
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();
+    }
+}
-- 
cgit v1.2.3