큰 정수의 덧셈

기본 내용

• 리스트를 이용하여 각 자리수(digit)를 하나의 원소로 저장
  ex) 654,321 -> S = [1, 2, 3, 4, 5, 6]으로 저장

  6 = S[5]
  5 = S[4]
  4 = S[3]
  3 = S[2]
  2 = S[1]
  1 = S[0]

• 𝑛개의 자릿수(digit) 각각을 더하면서 올림수(carry)를 고려
  

Python 코드 (덧셈)

정의

def ladd (u, v): # long add(긴덧셈)
  n = len(u) if (len(u) > len(v)) else len(v) #삼항식
  
  #초기값
  result = []
  carry = 0
  
  for k in range(n):
  	i = u[k] if (k < len(u)) else 0 
  	j = v[k] if (k < len(v)) else 0
  	# else 0은 4자리수와 3자리수의 덧셈에서 3자리수의 맨앞이 0을 의미
  	
    	value = i + j + carry # 1차 덧셈
  	carry = value // 10 #올림수, // : 정수부분만
  	result.append(value % 10) # % : 나머지부분만
  
  if (carry > 0):
  	result.append(carry)
  
  return result

예시 코드

u = [6, 7, 8, 9]
v = [3, 4, 5]
print(9876 + 543)
print(ladd(u, v)[::-1])

u = [2, 3, 8, 7, 6, 5]
v = [3, 2, 7, 3, 2, 4, 9]
print(567832 + 9423723)
print(ladd(u, v)[::-1])

큰 정수의 곱셈

기본 내용

• 분할정복법 (재귀호출 4번으로 효율성은 의미가 없다.)
  4번 : xw, wz, yw, yz

• 강화된 곱셈법 (재귀호출을 3번으로 줄인다.)
  3번 : xw, wz+yw, yz
  

Python 코드 (곱셈 - 분할정복법)

분할정복 곱셈 정의

def prod (u, v):
  n = len(u) if (len(u) > len(v)) else len(v)
  if (len(u) == 0 or len(v) == 0):
  	return [0]
  elif (n <= threshold):
  	return lmult(u, v)
  else:
        m = n // 2
        x = div(u, m); y = rem(u, m)
        w = div(v, m); z = rem(v, m)
        p1 = prod(x, w)
        p2 = ladd(prod(x, z), prod(w, y))
        p3 = prod(y, z)
        return ladd(ladd(exp(p1, 2*m), exp(p2, m)), p3)

10^n, 몫, 나머지 정의

# 10^n
def exp (u, m):
  if (u == [0]):
	  return [0]
  else:
 	 return ([0] * m) + u

#몫
def div (u, m):
  if (len(u) < m):
	  u.append(0)
  return u[m : len(u)]

#나머지
def rem (u, m):
  if (len(u) < m):
	  u.append(0)
  return u[0 : m]

곱셈 정의

def lmult (u, v):
  i = u[0] if (0 < len(u)) else 0
  j = v[0] if (0 < len(v)) else 0
  value = i * j
  carry = value // 10
  result = []
  result.append(value % 10)
  
  if (carry > 0):
  	result.append(carry)
  return result

예시 코드

u = [2, 3, 8, 7, 6, 5]
v = [3, 2, 7, 3, 2, 4, 9]
print(exp(u, 3))
print(div(u, 3))
print(rem(u, 3))

u = [2, 3, 8, 7, 6, 5]
v = [3, 2, 7, 3, 2, 4, 9]
print(567832 * 9423723)
print(prod(u, v)[::-1])

Python 코드 (곱셈 - 개선)

개선 곱셈 정의

def prod2 (u, v):
  n = len(u) if (len(u) > len(v)) else len(v)
  if (len(u) == 0 or len(v) == 0):
  	return [0]
  elif (n <= threshold):
  	return lmult(u, v)
  else:
        m = n // 2
        x = div(u, m); y = rem(u, m)
        w = div(v, m); z = rem(v, m)
        r = prod2(ladd(x, y), ladd(w, z))
        p1 = prod2(x, w)
        p3 = prod2(y, z)
        p2 = lsub(r, ladd(p1, p3))
        return ladd(ladd(exp(p1, 2*m), exp(p2, m)), p3)

뺄셈 정의

def lsub (u, v):
  n = len(u) if (len(u) > len(v)) else len(v)
  result = []
  borrow = 0
  for k in range(n):
    i = u[k] if (k < len(u)) else 0
    j = v[k] if (k < len(v)) else 0
    value = i - j + borrow
    if (value < 0):
      value += 10
      borrow = -1
    else:
      borrow = 0
      result.append(value % 10)
  if (borrow < 0):
      print("음의 정수는 처리 못함.")
  return result

예시 코드

u = [2, 3, 8, 7, 6, 5]
v = [3, 2, 7, 3, 2, 4, 9]
print(567832 * 9423723)
print(prod(u, v)[::-1])
print(prod2(u, v)[::-1])

출처 : 링크텍스트