From d8b346958a37451643e5e67ef7f34844ea9f2f6c Mon Sep 17 00:00:00 2001
From: Simon Forman <sforman@hushmail.com>
Date: Thu, 6 Oct 2022 08:04:54 -0700
Subject: [PATCH] Finish lil_divmod.

---
 bigjoyints/divmod.py     |  2 +-
 bigjoyints/lil_divmod.py | 37 +++++++++++++++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 1 deletion(-)
 create mode 100644 bigjoyints/lil_divmod.py

diff --git a/bigjoyints/divmod.py b/bigjoyints/divmod.py
index 25aa937..69cb4a9 100755
--- a/bigjoyints/divmod.py
+++ b/bigjoyints/divmod.py
@@ -224,6 +224,6 @@ def try_it(a, b):
 
 for _ in range(10**6):
     try_it(
-        randint(0, 10**randint(3, 15)),
+        randint(0, 10**randint(8, 15)),
         randint(1, 10**randint(1, 15))
         )
diff --git a/bigjoyints/lil_divmod.py b/bigjoyints/lil_divmod.py
new file mode 100644
index 0000000..f252d13
--- /dev/null
+++ b/bigjoyints/lil_divmod.py
@@ -0,0 +1,37 @@
+import  unittest
+
+
+def lil_divmod(A, B):
+    assert A >= B
+    assert A and B
+    # There is a greatest digit in 1..9 such that:
+    # B * digit <= A
+    # The obvious thing to do here is a bisect search,
+    # if we were really just doing 1..9 we could go linear.
+    # Maybe drive it by the bits in digit?
+    digit = 9
+    Q = digit * B
+    while Q > A:
+        digit = digit - 1
+        if not digit:
+            raise ValueError('huh?')
+        Q = digit * B
+    assert A >= Q
+    remainder = A - Q
+    assert remainder < B
+    return digit, remainder
+
+
+class BigIntTest(unittest.TestCase):
+
+    def test_to_int(self):
+        a = 123
+        b = 45
+        digit, remainder = lil_divmod(a, b)
+        self.assertLessEqual(b * digit, a)
+        self.assertGreater(b * (digit + 1), a)
+        self.assertEqual(b * digit + remainder, a)
+
+
+if __name__ == '__main__':
+    unittest.main()
-- 
2.11.0