56. Karatsuba's Algorithm

두 정수의 곱을 구할 때, 곱한 결과가 일반적인 정수 자료형에 저장하기에는 너무 큰 경우 정수를 문자열 형태로 저장한 후 직접 곱셈을 구현해야 한다. $100\text{~}1000$자리 정도의 정수를 곱할 때는 일반적인 $\Theta(n^2)$ 곱셈을 구현해도 괜찮지만 자릿수가 $10000$ 단위가 되면 $\Theta(n^2)$ 곱셈은 속도가 많이 느려지게 된다. 이때 카라츠바 알고리즘(Karatsuba's Algorithm)을 이용하면 곱셈의 시간복잡도를 $\Theta(n^{\text{lg }3})$으로 줄일 수 있다.

 

카라츠바 알고리즘은 분할 정복을 이용하여 정수의 곱을 계산하는 과정에서 중복된 계산을 유도한다. 계산이 중복되면 한 번만 해도 되므로 그만큼 연산 횟수가 줄어들게 된다. 곱해야 하는 두 수가 $a$와 $b$이고 각각의 자릿수가 $n$일 때, 카라츠바 알고리즘은 먼저 $a$와 $b$를 다음과 같이 두 부분으로 나눈다. (두 부분의 자릿수가 같아야 하므로 $n$은 짝수여야 한다. 만약 자릿수가 홀수인 경우 맨 앞에 $0$을 하나 추가해서 자릿수가 짝수인 것처럼 만들면 된다.)

$$a = a_0 \times 10^{n/2} + a_1$$

$$b = b_0 \times 10^{n/2} + b_1$$

그러면 $a \times b$는 다음과 같이 나타낼 수 있다.

$$a \times b = (a_0 \times 10^{n/2} + a_1) \times (b_0 \times 10^{n/2} + b_1)$$

$$= a_0b_0 \times 10^n + (a_0b_1 + a_1b_0) \times 10^{n/2} + a_1b_1$$

이때 가운데 항의 계수 $a_0b_1 + a_1b_0$를 다음과 같이 나타낼 수 있다.

$$a_0b_1 + a_1b_0$$

$$= a_0b_0 + a_0b_1 + a_1b_0 + a_1b_1 - a_0b_0 - a_1b_1$$

$$= (a_0 + a_1)(b_0 + b_1) - a_0b_0 - a_1b_1$$

따라서 다음과 같은 결과가 나온다.

$$a \times b = a_0b_0 \times 10^n + ((a_0 + a_1)(b_0 + b_1) - a_0b_0 - a_1b_1) \times 10^{n/2} + a_1b_1$$

이 식을 계산할 때 곱셈으로 구해야 하는 값은 $a_0b_0, a_1b_1, (a_0 + a_1)(b_0 + b_1)$의 세 가지이고, 모두 자릿수가 $\frac{n}{2}$인 두 수를 곱하므로 연산 횟수는 총 $\frac{3}{4}n^2$번이 된다. 일반적인 곱셈에 비해 연산 횟수가 $\frac{3}{4}$배로 줄어들었다. 또한 세 번의 곱셈 역시 위와 같은 방법으로 더 적은 연산으로 할 수 있고, 이렇게 재귀적으로 계산하면 앞에서 언급한 것과 같이 $\Theta(n^{\text{lg }3})$의 시간복잡도가 나오게 된다.

 

구현은 다음과 같다. 자릿수가 크지 않을 경우 일반적인 곱셉을 이용하는 것이 오히려 더 빠르기 때문에 자릿수가 어느 정도로 작아지면 단순 곱셈으로 처리한다. 일반적으로 자릿수가 $50\text{~}100$ 이하가 되면 단순 곱셈으로 처리하는 것이 더 빠르다고 한다.

vector<int> f(vector<int>&a, vector<int>&b, int p)
{
    vector<int>w(p << 1);
    if(p < 100)
    {
        for(int i = 0; i < p; i++)
        {
            for(int j = 0; j < p; j++)w[i + j] += a[i] * b[j];
        }
    }
    else
    {
        int h = p >> 1;
        vector<int>a0(a.begin(), a.begin() + h);
        vector<int>a1(a.begin() + h, a.end());
        vector<int>b0(b.begin(), b.begin() + h);
        vector<int>b1(b.begin() + h, b.end());
        vector<int>z0 = f(a0, b0, h);
        vector<int>z2 = f(a1, b1, h);
        for(int i = 0; i < h; i++)
        {
            a0[i] += a1[i];
            b0[i] += b1[i];
        }
        vector<int>z1 = f(a0, b0, h);
        for(int i = 0; i < p; i++)
        {
            w[i] += z0[i];
            w[h + i] += z1[i] - z0[i] - z2[i];
            w[p + i] += z2[i];
        }
    }
    return w;
}

함수 $f$는 길이가 $p$인 벡터 $a$와 $b$를 인자로 받아서 $w$에 $a$와 $b$의 곱을 저장한 뒤 반환한다. $z_0, z_1, z_2$는 각각 $a_0b_0, (a_0 + a_1)(b_0 + b_1), a_1b_1$을 의미한다. 이 함수는 기본적으로 $a$와 $b$를 다항식으로 간주해서 곱하게 구현되어 있기 때문에 두 정수를 곱할 경우에는 마지막에 받아올림을 처리해 주어야 한다.

 

카라츠바 알고리즘을 이용하면 큰 수 또는 차수가 큰 다항식을 빠르게 곱할 수 있다. 하지만 벡터의 생성이 많고, 자릿수가 $10$만 단위가 되면 속도가 느려진다는 단점이 존재한다. 이후에 소개할 FFT라는 대안이 존재하기 때문에 카라츠바 알고리즘을 사용하는 경우는 많지는 않지만, FFT를 안 쓸 경우 이 방법이 상당히 효과적이라고 할 수 있다.

 

[연습문제]

 

BOJ 1067. 이동 (Platinum II)

수열 $a$를 두 번 반복하고, 수열 $b$는 뒤집어서 카라츠바 알고리즘으로 서로 곱했을 때 나오는 항의 계수 중 가장 큰 값이 답이 된다.