카라츠바 곱셈

카라츠바 곱(Karatsuba Multiplication)은 대형 정수의 곱셈을 더 효율적으로 수행하는 분할 정복 알고리즘이다. 이 알고리즘은 일반적인 곱셈 방식(O(n²))보다 빠르게 계산할 수 있으며, O(n^log₂3) ≈ O(n^1.585) 의 시간 복잡도를 가진다.

1 개요

카라츠바 알고리즘은 큰 수의 곱셈을 더 작은 부분 문제로 나누고, 이를 재귀적으로 해결하여 전체 계산량을 줄인다. 기본적인 아이디어는 곱셈 연산을 단순한 덧셈과 시프트 연산으로 변환하는 것이다.

2 알고리즘 설명

두 개의 n자리 수 x와 y가 주어졌을 때, 이를 다음과 같이 분할한다.

• x = A × 10^m + B
• y = C × 10^m + D

여기서,

• A, C: 상위 m자리 숫자
• B, D: 하위 m자리 숫자
• m = n/2 (자리수를 절반으로 나눈다.)

이제 곱셈 x × y는 다음과 같이 변환된다.

• x × y = (A × 10^m + B) × (C × 10^m + D)
• x × y = A × C × 10^2m + (A × D + B × C) × 10^m + B × D

(A × D + B × C)의 직접적인 계산을 줄이기 위해 카라츠바 알고리즘은 다음과 같이 연산한다.

• M1 = A × C
• M2 = B × D
• M3 = (A + B) × (C + D)
• M4 = M3 - M1 - M2

최종 곱셈 결과는 다음과 같다.

• x × y = M1 × 10^2m + M4 × 10^m + M2

3 시간 복잡도

카라츠바 알고리즘의 재귀 관계식은 다음과 같다.

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

이를 마스터 정리를 사용하여 풀면:

• T(n) = O(n^lg₂3) ≈ O(n^1.585)

나이브 곱셈(O(n²))보다 빠르며, FFT 기반 곱셈(O(n log n))보다 느리다.

4 카라츠바 알고리즘 예시

예제: 12 × 34 계산 과정

단계	연산
A = 1, B = 2, C = 3, D = 4	12 = 1×10 + 2, 34 = 3×10 + 4
M1 = A × C	1 × 3 = 3
M2 = B × D	2 × 4 = 8
M3 = (A + B) × (C + D)	(1+2) × (3+4) = 3 × 7 = 21
M4 = M3 - M1 - M2	21 - 3 - 8 = 10
최종 결과	3 × 100 + 10 × 10 + 8 = 408

5 카라츠바 알고리즘의 장점과 한계

5.1 장점

• O(n²)보다 빠른 시간 복잡도를 가진다.
• 정수뿐만 아니라 다항식 곱셈에도 적용할 수 있다.
• 분할 정복을 사용하여 병렬 연산이 가능하다.

5.2 한계

• n이 작을 경우, 전통적인 곱셈보다 오버헤드가 크다.
• 재귀 호출이 많아 메모리 사용량이 증가할 수 있다.
• FFT 기반 알고리즘(O(n log n))보다 느리다.

6 같이 보기

• 분할 정복 알고리즘
• 빠른 푸리에 변환
• 스트라센 알고리즘
• 긴 정수 연산

7 참고 문헌

• Karatsuba, A. & Ofman, Y. (1962). "Multiplication of Multi-Digit Numbers on Automata".
• Wikipedia - Karatsuba Algorithm
• GeeksforGeeks - Karatsuba Algorithm