톰-쿡 알고리즘 개요

Posted by 적분 ∫2tdt=t²+c
2014.03.30 05:49 프로그래밍/Multi precision

카라슈바 알고리즘까지는 쉽게 이해했는데,톰-쿡 알고리즘은 괜히 어려워 보여서 그동안 접근하지 못했는데


사실 알고보면 단순한 거였슴다!


일반적인 곱셈 방법으로는 n자리 수 간의 곱셈을 수행하게 되면 총 n^2번의 곱셈이 필요하게 된다. 당연한 말씀.예를 들어

을 곱하고자 한다면 각 자리수마다 한 번씩 곱셈을 해야하니 총 36번의 곱셈을 해야겠지요..


근데 안드레이 톰과 스테픈 쿡이라는 학자가 발상의 전환을 했어요. (카라슈바마냥ㅋ)


숫자를 다항식으로 보고, 다항식끼리 곱하는거야


(그나마 간단한 톰-3 알고리즘을 중심으로 설명할게요.)

숫자 nm을 다항식으로 바꾸기 위해 3조각으로 나누도록하겠습니다. 한 조각의 단위는 100으로 잡으면 되겠네요.



자 이 조각을 계수로 이용해서 다항식을 만들어봅시다.


참 쉽죠? x에 100을 대입하면 P(100)=n, Q(100)=m이 될거라는 부연설명을 굳이 붙일 필요도 없겠네요. 두 다항식의 곱을 R(x)라고 하죠. 즉 R(x) = P(x)Q(x). 그렇다면 우리가 구하고자하는 nmP(100)*Q(100) = R(100)이 되겠습니다. 여기까지 보면 "그래서요? 뭐가 달라졌다는거죠?" 하겠지만 발상의 전환은 이제부터입니다.




R(100)을 구하기 위해서는 R(x)의 계수들을 구하면 됩니다. P(x)Q(x)가 2차식이었으니깐, R(x)는 당연히 4차식이 되겠죠. 여기서 잠깐, 4차식의 계수는 총 5개죠. 이 계수들을 모른다고 할때, 계수들을 알기 위해서는 방정식이 몇개 필요하더라...? 5개죠.


그럼 x에 적당한 수를 대입해서 방정식을 세워봅시다.


(마지막에 무한대가 들어간 수식은 편의를 위한 표기입니다. 저 표기가 마음에 안 들면 w4의 값은 n2 m2의 곱으로 이뤄진다는 정도로만 생각하고 가면 됩니다.)

이 다섯개의 값을 구하기 위해서는 다섯 번의 곱셈만 있으면 됩니다. 한번 실제로 값을 넣어서 계산해 볼까요?


결과는 아래와 같이 나와요.


(어째 결과가 무시무시하게 나오냐. 배보다 배꼽이 더 큰듯. -> 실제로 너무 작은 수에 대해서 톰-쿡 알고리즘을 적용하면 일반 곱셈법보다도 느리게 나옵니다. 여기서는 예를 위해 작은 수를 들었을 뿐이고 실제로는 훨~~씬 더 큰 수에 적용해야돼요.)


이쯤되면 무릎을 탁 치고 계실 분도 있을거에요. 이제부터는 적당히 위 식들을 더하고 빼줘서 미지수를 구하면 됩니다. 벌써 w0, w4는 구해졌고, 나머지만 구하면 되겠네요. 계산 과정은 굳이 적을 필요 없을 거 같아요. 서로 더하고 빼고, 2 혹은 3으로 나누는것만 하면 아래처럼 결과가 나옵니다.


이제 이걸 R(x)에 대입해서 x에 100을 넣으면 계산결과가 나오겠죠?!


적당히 100을 넣어서 숫자들을 다시 합치면


짠!


우리가 얼마나 이득을 보았는지 따져보죠. 우리가 112233와 445566을 3조각으로 나누고 일반 곱셈 알고리즘을 사용했다면 총 9번의 곱셈이 필요했을 거에요. 하지만 톰-3 알고리즘에서는 총 5번의 곱셈만 했죠. P(0)Q(0), P(1)Q(1), P(-1)Q(-1), P(2)Q(2), P(∞)Q(∞)를 구하는데 말이에요. (물론 방정식 풀때 소소하게 2 혹은 3으로 곱하는 경우가 있지만, 상수 곱셈은 실제로 정수가 매우 커지면 미미하니깐 쿨하게 무시해요.)


9번의 곱셈을 5번으로 줄이는데 성공. 덧뺄셈은 곱셈에 비해 시간복잡도가 껌도 안되니 크게 고려할 필요가 없어요.


이 과정은 역시나 재귀적으로 적용될 수가 있습니다. 정수가 충분히 작아질때까지 톰-쿡 알고리즘을 사용하면 곱셈량이 기하급수적으로 줄겠죠.

그래서 이 알고리즘의 시간복잡도는 원래 O(n^2)이던걸 O(n^1.465)로 줄일수 있습니다. 이건 3조각으로 나누었을 경우고, 나누는 조각을 더 늘리면 시간복잡도를 더 줄일수 있습니다. 2조각으로 나누었을 경우는 카라슈바 알고리즘과 동일해집니다.


무지막지하게 많이 나눌수록 더 빨라지는거 아냐? 하겠지만, 조각을 많이 나눌수록, 다항식의 차수는 높아지고, 미지계수의 수도 늘어나죠. 20차식에서 21개의 미지계수를 구하기 위해 방정식 21개를 풀고 있다고 생각하면 골이 아파지죠... 고려할 경우도 늘어나고. 그래서 보통은 3~8조각 정도까지만 사용하고, 그 보다 더 빠른 곱셈을 위해서는 FFT를 이용합니다. 끗.



Tags
이 댓글을 비밀 댓글로