a021: 大數運算-2
我們都知道電腦擅長於各種數字的計算，可是，我們又知道各種程式語言的變數又都有上限，比如整數只有216 或 232 個。如果要計算更大的數字時又該如何計算呢? 就交給聰明的您來解決囉。
以 + 代表加法
以 - 代表減法
以 * 代表乘法
以 / 代表除法 (取商數)
輸入說明
兩個正整數的運算式，運算元及運算子之間以空格隔開
輸出說明
兩個正整數的運算結果，總長度不超過 500 個位數
範例輸入
2222222222222222222222222 + 1111111111111111111111111
2222222222222222222222222 - 1111111111111111111111111
2222222222222222222222222 * 1111111111111111111111111
2222222222222222222222222 / 1111111111111111111111111
範例輸出
3333333333333333333333333
1111111111111111111111111
2469135802469135802469135308641975308641975308642
2
https://www.daniweb.com/programming/software-development/code/216587/python-can-handle-very-large-numbers
#======================================================
from itertools import dropwhile
from functools import reduce
class BigInt:
def __init__(self, val):
self.value = BigInt.parse(val) if isinstance(val, str) else val
def __str__(self):
v = BigInt.toComplement(self.value) \
if BigInt.isNegative(self.value) else self.value
builder = ['%04d' % v[i] for i in range(len(v) - 1, -1, -1)]
clist = list(dropwhile(lambda c: c == '0', list(''.join(builder))))
return '0' if len(clist) == 0 else ''.join(
((['-'] + clist) if BigInt.isNegative(self.value) else clist))
def __add__(self, that):
return (self - BigInt(BigInt.toComplement(that.value))) \
if BigInt.isNegative(that.value) else self.add(that)
def add(self, that):
length = max(len(self.value), len(that.value))
op1 = BigInt.copyOf(self.value, length)
op2 = BigInt.copyOf(that.value, length)
sum = BigInt.addForEach(op1, op2, 0)
return BigInt(
(((sum[0:-1] + [1]) if BigInt.isPositive(op1) else []) + [0] * 8)
if sum[-1] == 1
else (sum[0:-1] + [0 if BigInt.isPositive(op1) else 9999])
)
def __sub__(self, that):
return (self + BigInt(BigInt.toComplement(that.value))) \
if BigInt.isNegative(that.value) else self.sub(that)
def sub(self, that):
length = max(len(self.value), len(that.value))
op1 = BigInt.copyOf(self.value, length)
op2 = BigInt.copyOf(that.value, length)
remain = BigInt.subForEach(op1, op2, 0)
return BigInt(
((remain[0:-1] + [9998] if BigInt.isNegative(op1) else [])
+ [9999] * 8) if remain[-1] == 1
else (remain[0:-1] +
[9999 if BigInt.isNegative(op1) else 0])
)
def multiply(self, val, shift):
product = [0] * shift + \
BigInt.multiplyForEach(self.value, val, 0)
return BigInt((product[0:-1] + product[-1:] + [0] * 8) \
if product[-1] != 0 else (product[0:-1] + [0]))
def __mul__(self, that):
op1 = BigInt(BigInt.toComplement(self.value)) \
if BigInt.isNegative(self.value) else self
op2 = BigInt.toComplement(that.value) \
if BigInt.isNegative(that.value) else that.value
result = reduce(BigInt.__add__,
[op1.multiply(op2[i], i)
for i in range(len(op2) - 1)], BigInt('0'))
return BigInt(BigInt.toComplement(result.value)) \
if self.value[-1] + that.value[-1] == 9999 else result
def __ge__(self, that):
return False if BigInt.isNegative((self - that).value) else True
def isLessOrEqualsQuotient(self, op1, op2):
return True if op1 >= (self * op2) else False
def __floordiv__(self, that):
op1 = BigInt(BigInt.toComplement(self.value)) \
if BigInt.isNegative(self.value) else self
op2 = BigInt(BigInt.toComplement(that.value)) \
if BigInt.isNegative(that.value) else that
one = BigInt('1')
def quotient(left, right):
if right >= left:
x = (left + right).divide(2)
l, r = ((x + one, right)
if x.isLessOrEqualsQuotient(op1, op2)
else (left, x - one))
return quotient(l, r)
else:
return left - one
result = quotient(BigInt('0'), op1)
return BigInt(BigInt.toComplement(result.value)) \
if self.value[-1] + that.value[-1] == 9999 else result
@staticmethod
def divideForEach(op, val, remain):
if op == []:
return []
else:
tmp = op[-1] + remain
nextRemain = (tmp % val) * 10000
return [tmp // val] + \
BigInt.divideForEach(op[0:-1], val, nextRemain)
def divide(self, that):
result = BigInt.divideForEach(self.value, that, 0)
return BigInt(result[::-1] + [0] * (8 - (len(result) % 8)))
@staticmethod
def parse(val):
v = val[1:] if val[0] == '-' else val
digits = [int(v[i if i >= 0 else 0 : i + 4])
for i in range(len(v) - 4, -4, -4)]
zeros = [0] * ((len(digits) // 8 + 1) * 8 - len(digits))
return BigInt.toComplement(digits + zeros) \
if val[0] == '-' else (digits + zeros)
@staticmethod
def addForEach(op1, op2, carry):
if op1 == []:
return [carry]
else:
s = op1[0] + op2[0] + carry
nextCarry, c = (0, s) if s < 10000 else (1, s - 10000)
return [c] + BigInt.addForEach(op1[1:], op2[1:], nextCarry)
@staticmethod
def subForEach(op1, op2, borrow):
if op1 == []:
return [borrow]
else:
r = op1[0] - op2[0] - borrow
nextBorrow, c = (0, r) if r > -1 else (1, r + 10000)
return [c] + BigInt.subForEach(op1[1:], op2[1:], nextBorrow)
@staticmethod
def multiplyForEach(op, val, carry):
if op == []:
return [carry]
else:
tmp = op[0] * val + carry
nextCarry = tmp // 10000
return [tmp % 10000] + \
BigInt.multiplyForEach(op[1:], val, nextCarry)
@staticmethod
def toComplement(v):
c = [9999 - i for i in v]
return [c[0] + 1] + c[1:]
@staticmethod
def copyOf(original, newLength):
return original + [0 if BigInt.isPositive(original) else 9999
for i in range(len(original), newLength)]
@staticmethod
def isNegative(list):
return list[-1] == 9999
@staticmethod
def isPositive(list):
return list[-1] == 0
a = BigInt('99999999999999990999')
b = BigInt('-200')
print(a + b)
print(a - b)
print(a * b)
print(a // b)
===================== RESTART: F:/Python_APSC/a021-2.py =====================
99999999999999990799
99999999999999991199
-19999999999999998199800
-499999999999999954
>>>
沒有留言:
張貼留言