Karatsuba Algorithm

카라추바 알고리즘

• 곱셈을 더 빠르게 하기 위한 알고리즘
  • 가장 긴 자릿수 $N$에 대해 $O(N^{\log 3})$까지 시간복잡도를 줄일 수 있음
• 비교 알고리즘 (기존 방법) : 곱셈 문제에서 설명되는 곱셈 방법
  • 각 자릿수를 곱하는 과정을 반복하여 계산하므로 총 $O(N^2)$의 곱셈 연산이 필요

작동 원리

곱셈 연산은 덧셈, 뺄셈보다 기본적으로 더 많은 연산이 필요하므로 실행시간이 더 오래 걸린다. 앞에서 얘기했든 기존의 곱셈 방법은 $O(N^2)$의 복잡도를 가지지만 덧셈과 뺄셈은 $O(N)$의 복잡도를 가진다. 카라추바 알고리즘은 곱셈 연산의 횟수를 줄이고 대신 덧셈과 뺄셈 연산을 수행하여 큰 수의 곱셈을 빠르게 하기 위한 알고리즘이다.

카라추바 알고리즘은 분할정복 알고리즘을 통해 큰 수를 두 블록으로 쪼개서 계산하는 방법이다. 예시를 위해 두 큰 수 $a$와 $b$를 선언하자. 블록의 크기를 $T$라고 할 때, 두 수의 곱셈 $a \times b$는 아래와 같이 생각할 수 있다.

\[\begin{aligned} a \times b &= (a_1 \times 10^T + a_0) \times (b_1 \times 10^T + b_0) \\ &= a_1 b_1 \times 10^{2T} + (a_0 b_1 + a_1 b_0) \times 10^T + a_0 b_0 \\ &= z_0 \times 10^{2T} + z_1 \times 10^T + z_2 \end{aligned}\]

이 때 곱셈의 결과 계수 $z_0, z_1, z_2$를 계산하기 위해 곱셈을 총 4번 해야 한다는 것을 알 수 있다. 이 횟수를 줄이기 위해 아래와 같이 구하는 방식으로 변경한다.

• $z_0 = a_1 \times b_1$
• $z_2 = a_0 \times b_0$
• $z_1 = (a_0 \times b_1 + a_1 \times b_0) = (a_0 + a_1) \times (b_0 + b_1) - z_0 - z_2$

이렇게 하면 곱셈 연산 4번을 곱셈 연산 3번, 덧셈 연산 2번, 뺄셈 연산 2번으로 대신할 수 있다. 덧셈과 곱셈은 $O(N)$, 곱셈은 $O(N^2)$이므로 대체된 연산 방법이 더 효율적인 것을 알 수 있다.

시간복잡도 계산

그럼 이렇게 곱셈연산 횟수를 줄이면 시간복잡도가 어떻게 줄어들까? 연산하는 수의 자릿수가 $2^k$라고 해보자. 그리고 분할하는 블록의 자릿수를 항상 절반이라고 가정하자. 그리고 분할정복의 종료 시점을 자릿수가 $1$인 경우까지 진행한다고 가정해보자.

자릿수가 $N = 2^k$이고 매번 절반씩 분할하여 계산하므로, 재귀의 깊이는 $\log 2^k = k$가 된다. 그리고 재귀를 1번 진행할 때마다 곱셈 연산이 총 3번 발생하므로, 풀어야 할 부분문제는 대략 $3^k$번 발생할 것이다. 그렇다면 총 곱셈연산은 $O(3^k)$을 가지고, 이걸 다시 $N$에 대한 식으로 변경하면 $O(3^k) = O(3^{\log N}) = O(N^{\log 3})$의 복잡도를 가진다고 계산할 수 있다. $\log_2 {3} \approx 1.58$이므로 $O(N^2)$의 곱셈연산을 $O(N^{1.58})$ 정도로 낮출 수 있게 된다. 별로 차이가 나지 않는다고 생각할 수도 있지만, $N$이 2배 증가할 때마다 $O(N^2)$은 4배씩, $O(N^{1.58})$은 3배씩 증가하는 것이므로 $N$이 커지면 커질수록 연산 횟수에서 매우 큰 차이를 보인다. 아래 표는 그 값을 직접 계산해본 결과이다.

$N$	$O(N^2)$	$O(N^{\log 3})$
$16$	$256$	$81.00$
$32$	$1\,024$	$243.03$
$64$	$4\,096$	$729.11$
$128$	$16\,384$	$2\,187.39$
$256$	$65\,536$	$6\,562.36$
$512$	$262\,144$	$19\,687.60$
$1\,000$	$1\,000\,000$	$56\,885.29$
$5\,000$	$25\,000\,000$	$729\,234.91$
$10\,000$	$100\,000\,000$	$2\,187\,761.62$
$100\,000$	$10\,000\,000\,000$	$84\,139\,514.16$
$1\,000\,000$	$1\,000\,000\,000\,000$	$3\,235\,936\,569.29$

$N$이 커지면 커질수록 연산 횟수가 매우 큰 폭으로 줄어듦을 볼 수 있다. 작은 수보다는 큰 수의 곱셈을 구현할 때 시간효율적인 알고리즘이라는 것을 알 수 있다. 다만 $N$이 작을 때는 효율을 그렇게 볼 수 없다. 그래서 $N$이 작을 때는 기존의 $O(N^2)$의 방법을 채택하는 구현도 있다.

소스코드

// Karatsuba 알고리즘 (정수 버전)
// a, b는 양의 정수라고 가정 (절댓값의 곱)
long long karatsuba(long long x, long long y) {
    // 임계값: 너무 작으면 그냥 곱하기 (직접 곱셈이 더 빠름)
    if (x < THRESHOLD || y < THRESHOLD) {
        return x * y;
    }

    // 자릿수 계산
    int n = fmax(log10(x) + 1, log10(y) + 1);
    int m = n / 2;
    long long power = pow(10, m);

    // 하위 / 상위 분리
    long long x_high = x / power;
    long long x_low  = x % power;
    long long y_high = y / power;
    long long y_low  = y % power;

    // 재귀 호출
    long long z0 = karatsuba(x_low, y_low);
    long long z2 = karatsuba(x_high, y_high);
    long long z1 = karatsuba(x_low + x_high, y_low + y_high) - z0 - z2;

    // 결과 결합
    return z2 * (long long)pow(10, 2 * m) + z1 * power + z0;
}