카라츠바 알고리즘 — n자리 곱셈은 n²보다 빠를 수 있다

행렬 곱셈에서 곱을 8번에서 7번으로 줄이자 지수가 $3$ 에서 $2.807$ 로 내려갔다. 같은 요령이 훨씬 단순한 무대에도 있다. 큰 수 두 개를 곱하는 문제다. 1960년 카라츠바는 곱을 4번에서 3번으로 줄여, “곱셈은 $n^2$ 보다 빠를 수 없다”는 당대의 추측을 무너뜨렸다.

이 포스트에서 다루는 내용

$n$ 자리 곱셈이 왜 $\Theta(n^2)$ 인가 — 무엇을 “곱셈 한 번”으로 세는가
수를 반으로 나눈 분할 정복 — 왜 $T(n)=4T(n/2)$ 라서 여전히 $n^2$ 인가
카라츠바: $(x_1+x_2)(y_1+y_2)$ 하나로 곱을 3번으로 줄이기
복잡도 $T(n)=3T(n/2)+\Theta(n)=\Theta(n^{\log_2 3})\approx\Theta(n^{1.585})$
$n$ 비트와 $n$ 자리가 같은 문제인 이유
Strassen과의 구조적 대응, 그 뒤의 기록

무엇을 “곱셈 한 번”으로 세는가

곱셈 하나가 상수 시간에 끝난다는 가정은 수가 하드웨어 레지스터에 들어갈 때만 참이다. RSA 키나 다중 정밀도 산술에서 다루는 수는 수천 비트다. 이런 수에서 비용의 단위는 한 자리 × 한 자리 곱셈이다.

$n$ 자리 수 $x$ , $y$ 를 초등학교식으로 곱한다. $y$ 의 자리마다 $x$ 의 $n$ 자리를 전부 훑어 부분곱을 만들고, 자리를 밀어 모두 더한다. 자리 곱셈은 $n \times n$ 번이다.

T_{\text{naive}}(n) = \Theta(n^2)

$n$ 자리 두 수를 더하는 비용은 $\Theta(n)$ 이라 곱셈보다 싸다. 앞으로 자리 곱셈 횟수만 센다.

질문은 하나다. 이보다 빠르게 할 수 있는가?

일주일 만에 무너진 추측

1956년 콜모고로프는 $n$ 자리 곱셈에 $\Omega(n^2)$ 이 필요하다고 추측했다. 1960년 자신의 세미나에서 이 추측을 소개했고, 당시 23살이던 카라츠바가 일주일 만에 반례를 가져왔다. 콜모고로프는 그 자리에서 세미나를 접었다.

반으로 잘라 보기

분할 정복의 문법을 그대로 가져온다. 큰 곱을 작은 곱들로 쪼갤 수 있을까? 수를 반으로 자르면 된다.

$n$ 이 짝수라 하고 $m = n/2$ 로 둔다. 10진법에서 $x$ 를 위쪽 $m$ 자리 $x_1$ 과 아래쪽 $m$ 자리 $x_2$ 로 가르면

x = x_1 \cdot 10^{m} + x_2, \qquad y = y_1 \cdot 10^{m} + y_2

이다. 곱을 전개한다.

xy = x_1y_1 \cdot 10^{2m} + (x_1y_2 + x_2y_1)\cdot 10^{m} + x_2y_2

n자리 수를 위쪽 m자리와 아래쪽 m자리로 가르면, 곱은 서로 다른 자리에 놓이는 세 조각으로 분해된다. 순진하게 계산하면 절반 크기의 곱이 네 번 필요하다.

$10^k$ 를 곱하는 연산은 자리를 $k$ 칸 미는 일이라 $\Theta(n)$ 이고, 자리 곱셈으로 세지 않는다. 진짜 곱셈은 $x_1y_1,\ x_1y_2,\ x_2y_1,\ x_2y_2$ 의 네 번이다. 각각 $m = n/2$ 자리끼리의 곱, 즉 절반 크기의 같은 문제다.

가운데 항의 10^m을 빠뜨리기 쉽다

세 조각은 각각 다른 자리에서 시작한다. $x_1y_1$ 은 $2m$ 칸 위, 가운데 합은 $m$ 칸 위, $x_2y_2$ 는 제자리다. 이 자리 이동이 있어야 세 조각이 저마다 올바른 자릿수에 맞춰지고, 겹치는 자릿수끼리 더해져 하나의 수로 합쳐진다. 가운데 항을 그냥 더하면 자릿수가 어긋나 전혀 다른 값이 나온다.

점화식은 다음과 같다.

T(n) = 4\,T\!\left(\tfrac{n}{2}\right) + \Theta(n)

$\Theta(n)$ 은 자리를 밀고 네 조각을 더하는 비용이다. 덧셈 항을 잠시 무시하고 재귀 항만 따라가면

T(n) = 4\,T\!\left(\tfrac{n}{2}\right) = 4^2\,T\!\left(\tfrac{n}{4}\right) = \cdots = 4^{\log_2 n}\,T(1) = n^{\log_2 4} = n^2

이다. 여기에 $\Theta(n)$ 을 더해도 $n^2$ 이 압도하므로 결과는 그대로 $\Theta(n^2)$ 이다.

나누기만으로는 못 이긴다

행렬을 2×2 블록으로 나눴을 때와 같은 상황이다. 그쪽은 블록 곱이 8번이라 지수가 $\log_2 8 = 3$ 이었고, 여기서는 자리 곱셈이 4번이라 지수가 $\log_2 4 = 2$ 다. 재귀 호출과 임시 메모리 오버헤드까지 붙으니 실제로는 초등학교식보다 느리다. 지수는 재귀 호출 횟수 $a$ 와 크기 축소 비율 $b$ 로 $\log_b a$ 가 되므로, 얼마나 잘게 나누느냐가 아니라 절반 크기 호출을 몇 번 하느냐가 지수를 정한다.

넘어야 할 벽이 분명해진다. 절반 크기의 곱을 네 번보다 적게 하면 된다.

카라츠바: 곱을 3번으로

전개식을 다시 본다.

xy = x_1y_1 \cdot 10^{2m} + (x_1y_2 + x_2y_1)\cdot 10^{m} + x_2y_2

필요한 값은 셋이다. $x_1y_1$ , $x_2y_2$ , 그리고 가운데의 합 $x_1y_2 + x_2y_1$ . 세 번째는 합일 뿐이므로 $x_1y_2$ 와 $x_2y_1$ 을 따로 알 필요가 없다. 합만 손에 넣으면 된다.

(x_1+x_2)(y_1+y_2) = x_1y_1 + x_1y_2 + x_2y_1 + x_2y_2

우변에 원하는 합이 통째로 들어 있다. 군더더기로 붙은 $x_1y_1$ 과 $x_2y_2$ 는 어차피 계산해야 하는 값이니, 빼내면 그만이다.

정리 1곱 3번으로 충분하다

P_1 = x_1y_1, \qquad P_2 = x_2y_2, \qquad P_3 = (x_1+x_2)(y_1+y_2)

로 두면

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

이다. 곱셈은 $P_1, P_2, P_3$ 을 만드는 세 번뿐이다.

증명. $P_3$ 을 전개한다.

P_3 = (x_1+x_2)(y_1+y_2) = x_1y_1 + x_1y_2 + x_2y_1 + x_2y_2

여기서 $P_1 = x_1y_1$ 과 $P_2 = x_2y_2$ 를 빼면

P_3 - P_1 - P_2 = x_1y_2 + x_2y_1

이 되어 전개식 가운데 항의 계수와 일치한다. $10^{2m}$ 자리의 계수는 $P_1 = x_1y_1$ , 상수 자리의 계수는 $P_2 = x_2y_2$ 로 정의 그대로다. 세 자리가 모두 맞으므로

P_1 \cdot 10^{2m} + (P_3-P_1-P_2)\cdot 10^{m} + P_2 = x_1y_1\cdot 10^{2m} + (x_1y_2+x_2y_1)\cdot 10^{m} + x_2y_2 = xy

이다. $P_1, P_2, P_3$ 을 만드는 데 곱셈은 세 번이고, 나머지는 덧셈·뺄셈과 자리 밀기뿐이다. ∎

하나의 곱을 두 출력이 나눠 쓴다

$P_3$ 한 번의 곱이 $x_1y_2$ 와 $x_2y_1$ 을 동시에 담는다. 이미 가진 $P_1$ , $P_2$ 로 군더더기를 걷어내면 원하는 합만 남는다. Strassen에서 $P_5$ 가 $C_{11}$ 과 $C_{22}$ 양쪽에 쓰이던 방식, 가우스가 복소수 곱을 4번에서 3번으로 줄인 요령과 같은 구조다. 곱 하나를 덧셈 몇 번과 맞바꾸는 거래다.

복잡도

절반 크기의 곱이 세 번이므로 점화식은 다음과 같다.

T(n) = 3\,T\!\left(\tfrac{n}{2}\right) + \Theta(n)

$\Theta(n)$ 은 $x_1+x_2$ 같은 덧셈, $P_3-P_1-P_2$ 뺄셈, 자리 밀기와 최종 합산 비용이다. 재귀 항을 펼치면

T(n) = 3\,T\!\left(\tfrac{n}{2}\right) = 3^2\,T\!\left(\tfrac{n}{4}\right) = \cdots = 3^{\log_2 n}\,T(1) = n^{\log_2 3}

이고, $\log_2 3 > 1$ 이므로 덧셈의 $\Theta(n)$ 은 흡수된다.

T_{\text{Karatsuba}}(n) = \Theta\!\left(n^{\log_2 3}\right) = \Theta\!\left(n^{1.585\ldots}\right)

지수가 log₂3인 이유

$4^{\log_2 n} = n^{\log_2 4} = n^2$ 이었던 것과 똑같이, $3^{\log_2 n} = n^{\log_2 3}$ 이다. $\log_2 3 = 1.5849\ldots$ 이고 $2^{1.585}\approx 3$ 으로 검산된다. $n = 1024$ 자리라면 나이브는 자리 곱셈 약 $105$ 만 번, 카라츠바는 $3^{10} = 59049$ 번으로 열여덟 배 가까이 차이가 난다.

자릿수가 어긋나는 경우

$x_1+x_2$ 는 $m$ 자리를 넘어 $m+1$ 자리가 될 수 있다. 그래서 $P_3$ 의 재귀 호출은 엄밀히 $m$ 자리가 아니라 $m+1$ 자리 곱이다. 아래 의사코드도 합을 그대로 넘긴다.

점화식을 그 사실에 맞춰 다시 쓰면 이렇다.

T(n) \;\le\; 2\,T\!\left(\left\lceil \tfrac{n}{2} \right\rceil\right) + T\!\left(\left\lceil \tfrac{n}{2} \right\rceil + 1\right) + \Theta(n)

지수는 그대로 $\log_2 3$ 이다. $T$ 가 증가함수이므로 세 항을 모두 $T(\lceil n/2 \rceil + 1)$ 로 올려 잡아도 되고, $u = n + 2$ 로 두면 $\lceil n/2 \rceil + 1 \le \lceil u/2 \rceil$ 이라 $S(u) = T(u-2)$ 가 $S(u) \le 3\,S(\lceil u/2 \rceil) + \Theta(u)$ 를 만족한다. 원래 점화식과 같은 꼴이므로 $S(u) = O(u^{\log_2 3})$ 이고, 되돌리면 $T(n) = O(n^{\log_2 3})$ 이다. 한 자리가 더 붙는 것은 지수를 바꾸지 못한다.

넘친 올림 자리를 따로 떼어 내 재귀에 넘기는 값을 $m$ 자리로 맞추는 구현도 있다. 그때는 떼어 낸 자리를 $\Theta(n)$ 짜리 보정 덧셈으로 처리하므로 점화식이 정확히 $3\,T(n/2) + \Theta(n)$ 이 된다. 어느 쪽이든 결론은 같다.

$n$ 이 홀수이거나 $x$ 와 $y$ 의 길이가 다를 때는 위쪽을 $0$ 으로 채워 맞춘다.

의사코드

// x, y: n자리(또는 n비트) 큰 수.  << k 는 자리를 k칸 미는 연산.
BigInt karatsuba(const BigInt& x, const BigInt& y) {
    int n = max(x.digits(), y.digits());
    if (n <= THRESHOLD) return schoolbook(x, y);   // 기저: 작으면 초등학교식

    int m = n / 2;

    // 1. 위쪽 / 아래쪽 m자리로 분할
    BigInt x1 = x >> m,  x2 = x.low(m);   // x = x1 * BASE^m + x2
    BigInt y1 = y >> m,  y2 = y.low(m);

    // 2. 곱은 딱 3번 — P1·P2는 절반 크기, P3는 합이라 최대 m+1자리
    BigInt P1 = karatsuba(x1, y1);
    BigInt P2 = karatsuba(x2, y2);
    BigInt P3 = karatsuba(x1 + x2, y1 + y2);   // 합이라 최대 m+1자리 — 위 점화식 참고

    // 3. 자리를 밀어 조립 — 덧셈·뺄셈뿐
    BigInt mid = P3 - P1 - P2;
    return (P1 << 2*m) + (mid << m) + P2;
}

곱셈이 일어나는 곳은 karatsuba 재귀 호출 세 줄뿐이다. 나머지 덧셈·뺄셈과 자리 밀기는 $\Theta(n)$ 으로 점화식의 $\Theta(n)$ 항에 흡수된다. 기저를 $n=1$ 이 아니라 THRESHOLD 로 잡는 이유는 아래 “현실에서는”에서 다룬다.

n비트인가, n자리인가

유도에서 밑 $10$ 이 쓰인 자리는 분할과 조립 두 곳뿐이다. $2$ 로 바꿔도 논증이 한 글자도 달라지지 않는다.

x = x_1 \cdot 2^{m} + x_2,\qquad y = y_1 \cdot 2^{m} + y_2

xy = x_1y_1 \cdot 2^{2m} + (x_1y_2 + x_2y_1)\cdot 2^{m} + x_2y_2

밑이 무엇이든 재귀 가지는 셋, 조립 비용은 $\Theta(n)$ 이다. $n$ 비트 곱셈도 $\Theta(n^{\log_2 3})$ 이다. 밑은 상수라 지수에 들어가지 않는다. $n$ 비트 수는 십진으로 약 $0.301\,n$ 자리이므로, 두 표기는 상수 배로 서로 환산될 뿐이다.

실제 구현은 밑을 $2^{32}$ 나 $2^{64}$ 로 잡는다. 하드웨어 곱셈기가 한 번에 처리하는 크기를 한 “자리”로 삼으면, 같은 수를 표현하는 자리 수 $n$ 이 그만큼 줄어든다.

Strassen과 나란히 놓기

두 알고리즘은 같은 문장의 서로 다른 사례다.

	카라츠바 (1960)	Strassen (1969)
대상	$n$ 자리 정수 곱	$N\times N$ 행렬 곱
나이브	$\Theta(n^2)$	$\Theta(N^3)$
순진한 분할	$4T(n/2)$ → $n^2$	$8T(N/2)$ → $N^3$
줄인 뒤	$3T(n/2)$	$7T(N/2)$
지수	$\log_2 3 \approx 1.585$	$\log_2 7 \approx 2.807$
조립 비용	$\Theta(n)$	$\Theta(N^2)$

두 경우 모두 곱셈 하나를 덧셈 몇 번과 맞바꿨고, 그 덧셈이 재귀 항에 흡수되어 이득만 남았다. 지수를 정한 것은 오직 재귀 가지의 수다.

어느 쪽이 먼저인가

카라츠바가 9년 앞선다. 시간 순서로 보면 Strassen이 카라츠바의 발상을 행렬로 끌어올린 셈이다. 두 결과 모두 “이 문제는 나이브가 최선”이라는 널리 퍼진 직관이 증명 없는 추측이었음을 드러냈다.

그 뒤의 기록들

1963년, Toom–Cook: 반이 아니라 세 조각 이상으로 나눈다. 세 조각이면 곱 9번을 5번으로 줄여 $\Theta(n^{\log_3 5}) \approx \Theta(n^{1.465})$ . 조각을 늘릴수록 지수는 $1$ 에 가까워지지만 숨은 상수가 커진다.
1971년, Schönhage–Strassen: 곱을 FFT로 옮겨 $O(n \log n \log\log n)$ . 다중 정밀도 라이브러리가 아주 큰 수에 실제로 쓰는 방법이다.
2019년, Harvey–van der Hoeven: $O(n \log n)$ . 오래 추정되던 목표에 도달했으나, 이득을 보려면 비현실적으로 큰 수가 필요한 갤럭틱 알고리즘이다.
확실한 하한은 $\Omega(n)$ 뿐이다(입력을 최소한 한 번씩은 읽어야 한다). 진짜 하한이 $n\log n$ 인지는 아직 열린 문제다.

현실에서는

카라츠바가 항상 이기지는 않는다. 재귀 호출, 임시 메모리 할당, 늘어난 덧셈이 오버헤드로 붙어 작은 수에서는 초등학교식이 빠르다. GMP 같은 다중 정밀도 라이브러리는 임계값(대략 수백~수천 비트) 아래에서 초등학교식을, 그 위에서 카라츠바를, 훨씬 큰 수에서 Toom–Cook과 FFT를 쓰도록 단계별로 전환한다. Strassen을 작은 행렬에 쓰지 않는 것과 같은 이야기다.

마치며

큰 수 곱셈의 벽 역시 얼마나 잘게 나누느냐가 아니라 절반 크기의 곱을 몇 번 하느냐에 있었다. 순진한 분할은 그 횟수가 $4$ 라 나이브와 같은 $n^2$ 에 갇혔고, 카라츠바는 $(x_1+x_2)(y_1+y_2)$ 하나를 끼워 넣어 $3$ 까지 줄이며 지수를 $\log_2 3 \approx 1.585$ 로 낮췄다. 9년 뒤 Strassen은 같은 요령을 행렬로 옮겨 $8$ 을 $7$ 로 줄인다. 분할 정복에서 재귀 가지의 수는 그만큼 무겁다.

행렬 곱셈 본편 → · Strassen의 7은 어디서 왔는가 →