Karatsuba Multiplication

초등학교 곱셈법의 벽

두 개의 $n$자리 정수 $x$와 $y$를 곱한다고 하자. 초등학교에서 배우는 긴 곱셈은 $y$의 각 자리를 $x$와 곱한 뒤 자리를 맞춰 더하는 방식으로, 총 $n^2$회의 한 자리 곱셈이 필요하다. 점근적으로 $\Theta(n^2)$이다.

1952년 콜모고로프는 세미나에서 "$n$자리 정수 곱셈은 $\Omega(n^2)$보다 빠를 수 없다"고 추측했다¹. 그러나 1960년 카라추바가 세미나에 참석해 일주일 만에 반례를 구성했다. 핵심은 분할 정복과 대수적 항등식이었다.

카라추바의 항등식

$n$자리 정수를 반으로 쪼개자. $m = \lceil n/2 \rceil$이라 하면

$x = x_1 \cdot 10^m + x_0, \quad y = y_1 \cdot 10^m + y_0$

으로 쓸 수 있다. $x_1, y_1$은 상위 $m$자리, $x_0, y_0$은 하위 $m$자리다. 두 수의 곱을 전개하면

$x \cdot y = x_1 y_1 \cdot 10^{2m} + (x_1 y_0 + x_0 y_1) \cdot 10^m + x_0 y_0$

이다. 여기까지는 네 번의 $m$자리 곱셈 $x_1 y_1$, $x_1 y_0$, $x_0 y_1$, $x_0 y_0$이 필요하다. 이대로라면 재귀식은 $T(n) = 4T(n/2) + \Theta(n)$이 되고 복잡도는 여전히 $\Theta(n^2)$이다.

카라추바의 통찰은 중간 항 $x_1 y_0 + x_0 y_1$을 세 번째 곱셈 하나만으로 얻어 내는 것이었다. 다음 항등식을 보자.

$(x_1 + x_0)(y_1 + y_0) = x_1 y_1 + x_1 y_0 + x_0 y_1 + x_0 y_0$

좌변에서 $x_1 y_1$과 $x_0 y_0$을 빼면 중간 항만 남는다.

$x_1 y_0 + x_0 y_1 = (x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0$

따라서 세 번의 $m$자리 곱셈 $P_1 = x_1 y_1$, $P_2 = x_0 y_0$, $P_3 = (x_1 + x_0)(y_1 + y_0)$만 계산하면 된다. 최종 결과는

$x \cdot y = P_1 \cdot 10^{2m} + (P_3 - P_1 - P_2) \cdot 10^m + P_2$

이다. 덧셈과 뺄셈은 $\Theta(n)$의 비용밖에 들지 않으므로, 곱셈 횟수를 4회에서 3회로 줄인 것이 곧바로 복잡도 개선으로 이어진다.

점화식과 복잡도

$n$자리 곱셈을 세 번의 $n/2$자리 곱셈과 $\Theta(n)$의 덧·뺄셈으로 해결하므로, 수행 시간은 다음 점화식을 따른다.

$T(n) = 3T\!\left(\frac{n}{2}\right) + \Theta(n)$

마스터 정리의 단순 형태에 $a = 3$, $b = 2$, $d = 1$을 대입하면 $b^d = 2 < 3 = a$이므로 "잎이 지배하는 경우"에 해당한다. 따라서

$T(n) = \Theta\!\left(n^{\log_2 3}\right) \approx \Theta\!\left(n^{1.585}\right)$

이다. $n = 1024$에서 긴 곱셈은 약 백만 번의 한 자리 곱셈이 필요하지만, 카라추바는 약 $1024^{1.585} \approx 65{,}000$번으로 끝난다. 차이는 $n$이 커질수록 벌어진다.

의사코드

function KARATSUBA(x, y) returns x · y
    if x < 10 or y < 10 then
        return x · y                    ▷ 기저 조건 — 한 자리 곱은 직접 계산

    n ← max(digits(x), digits(y))
    m ← ⌈n / 2⌉

    (x1, x0) ← (x / 10^m,  x mod 10^m)   ▷ 상위·하위 m자리로 분할
    (y1, y0) ← (y / 10^m,  y mod 10^m)

    P1 ← KARATSUBA(x1, y1)               ▷ 재귀 호출 3번
    P2 ← KARATSUBA(x0, y0)
    P3 ← KARATSUBA(x1 + x0, y1 + y0)

    return P1 · 10^(2m) + (P3 - P1 - P2) · 10^m + P2

구현 시 고려 사항

기저 조건의 임계값

실전 구현에서는 재귀를 끝까지 내려가지 않는다. $n$이 어느 크기 이하로 작아지면 재귀 호출과 덧·뺄셈의 상수 오버헤드가 곱셈 절감분을 상회하므로, 일정 크기 이하에서는 긴 곱셈으로 되돌아간다. GMP 라이브러리는 이 임계값을 컴파일 시점에 플랫폼별로 튜닝한다².

비트 단위 분할

실제 코드에서는 10진수가 아닌 2진수(또는 $2^{32}$ 진수)로 분할한다. 진법은 복잡도에 영향을 주지 않고, 시프트 연산으로 $10^m$ 곱셈을 대체할 수 있어 구현이 단순해진다.

$P_3$의 오버플로

$(x_1 + x_0)(y_1 + y_0)$에서 두 합은 각각 $m+1$비트가 될 수 있으므로, $P_3$의 재귀 호출은 $m+1$ 비트로 이루어진다. 이 때문에 구현에서는 한 비트 여유를 둔 버퍼를 사용한다.

역사적 의의와 그 이후

카라추바의 발견은 단순히 상수를 개선한 것이 아니라 복잡도의 지수를 낮춘 사건이었다. 이 아이디어는 이후 여러 방향으로 확장된다. Toom-Cook 알고리즘은 수를 $k$개의 조각으로 쪼개 $2k-1$번의 곱셈으로 해결한다. Toom-3은 $\Theta(n^{\log_3 5}) \approx \Theta(n^{1.465})$으로, Karatsuba(Toom-2)의 일반화다. Schönhage-Strassen 알고리즘(1971)은 고속 푸리에 변환Fast Fourier Transform을 이용해 $\Theta(n \log n \log \log n)$을 달성했다. Harvey-van der Hoeven 알고리즘(2019)은 마침내 $\Theta(n \log n)$을 달성하여 Schönhage가 1971년에 제시한 하한 추측을 만족시켰다³.

그러나 이 모든 후속 알고리즘은 매우 큰 $n$에서만 카라추바의 알고리즘을 능가하며, 중간 규모(수백~수만 자리)의 정수 곱셈에는 카라추바가 여전히 실전 최적이다. 60년이 넘은 알고리즘이 실무에서 살아남아 있다.

---

출처

• Karatsuba, A. and Ofman, Y. (1962) 'Multiplication of multidigit numbers on automata', Soviet Physics Doklady, 7, pp. 595–596. (1960년 발견, 1962년 공식 출판)
• Knuth, D. E. (1998) The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3rd edn. Reading, MA: Addison-Wesley, §4.3.3.
• Harvey, D. and van der Hoeven, J. (2021) 'Integer multiplication in time O(n log n)', Annals of Mathematics, 193(2), pp. 563–617.

Footnotes

1. Kolmogorov는 "복잡도 하한" 개념의 초기 제창자 중 한 명이었고, 정수 곱셈은 $\Omega(n^2)$이라는 직관적 추측을 가졌다. Karatsuba가 이 추측을 반례로 뒤엎은 뒤, Kolmogorov는 세미나를 종료하고 Karatsuba의 이름으로 논문을 제출하게 했다. ↩

2. GMP(GNU Multiple Precision Arithmetic Library)는 MUL_TOOM22_THRESHOLD라는 상수를 통해 Karatsuba로 전환할 자릿수 경계를 플랫폼별로 저장한다. 대개 수십~수백 자리 수준이다. ↩

3. Harvey와 van der Hoeven의 결과는 "언젠가는 달성될 것"이라 여겨졌지만 60년 가까이 열린 문제였다. 이들의 알고리즘은 이론적으로 최적이나 상수 인자가 천문학적이어서 실용적이지는 않다. ↩