76 lines
2.0 KiB
Python
76 lines
2.0 KiB
Python
import unittest
|
|
|
|
max_digit = 2**31 - 1
|
|
|
|
def lil_divmod(A, B):
|
|
'''
|
|
Return the greatest digit in 1..max_digit such that B * digit <= A
|
|
and the remainder A - B * digit.
|
|
'''
|
|
assert A > 0 and B > 0
|
|
assert A >= B
|
|
assert B * (max_digit + 1) > A
|
|
predicate = lambda n: B * n <= A
|
|
digit = find_greatest(1, max_digit, predicate)
|
|
remainder = A - digit * B
|
|
return digit, remainder
|
|
|
|
|
|
def find_greatest(low, high, f):
|
|
'''
|
|
Return the highest number n: low <= n <= high for which:
|
|
|
|
for all i in low..n f(i) is True
|
|
-and-
|
|
for all i in (n+1)..high f(i) is False.
|
|
|
|
If the function f::int->bool doesn't behave like above
|
|
then I don't know what this function will do.
|
|
|
|
There must be some number in the range or this function will
|
|
fail with an assertion error. (If you turn off assertions
|
|
it will succeed and return low in such a case.)
|
|
'''
|
|
assert low <= high
|
|
if f(high):
|
|
return high
|
|
pivot = (low + high) >> 1
|
|
# If there isn't a pivot between low and high that means there's only
|
|
# two numbers it could be: low or high, and we already know it isn't
|
|
# high from the test above so it must be low.
|
|
if low == pivot:
|
|
assert f(low) and not f(low + 1)
|
|
return low
|
|
assert low < pivot < high
|
|
return (
|
|
find_greatest(pivot, high - 1, f)
|
|
if f(pivot) else
|
|
find_greatest(low, pivot - 1, f)
|
|
)
|
|
|
|
|
|
class find_greatest_Test(unittest.TestCase):
|
|
|
|
def test_find_greatest(self):
|
|
k = 23300
|
|
a = 1
|
|
b = 2**31-1
|
|
f = lambda n: n <= k
|
|
n = find_greatest(a, b, f)
|
|
self.assertEqual(n, k)
|
|
|
|
|
|
class BigIntTest(unittest.TestCase):
|
|
|
|
def test_to_int(self):
|
|
a = 10*max_digit-3
|
|
b = 123
|
|
a = (max_digit-3) * b
|
|
digit, remainder = lil_divmod(a, b)
|
|
#print(f'divmod({a}, {b}) == ({digit}, {remainder}) # ? ')
|
|
self.assertEqual((digit, remainder), divmod(a, b))
|
|
|
|
|
|
if __name__ == '__main__':
|
|
unittest.main()
|