어릴적에 계산기를 가지고 놀면서 말도안되는 큰 수 두개를 더하거나 곱하면 계산기 표시 범위 밖으로 나가서 e (expotential)이라는 글자를 본 경험이 한번쯤은 있을것이라 생각한다.
컴퓨터도 이와 마찬가지로 자신의 데이터타입을 뛰어넘는 결과값을 가지는 계산은 수행하지 못한다.
정수형의 데이터타입 int의 경우 표현할 수 있는 수는
–2,147,483,648 ~ 2,147,483,647 이다. 즉 -20억에서 20억정도까지 표현가능하다. (C언어 기준)
그렇다면 이 이상의 정수들의 계산값은 어떻게 해야 할까?
그래서 나온 것이 이 큰 정수의 계산 알고리즘이다.
사실 알고리즘이라고 하기에는 좀 단순한편이다. 덧셈 곱셈을 처음 배울 때 사용한 계산법을 사용하면 된다. 하지만 그 구현은 전혀 쉽지 않다.
큰 정수의 덧셈
덧셈은 매우 간단한 계산법중 하나이다.
각 자리수별로 리스트에 거꾸로 저장하고, 반복문을 통해
리스트에서 순서대로 꺼내면서 합을 구하고 결과값 리스트에 따로 저장한다.
그와 동시에 두 수의 값이 10이상이면 carry를 1로 저장하여 다음 자리수 계산에 반영하는 방식이다.
파이썬 코드
def ladd (u, v):
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
value = i + j + carry
carry = value // 10
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(567832 + 9423723)
print(ladd(u, v)[::-1])자바 코드
static ArrayList<Integer> sum(char[] u, char[] v) {
int n = 0;
ArrayList<Integer> result = new ArrayList<Integer>();
if (u.length > v.length ) {
n = u.length;
}
else {
n = v.length;
}
int carry = 0;
for (int k = 0; k < n; k++) {
int i = 0;
int j = 0;
if (k < u.length) {
i = u[k] - '0';
}
if (k < v.length ) {
j = v[k] - '0';
}
int value = i + j + carry;
carry = value / 10;
int ans = value % 10;
result.add(ans);
}
if (carry > 0) {
result.add(carry);
}
return result;
}유의할점은 리스트에 123 이라는 숫자를 저장한다고 하면 321 순서로 저정해야 한다는점이다.
파이썬의 경우 숫자를 입력하고 split으로 나눈다음, reverse를 사용하여 리스트를 뒤집으면 쉽게 해결되지만 자바의 경우 array를 reverse 하는 함수가 따로 존재하지 않는다. 이에 두가지 방법을 쓰는데 하나는 list로 변환한 후 reverse 하는 방법이다. 다른 하나는 직접 작성하여 뒤집는 방법이다.
리스트를 뒤집는 코드
for (int i = 0; i < str1.length/2 ; i++) {
char temp = str1[i];
str1[i] = str1[str1.length -i -1];
str1[str1.length-i-1] = temp;
}
for (int i = 0; i < str2.length/2 ; i++) {
char temp = str2[i];
str2[i] = str2[str2.length -i -1];
str2[str2.length-i-1] = temp;
}큰 수의 덧셈은 이와 같이 기본적인 계산원리를 구현해놓은것에 불과하다.
큰 정수의 곱셈
큰 정수의 곱셈은 단순 무식한 Brute-Force 방법으로 풀게 되면 초등학교에서 배운 방법으로 풀수 있다. 다만 이렇게 코딩을 구현 할 경우 코드가 길어지고 Θ(𝑛^2)의 시간복잡도를 가지게 된다.
이에 곱셈의 경우 Divide and Conquer 를 통해 계산하게 된다.
해당과정은 다음과 같다
현)경북대학교 컴퓨터학부 초빙교수님이 직접 운영하시는 주니온 TV 채널에서 따온 자료이다. 정말 좋은 수업이니 다들 모르는게 있다면 찾아서 들어보면 도움이 많이 될 것이라 생각된다. Youtube
따라서 우리는 이 과정에 맞춰서 나온 공식을 코드로 구현하면 된다.
def prod (u, v):
n = len(u) if (len(u) > len(v)) else len(v)
threshold = 1
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^2𝑚 + 𝑥𝑧 + 𝑦𝑤 × 10^𝑚 + 𝑦z를 +를 기준으로 나눈 후 각 파트를 p1 p2 p3로 지정하고 계산을 수항해고 최종적으로 ladd를 통해 모두 합해주는 과정을 거치게 된다.
threshold의 역활은 만약 입력값이 int범위내에서 처리가 가능한 범위이면 기존의 방식대로 처리하기위해 주는 값이지만 여기서는 여러가지를 테스트 해야 하기에 1로 설정하여 모든 계산에서 작동하지 않도록 설정하였다.
다음은 계산을 수행하는 exp, div, rem, lmult에 관하여 설명하겠다.
- ladd는 위에서 사용한 큰수의 합이다.
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]
exp는 10^n을 수행하기 위한 메소드이다. 어떤 수에 10의 n승을 곱하면 n만큼 0이 뒤에 생기게 된다. 123에 10^3을 하면 123,000이 되는 원리이다. 따라서 n의 크기만큼 0을 추가하고 기존값을 더해주는것으로 계산이 완료된다.
div 와 rem은 나눈값과 나머지이다. 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 resultlmult의 경우 ladd 같이 곱셈을 수행하는 식이다. 두 값을 곱하고 나눈 10으로 나눈 몫이 carry가 되고 나머지가 result에 저장되는 방식이다. 이는 divide가 최종단계까지 가서 더 이상 나눌 수 없을때 작동하게 된다
그냥 a * b를 해도 될거같긴한데 자세한건 확인을 해 봐야 알 수 있을것 같다.
def prod (u, v):
n = len(u) if (len(u) > len(v)) else len(v)
threshold = 1
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)
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 ladd (u, v):
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
value = i + j + carry
carry = value // 10
result.append(value % 10)
if (carry > 0):
result.append(carry)
return result
이렇게 방대한 전 과정을 끝내고 나면 큰 수를 계산하는 하나의 알고리즘이 완성된다.
하지만 이 알고리즘에는 함정이 있다. 바로 시간복잡도가 기존의 방식과 동일하다는 점이다. 아니 이게 무슨 소리인가? 이렇게 열심히 식을 짜왔는데 brute-force 랑 같은 시간이 걸린다니?
우선 시간복잡도를 파악해보겠다.
⁃ prod() 함수에서 재귀 호출을 네 번 한다는 것에 주목
⁃ 𝑊(𝑠) = 0, 𝑊(𝑛) = 4𝑊(𝑛/2) + 𝑐𝑛
⁃ 𝑊(𝑛) ∈ Θ(𝑛^log2^4) = Θ(𝑛^2)
즉, 시간복잡도 면에서 큰 효율이 없는 나쁜 알고리즘이 된 것이다.
다만 이러한 문제는 약간의 개선을 통해 해결 될 수 있다.
바로 4번이나 되는 재귀호출 횟수를 줄여가는것이다.
이와 관련된 자료는 교수님의 강의자료로 대체하도록 하겠다
간단히 요약하자면 r을 빼는것으로 재귀횟수를 한 번 줄일수 있다는것이다.
def prod2 (u, v):
n = len(u) if (len(u) > len(v)) else len(v)
threshold = 1
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 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 ladd (u, v):
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
value = i + j + carry
carry = value // 10
result.append(value % 10)
if (carry > 0):
result.append(carry)
return result
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
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(567832 * 9423723)
print(prod2(u, v)[::-1])이에 맞춰 작성되는 알고리즘에는 lsub라는 새로운 기능이 들어간다. 작동원리는 ladd와 유사하기떄문에 생략하도록 하겠다.
이 경우 시간복잡도는 재귀가 3회로 줄어들어서
• 재귀 호출의 숫자를 3회로 줄임
• 𝑊 𝑛 ∈ Θ (𝑛^log2 3) ≈ Θ(𝑛^1.58)
즉, Θ(𝑛^1.58). 이 된다.
Θ(𝑛^2) 과 Θ(𝑛^1.58). 그냥보기에는 별 차이 없어보이지만 큰수가 들어가면 그 결과는 수십배가 넘게 차이나게 된다.
이렇게 개선된 큰 수 곱셈 알고리즘이 완성되었다.
이 알고리즘을 공부하면서 가장 크게 느낀점이라면
하나, 컴퓨터가 생각보다 똑똑하지 않다는점과
둘, 약간의 차이가 큰 변화를 가지고 온다는 점이다.
물론 내가 저 약간의 차이를 만들수 있을까에 대한 의문에는 아마 어렵다는 생각이 든다.
하지만 남들이 만들어준 약간의 차이를 이용하는 수준까지는 도달해야 한다 생각한다.
