From 791688565eb840954b64416fa4fde17c341522bc Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Sat, 18 Mar 2023 12:19:07 +0400
Subject: =?UTF-8?q?=D0=98=D1=81=D0=BF=D1=80=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD?=
 =?UTF-8?q?=D0=B0=20=D0=BE=D1=88=D0=B8=D0=B1=D0=BA=D0=B0=20=D0=BF=D1=80?=
 =?UTF-8?q?=D0=B8=20=D0=B4=D0=B5=D0=BB=D0=B5=D0=BD=D0=B8=D0=B8?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 sem2/src/mpn.rs | 40 ++++++++++++++++++++++++++++------------
 1 file changed, 28 insertions(+), 12 deletions(-)

diff --git a/sem2/src/mpn.rs b/sem2/src/mpn.rs
index 742e485..97ba55d 100644
--- a/sem2/src/mpn.rs
+++ b/sem2/src/mpn.rs
@@ -1,7 +1,8 @@
 use std::cmp::{max, Ordering};
 use std::fmt;
-use std::ops::{Add, Div, Mul, Rem, Sub};
+use std::ops::{Add, Div, Index, IndexMut, Mul, Rem, Sub};
 
+#[derive(Debug)]
 pub struct Number {
     radix: u8,
     digits: Vec<u8>,
@@ -16,6 +17,20 @@ impl Clone for Number {
     }
 }
 
+impl Index<usize> for Number {
+    type Output = u8;
+
+    fn index(&self, idx: usize) -> &Self::Output {
+        &self.digits[idx]
+    }
+}
+
+impl IndexMut<usize> for Number {
+    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
+        &mut self.digits[idx]
+    }
+}
+
 impl Number {
     pub fn parse(snum: &str, radix: u8) -> Result<Number, String> {
         let snum = snum.as_bytes();
@@ -259,6 +274,7 @@ impl Number {
             tmp.pop();
             tmp
         };
+        let v_number = Number::from_digits(&v, self.radix).unwrap();
 
         let mut quo = Vec::new();
         for j in (0..=m).rev() {
@@ -270,11 +286,11 @@ impl Number {
                 let uj1 = u[j + n - 1] as i32;
                 let uj2 = u[j + n - 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;
+                let mut qhat = (uj * b + uj1) / v1;
+                while v2 * qhat > (uj * b + uj1 - qhat * v1) * b + uj2 {
+                    qhat -= 1;
                 }
-                qc
+                qhat
             };
 
             let u_sub = Vec::from(&u[j..=j + n]);
@@ -285,15 +301,15 @@ impl Number {
             )
             .unwrap();
 
-            if u_sub >= qv {
-                let p = u_sub - qv;
-                for i in 0..n + 1 {
-                    u[j + i] = if i < p.len() { p.digits[i] } else { 0 };
-                }
-                quo.push(q as u8);
+            let (p, q) = if u_sub >= qv {
+                (u_sub - qv, q as u8)
             } else {
-                quo.push((q - 1) as u8);
+                (u_sub + v_number.clone() - qv, (q - 1) as u8)
+            };
+            for i in 0..n + 1 {
+                u[j + i] = if i < p.len() { p.digits[i] } else { 0 };
             }
+            quo.push(q);
         }
 
         quo.reverse();
-- 
cgit v1.2.3