Skip to content

Instantly share code, notes, and snippets.

@sooop

sooop/BigInt.py Secret

Created November 15, 2014 11:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sooop/f92f85b50f9e0b409f90 to your computer and use it in GitHub Desktop.
Save sooop/f92f85b50f9e0b409f90 to your computer and use it in GitHub Desktop.
class BigInt(object):
UNIT_LENGTH = 5
def __init__(self, string):
self.digits = []
if type(string) == str:
self.parse(string)
elif type(string) == list:
for i in string:
self.digits.append(i)
self.negative = False
def parse(self, string):
while True:
if len(string) > BigInt.UNIT_LENGTH:
self.digits.append(int(string[-BigInt.UNIT_LENGTH:]))
string = string[:-BigInt.UNIT_LENGTH]
else:
self.digits.append(int(string))
break
@property
def description(self):
result = ""
for unit in self.digits:
result = ("000000" + str(unit))[-BigInt.UNIT_LENGTH:] + result
result = result.lstrip("0")
if self.negative:
result = '-' + result
return result
def addTo(self, num):
upFlag = 0
resultArray = []
i = 0
UNIT_CUT = 10**BigInt.UNIT_LENGTH
UNIT_LIMIT = UNIT_CUT - 1
while True:
nl = self.digits[i] if i < len(self.digits) else 0
rl = num.digits[i] if i < len(num.digits) else 0
d_sum = nl + rl + upFlag
resultArray.append(d_sum % UNIT_CUT)
upFlag = (d_sum // UNIT_CUT)
if d_sum + upFlag == 0:
break
i += 1
return BigInt(resultArray)
def multiplty(self, num):
UNIT_CUT = 10**BigInt.UNIT_LENGTH
UNIT_LIMIT = UNIT_CUT - 1
toBeSummed = []
finalResult = []
level = 0
for i in self.digits:
upFlag = 0
tempResult = []
for x in range(0, level):
tempResult.append(0)
for j in num.digits:
d_sum = i * j + upFlag
tempResult.append(d_sum % UNIT_CUT)
upFlag = d_sum // UNIT_CUT
if upFlag != 0:
tempResult.append(upFlag)
toBeSummed.append(tempResult)
level += 1
i = 0
upFlag = 0
while True:
currentSummed = map(lambda x:x[i], filter(lambda x:len(x) > i, toBeSummed))
if len(currentSummed) == 0:
if upFlag != 0:
finalResult.append(upFlag)
break
currentSum = sum(currentSummed) + upFlag
finalResult.append(currentSum % UNIT_CUT)
upFlag = currentSum // UNIT_CUT
i += 1
return BigInt(finalResult)
a = BigInt('1')
for i in xrange(2,300+1):
a = a.multiplty(BigInt(str(i)))
#a = a.addTo(BigInt(str(i)))
print a.description
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment