만약 하드웨어의 저장 공간을 넘어서는 숫자들의 연산을 해야 한다면 어떻게 해야 할까요?
이 경우에 유일한 대안은 소프트웨어적으로 숫자들을 표현하고 처리해야 합니다.
방법은 숫자들을 하나씩 쪼개서 배열에 넣는 방법이 있습니다. 이때 배열에는 역순으로 넣어야 합니다.
1. 알고리즘 및 코드
우선 긴 숫자를 쪼개 봅시다.
\(u\,=\,x\times10^m+y\)
\(v\,=\,w\times10^m+z\)
일 때,
\(uv\, =\, \left (x \times 10^m + y \right )\left ( w\times10^m+z \right )\)
이고, 이는 \(xw\times10^{2m}+(xz+wy)\times10^m+yz\)
입니다.
이것을 통해 쉽게 계산할 수 있습니다.
Problem : 큰 정수의 곱셈
Input : 큰 정수 두 개와 threshold
Output : 두 정수의 곱셈 결과
알고리즘)
1. 큰 정수를 기준으로 반으로 나눈다. (큰 정수의 길이가 n이면 m = n//2)
2. 위의 수식을 적용한다. (곱셈 재귀 호출)
3. 만약 재귀 호출을 하였는데도 길이가 threshold보다 크면 또다시 1~3번 반복한다.
코드, Python)
import sys
input = sys.stdin.readline
threshold = int(input()) # 임곗값 입력
A = list(map(int, reversed(input().strip()))) # input받은 것을 '\n'을 제외하고 역순 처리
B = list(map(int, reversed(input().strip()))) # input받은 것을 '\n'을 제외하고 역순 처리
def list_to_int(A):
# 숫자형 리스트를 정수로 바꿔줌
A.reverse()
A = ''.join(list(map(str, A))) # 숫자형 리스트를 string 타입 변환 후 이어붙임
return A
def roundup_carry(A):
# 반올림 함수
carry = 0
for i in range(len(A)):
A[i] += carry # carry의 초깃값은 0이라 A[0]에 영향을 주지 않지만, loop문 안에서 carry가 업데이트 되면서, 그 다음 A[i]에게 영향을 줌
carry = A[i] // 10 # carry 업데이트
A[i] %= 10 # A[i] 업데이트
if carry != 0: # A배열이 끝났는데 carry가 0이 아니면
A.append(carry) # 리스트의 끝에 반올림 해줌
def ladd(A, B):
# 더하기 함수
c = [0] * max(len(A), len(B)) # 둘 중에 큰 길이의 배열로 길이 설정
for i in range(len(c)): # 일단 다 더함
if i < len(A): c[i] += A[i]
if i < len(B): c[i] += B[i]
roundup_carry(c) # 반올림 함수를 통해 c 배열을 업데이트
return c
def lmult(A, B):
# A, B 단순 곱셈 함수
c = [0] * (len(A) + len(B) - 1)
for i in range(len(A)):
for j in range(len(B)):
c[i + j] += A[i] * B[j]
roundup_carry(c)
return c
def div_by_exp(A, m):
# A // 10^m 함수
if len(A) <= m: # A와 m의 자릿수가 같다면 몫은 0임
return [0]
return A[m:]
def rem_by_exp(A, m):
# A % 10^m 함수
if len(A) <= m: # A와 m의 자릿수가 같다면 나머지는 A임
return A
return A[:m]
def pow_by_exp(A, m):
# A * 10^m 함수
remove_zero(A)
if len(A) == 0:
return [0]
c = [0] * m # c에 0을 먼저 집어 넣음
c.extend(A) # c에 A를 extend함
return c
def remove_zero(A):
# 맨 뒤의 0을 없애주는 함수
while len(A) != 0 and A[-1] == 0: # 리스트가 비지 않고, 맨 뒤에가 0일 때
A.pop()
def prod(A, B):
# 큰 숫자의 곱하기 함수
[remove_zero(x) for x in [A, B]] # A, B의 끝에 0이 들어가는지 우선 check
globals()['count'] += 1 # global 변수 count 참조 및 수정
N = max(len(A), len(B)) # 큰 숫자의 분할을 위해 N 설정, 이 N은 추후 m = N // 2 를 위해 활용
if len(A) == 0 or len(B) == 0: # A, B 둘중에 하나라도 길이가 0이면 0이므로 곱하기는 0이 됨
C = [0] # 수정 해봐야함
elif N <= threshold: # N이 임곗값 보다 작으면
C = lmult(A, B) # 단순 계산을 함
else:
# xw * 10^2m + (xz + yw) * 10^m + yz
m = N // 2 # 큰 숫자를 분할
x = div_by_exp(A, m); y = rem_by_exp(A, m) # A를 분할
w = div_by_exp(B, m); z = rem_by_exp(B, m) # B를 분할
t1 = prod(x, w); t2 = pow_by_exp(t1, 2 * m) # t2 = xw * 10^2m
t3 = prod(x, z); t4 = prod(y, w); t5 = ladd(t3, t4); t6 = pow_by_exp(t5, m) # t6 = (xz + yw) * 10^m
t7 = prod(y, z) # t7 = yz
t8 = ladd(t2, t6); C = ladd(t7, t8) # 전체 더하기
return C
globals()['count'] = 0 # 글로벌 변수 count 선언
C = prod(A, B)
remove_zero(C)
print(globals()['count'])
# for i in range(len(C) - 1, -1, -1):
# print(C[i],end='')
# print()
print(list_to_int(C) if len(C) else 0)2. 시간 복잡도 분석
basic operation : 덧셈, 뺄셈, 거듭제곱, 나머지 계산, 몫 계산
Input size : n
worst-case는 두 정수 모두 0과 같은 숫자가 없는 경우입니다.
왜냐하면 이 알고리즘의 재귀의 끝은 threshold가 끝나야지만 끝나기 때문입니다.
따라서 n이 2의 거듭제곱이라면 계속해서 재귀를 합니다.
따라서 시간 복잡도는
\(W(n)=4W(\frac{n}{2})+cn\)이 됩니다.
즉, \(W(n)\,\epsilon\,\Theta(n^{lg4})=\Theta(n^2)\)이 됩니다.
더 좋은 시간 복잡도도 있는데 이는 추후 공부하고 올리겠습니다.
감사합니다.
지적 환영합니다.