Karatsuba 곱셈 알고리즘: 세 번의 재귀와 O(n^log₂3) 유도

Karatsuba 알고리즘의 핵심은 큰 정수 두 개를 반으로 나눈 뒤, 네 번 필요하던 부분 곱셈을 세 번만 수행하는 것이다. 균형 잡힌 n자리 정수 곱셈이라면 점화식은 T(n) = 3T(n/2) + O(n)이 되고, 시간 복잡도는 O(n^log₂3), 약 O(n^1.585)가 된다.

이 표기는 O(n^log3)이 아니다. 로그의 밑이 2라는 점과, 작은 입력에서는 일반 곱셈으로 전환해야 실제 구현이 과도하게 느려지지 않는다는 점을 함께 기억해야 한다.

네 번의 곱셈을 어떻게 세 번으로 줄일까

두 수를 같은 자릿수 기준으로 나눈다고 하자. B를 절반 자릿수에 해당하는 밑으로 두면 다음처럼 표현할 수 있다.

x = aB + b
y = cB + d

그대로 전개하면 ac, ad, bc, bd라는 네 번의 곱셈이 필요하다.

xy = acB² + (ad + bc)B + bd

Karatsuba는 가운데 항을 다음 식으로 구한다.

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

xy = z2B² + z1B + z0

예를 들어 1234 × 5678을 두 자리씩 나누면 B = 100, a = 12, b = 34, c = 56, d = 78이다.

z2 = 12 × 56 = 672
z0 = 34 × 78 = 2,652
z1 = 46 × 134 - 672 - 2,652 = 2,840

672 × 100² + 2,840 × 100 + 2,652 = 7,006,652

왜 O(n^log₂3)일까

입력을 절반 크기로 나눌 때 재귀 곱셈은 세 개 생긴다. 분할, 덧셈, 뺄셈, 결과 결합에는 자릿수에 비례하는 작업이 든다고 가정한다.

T(n) = 3T(n/2) + O(n)

마스터 정리를 적용하면 log₂3 ≈ 1.585이므로 T(n) = O(n^1.585)다. 학교식 곱셈의 O(n²)보다 점근적으로 빠르다.

다만 이 분석에는 전제가 있다.

• 두 피연산자의 크기가 대체로 비슷하다.
• 덧셈과 자릿수 분할을 O(n)에 처리한다.
• 충분히 작은 부분 문제는 일반 곱셈으로 끝낸다.
• n은 비트 수나 내부 limb 수처럼 일관된 크기 단위다.

10진 문자열 길이를 사용하는 아래 코드는 원리를 보여 주기 위한 Python 예제다. CPython의 큰 정수는 10진수 한 자리씩 저장하지 않으므로, 이 코드의 임계값을 CPython 내부 임계값과 같다고 보면 안 된다. 호출마다 수행하는 문자열 변환과 객체 할당 비용도 있어 이 코드의 실제 실행 시간을 점화식과 그대로 동일시할 수 없다.

음수와 불균형한 길이까지 처리한 Python 예제

def karatsuba(x: int, y: int, cutoff_digits: int = 32) -> int:
    if cutoff_digits < 1:
        raise ValueError("cutoff_digits must be at least 1")

    if x == 0 or y == 0:
        return 0

    sign = -1 if (x < 0) ^ (y < 0) else 1
    result = _karatsuba_nonnegative(
        abs(x), abs(y), cutoff_digits
    )
    return sign * result


def _karatsuba_nonnegative(
    x: int,
    y: int,
    cutoff_digits: int,
) -> int:
    x_digits = len(str(x))
    y_digits = len(str(y))
    smaller = min(x_digits, y_digits)
    larger = max(x_digits, y_digits)

    # 작은 입력과 지나치게 불균형한 입력은 내장 곱셈으로 끝낸다.
    if smaller <= cutoff_digits or larger >= 2 * smaller:
        return x * y

    half = larger // 2
    base = 10**half

    x_high, x_low = divmod(x, base)
    y_high, y_low = divmod(y, base)

    z0 = _karatsuba_nonnegative(
        x_low, y_low, cutoff_digits
    )
    z2 = _karatsuba_nonnegative(
        x_high, y_high, cutoff_digits
    )
    z1 = _karatsuba_nonnegative(
        x_low + x_high,
        y_low + y_high,
        cutoff_digits,
    ) - z0 - z2

    return z2 * base * base + z1 * base + z0

부호는 재귀 바깥에서 한 번만 처리한다. 0은 즉시 반환한다. 두 수의 길이가 크게 다르면 교육용 재귀를 계속하기보다 Python 내장 곱셈으로 돌아간다. 실무 라이브러리는 단순 fallback보다 정교한 불균형 곱셈 경로를 둘 수 있다. CPython 3.14.6 소스도 별도의 k_lopsided_mul 경로와 내부 자릿수 기준 cutoff를 사용한다.

cutoff_digits=32는 설명을 위한 값일 뿐 최적값이 아니다. 언어, CPU, 정수 표현, 메모리 할당 비용에 따라 교차점이 달라지므로 실제 적용 전에는 벤치마크해야 한다. Python에서는 이미 최적화된 x * y가 이 순수 Python 코드보다 대체로 빠르다.

어떤 입력을 검증해야 할까

코드는 다음 경계를 포함해 내장 곱셈과 결과를 비교하는 것이 좋다.

test_cases = [
    (0, 0),
    (0, 987654321),
    (-12, 34),
    (12345678, 87654321),
    (10**80 + 7, -(10**9 + 3)),
]

for x, y in test_cases:
    assert karatsuba(x, y, cutoff_digits=8) == x * y

작성한 구현은 0, 음수, 자릿수가 크게 다른 수를 포함한 1,005개 정수 조합에서 Python 내장 곱셈과 같은 결과를 확인했다. 이 검증은 정확성을 확인하는 것이지, 성능 우위를 증명하는 벤치마크는 아니다.

참고 자료

• Karatsuba·Ofman 원 논문: Multiplication of many-digital numbers by automatic computers
• CPython 3.14.6 longobject.c