Karatsuba

Karatsuba 알고리즘을 c언어로 구현했다.
매우매우매우매우 복잡하고 매우매우매우 더럽고 매우매우매우 직관적이지 않은 코드
이유
1. Karatsuba 하나를 위해 함수를 여러 개 작성했는데, 더 단순히 할 수 있을듯 하다..
2. Grade school보다 이론상 빨라야하는데, 느리다 ㅋㅋㅋ ㅋㅋㅋㅋㅋㅋ
3. valgrind로 메모리 누수를 체크해본결과 매우 많이 새고있다..
4. 메모리 누수때문인지 큰 수에서는 오히려 안 돌아간다.. 100자리까지는 잘 돌아간다.

Karatsuba 알고리즘이란?

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 뒤에 추가하는 함수이다.