Karatsuba 알고리즘을 c언어로 구현했다.
매우매우매우매우 복잡하고 매우매우매우 더럽고 매우매우매우 직관적이지 않은 코드
이유
1. Karatsuba 하나를 위해 함수를 여러 개 작성했는데, 더 단순히 할 수 있을듯 하다..
2. Grade school보다 이론상 빨라야하는데, 느리다 ㅋㅋㅋ ㅋㅋㅋㅋㅋㅋ
3. valgrind로 메모리 누수를 체크해본결과 매우 많이 새고있다..
4. 메모리 누수 때문인지 큰 수에서는 오히려 안 돌아간다.. 100자리까지는 잘 돌아간다.
a, b가 256자리라면 이렇게 절반으로 쪼갠다
그런데.. 이렇게 하더라도 사실 빨라지지 않는다. 여전히 O(n^2)의 시간복잡도이다.
여기서 Gauss's trick이 등장한다.
그리고 곱셈을 진행하는데, T(n) = 3T(n/2)+O(n)이라
T(n) ~= O(n^1.59)가 된다.
즉, grade school의 O(n^2)보다 빠르다!
char * karatsuba(char * num1, char * num2)
{
int len1 = strlen(num1);
int len2 = strlen(num2);
if(len1 <2 || len2 <2)
{
return grade_school(num1, num2);
}
int total = len1 + len2;
char * ans_ret = (char *)calloc(total+1, sizeof(char));
int len;
// find min(len1, len2)
if(len1<len2)
{
len = len1;
}
else
{
len = len2;
}
// half-length
int hlen;
hlen = floor(len/2);
// make a, b, c, d in karatsuba algorithm
char * num11 = (char *)calloc(len1-hlen+2, sizeof(char));
memcpy(num11, num1, len1-hlen);
char * num12 = (char *)calloc(hlen+1, sizeof(char));
memcpy(num12, num1+len1-hlen, hlen);
char * num21 = (char *)calloc(len2-hlen+2, sizeof(char));
memcpy(num21, num2, len2-hlen);
char * num22 = (char *)calloc(hlen+1, sizeof(char));
memcpy(num22, num2+len2-hlen, hlen);
char * ac;
char * bd;
char * temp;
char * abcd;
// set each variable
ac = karatsuba(num11, num21);
bd = karatsuba(num12, num22);
temp = karatsuba(sum(num11, num12), sum(num21, num22));
abcd = minus(temp, sum(ac, bd));
ans_ret = sum(sum(zero_plus(ac, 2*hlen), zero_plus(abcd, hlen)), bd);
return ans_ret;
}
free 과정은 생략했다. 최소 단위인 한 자리수에서는 grade_school 알고리즘으로 곱셈했다.
각 함수 설명
minus : karatsuba를 위해 만든 함수, 첫 포인터에서 두번째 포인터를 빼고 char 포인터로 return한다.
sum : minus와 마찬가지로 더한 값을 return한다.
zero_plus : 위에서 알고리즘 설명할 때, 10^n을 해주기 위해 n자리만큼 0을 string 뒤에 추가하는 함수이다.