Karatsuba Multiplication

1. 문제 정의

입력 : 두개의 n자리 양수 x, y

출력 : x y 의 곱

2. Grade-School Algorithm

5678 * 1234 계산 시 다음과 같이 계산

5678 * 4 + (5678 * 3) * 10 + (5678 * 2) * 100 + (5678 * 1) * 1000

복잡도는 O(n²)

-> 너무 느리다

3. Improving

3.1. Divide and conquer

Divide and conquer란?

큰 문제를 더 작고 쉬운 문제들의 모음으로 쪼개어 풀어내는 것

3.2. Integer Multiplication에 적용

1234 = 12 * 100 + 34

1234 * 5678
= (12 * 100 + 34) (56 * 100 + 78)
= (12 * 56)10000 + (34 * 56 + 12 * 78)100 + (34 * 78)

위와 같이 하나의 4자리 곱셈 문제는 4개의 2자리 곱셈 문제로 쪼개낼 수 있다.

recursive하게 위와 같이 쪼개내 1자리 곱셈 문제로까지 쪼개낸다.

 

n size의 문제 1개가 n/2 size의 문제 4개로 쪼개진다.

이것을 문제의 크기가 1이 될 때 까지 반복하면,

1 size의 문제 n²개가 된다.

 

Pseudo Code

Multiply(x, y):
    if n == 1:
        return xy;
    x = a * 10^(n/2) + b
    y = c * 10^(n/2) + d
    
    # recursively compute ac, ad, bc, bd
    ac = Multiply(a,c), etc
    
    xy = ac*10^n + (ad + bc)*10^(n/2) + bd

 

여기까지 결국 Divide and Conquer을 적용해도 복잡도는 O(n²)인 것처럼 보이나,

이를 더 개선해낸 것이 Karatsuba Multiplication이다.

3.3 Karatsuba Multiplication

ac*10^n + (ad + bc)*10^(n/2) + bd

빨간 부분을 (a + b)(c + d) - ac - ad로 대치하면

4개의 식을 3개로 줄일 수 있다.

Multiply(x, y):
    if n == 1:
        return xy;
    x = a * 10^(n/2) + b
    y = c * 10^(n/2) + d
    
    ac = Multiply(a, c)
    bd = Multiply(b, d)
    z = Multiply(a+b, c+d)
    
    xy = ac*10^n + (z - ac - bd)*10^(n/2) + bd

따라서 기존의 크기 1의 문제 수 4^(log2 n) 에서 3^(log2 n) 으로 n^(log2 3) ≒ n^(1.6)로 줄어들게 된다.

 

결론적으로 O(n^2)에서 O(n^1.6)정도로 성능이 증가한다.