[알고리즘] 카라추바의 빠른 곱셈(Karatsuba)

123 × 456 = ?

평소에 일상적으로 계산하던 방법을 분석적으로 풀어써보면 이렇다.
우리는 평소 한 자리에 0부터 9까지의 숫자만 사용하는 십진법을 사용하기 때문에, 각 자리별로 십의 자리 수는 다음 칸으로 넘겨준다(예를 들어 10의 자리 27은 (20 + 7)이므로 100의 자리로 2를 넘겨준다).

 

(4 * 10000) + (13 * 1000) + (28 * 100) + (27 * 10) + (18 * 1)
= (5 * 10000) + (6 * 1000) + (0 * 100) + (8 * 10) + (8 * 1)
= 56088

 

최종적으로 값을 이렇게 계산해 낼 수있다.
456의 갯수만큼, 123의 각 원소(1, 2, 3)과 한 번씩 곱셈연산을 해야함을 알 수있다.
따라서 전통적인 방법으로는 만약 (n 자릿수) × (n 자릿수)의 상황에서는 n2 번의 곱셈을 수행해야 한다.

​

 

 

카라추바의 빠른 곱셈

카라추바(Karatsuba)는 분할정복을 이용해, 이러한 과정의 효율을 크게 개선할 수 있음을 보였다.

 

예를 들어,1234 × 5678 의 계산을 카라추바의 빠른 곱셈을 이용해보자.
1234 = 12 × 100 + 34,
5678 = 56 × 100 + 78로 나눌 수 있다.​

 

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

 

여기서 10의 거듭제곱의 계수를 z0, z1, z2로 놓는다.
z0 = 34 × 78
z1 = 12 × 78 + 34 × 56
z2 = 12 × 56​

 

z1은 다시 쓰면 다음과 같이 쓸 수 있다. 계산 결과가 같은지만 확인해보자.
z1 = (34 + 12) × (56 + 78) - z0 - z2

 

이제 z0, z1, z2를 이용하면, 단 3번의 곱셈으로 문제를 해결 할 수 있다!
각 곱셈에 대하여 재귀 호출을 할 것이므로, 3log n ( = nlog 3)의 효율로 문제를 해결할 수 있게 된다!
log 3 = 0.4 정도이므로 훨씬 좋은 효율을 보인다. 다만 코드의 길이 상 크기가 큰 곱셈에서만 더 빠른 실행을 보인다. ​이를 코드로 구현하면 다음과 같다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

int karatsuba(int num1, int num2) {
    // 한 자릿수가 되면 그냥 연산
	if (num1 < 10 || num2 < 10)
		return num1 * num2;
	
    // 숫자를 분할할 m을 둘 중 더 작은 자릿수의 절반으로 설정
	int m;
	m = min((int)(log10(num1) + 1), (int)(log10(num2) + 1));
	m /= 2;

    // num을 high(앞부분), low(뒷부분)으로 분할
	int high1, low1;
	high1 = num1 / pow(10, m);
	low1 = num1 % (int)pow(10, m);	
	int high2, low2;
	high2 = num2 / pow(10, m);
	low2 = num2 % (int)pow(10, m);

    // z0, z1, z2를 각각 재귀호출
	int z0 = karatsuba(low1, low2);
	int z1 = karatsuba((low1 + high1), (low2 + high2));
	int z2 = karatsuba(high1, high2);

	return (z2 * pow(10 , (m * 2)) + ((z1 - z2 - z0) * pow(10 , m)) + z0);
}

int main() {
	int A, B;
	cin >> A >> B;
	cout << karatsuba(A, B) << endl;
	return 0;
}

 

자료형이 int라서 큰 연산은 불가능하겠지만, 원리를 보이기 위해 최대한 간단하게 구현했다.

 

ruhz3/CodingTest