카라추바 곱셈 (Karatsuba Multiplication)

큰 수 두 개를 곱할 때 필요한 "작은 곱셈"을 4번에서 3번으로 — 분할 정복으로 O(n²)를 O(n^1.585)로

한 줄 요약. 초등학교에서 배우는 세로셈 곱셈은 자릿수가 n이면 곱셈을 약 n²번 한다. 1960년, 23살이던 아나톨리 카라추바는 "곱셈은 절대 n²보다 빠를 수 없다"던 콜모고로프의 추측을 일주일 만에 반증했다. 핵심은 딱 하나 — 두 자리 곱을 4번이 아니라 3번만 하고, 이걸 재귀적으로 반복하는 것이다.

1. 세로셈은 왜 n²인가

1234 × 5678 을 손으로 계산하면, 아래 수의 각 자리(4개)를 위 수의 각 자리(4개)에 전부 곱한다 → 4 × 4 = 16번의 한 자리 곱셈. 자릿수가 n이면 n²번. n이 커질수록 급격히 느려진다.

2. 3번의 곱셈으로 줄이는 항등식

n자리 수 x, y를 절반 지점 m 에서 자른다 (B는 진법, 10진수면 B=10):

    x = a·Bm + b    
    y = c·Bm + d

    x·y = ac·B2m + (ad + bc)·Bm + bd

순진하게 하면 ac, ad, bc, bd 4번의 곱이 필요하다. 그런데 중간항 ad + bc 는 이렇게 구할 수 있다:

    z1 = (a + b)(c + d) = ac + ad + bc + bd

    ad + bc = z1 − ac − bd

즉 ac, bd, (a+b)(c+d) — 곱셈 3번과 덧셈/뺄셈 몇 번이면 끝. 곱셈은 재귀적으로 다시 카라추바로 처리한다. 점화식 T(n) = 3·T(n/2) + O(n) → T(n) = O(n^log₂3) ≈ O(n^1.585).

3. 한 단계 분할 해보기

x y

4. 재귀 호출 트리 — 전체 곱셈 추적

아래는 카라추바가 실제로 만드는 재귀 호출 트리다. 각 노드는 한 번의 곱셈 x × y, 한 자리 수끼리 만나면 잎(leaf)이 되어 실제 한 자리 곱셈 1회로 계산된다. 잎의 개수 = 실제로 수행한 기본 곱셈 횟수.

x y

5. 세로셈 vs 카라추바 — 곱셈 횟수 증가

자릿수 n에 대해 필요한 한 자리 곱셈 횟수. n²과 n^1.585은 처음엔 비슷하지만, n이 커지면 격차가 폭발적으로 벌어진다. (예: n = 1024 → 세로셈 약 100만, 카라추바 약 6만)

자릿수 n	세로셈 n²	카라추바 ≈ n^1.585	배율

6. 파이썬 구현

def karatsuba(x, y):
    # 한 자리(작은 수)면 그냥 곱한다 — 재귀의 바닥
    if x < 10 or y < 10:
        return x * y

    n = max(len(str(x)), len(str(y)))
    m = n // 2
    B = 10 ** m

    a, b = divmod(x, B)   # x = a·B + b
    c, d = divmod(y, B)   # y = c·B + d

    z2 = karatsuba(a, c)          # 곱셈 1
    z0 = karatsuba(b, d)          # 곱셈 2
    z1 = karatsuba(a + b, c + d)  # 곱셈 3

    mid = z1 - z2 - z0            # ad + bc
    return z2 * B*B + mid * B + z0

7. 정리

	세로셈 (Long Multiplication)	카라추바
부분 곱 개수	4 (a,b,c,d 전조합)	3
시간 복잡도	O(n²)	O(n^1.585)
덧셈/자리 이동	적음	더 많음 (오버헤드)
유리한 구간	작은 수 (~수십 자리)	큰 수 (수백 자리~)
더 빠른 방법	Toom-Cook (3-way 이상), Schönhage–Strassen(FFT, O(n log n log log n)), Harvey–van der Hoeven O(n log n)

파이썬의 int, 자바 BigInteger, GMP 같은 큰 수 라이브러리는 수가 일정 크기를 넘으면 자동으로 세로셈 → 카라추바 → Toom-Cook → FFT 곱셈으로 전환한다. 알고리즘 하나가 도구 전체의 성능을 바꾼 사례.