카라츠바의 빠른 곱셈 알고리즘

카라츠바 알고리즘이란 ?

분할 정복 알고리즘의 한 예로, 재미있는 병합과정을 가진 알고리즘이다.
수 백 자리 이상의 큰 수의 곱셈할 때 사용하는 빠른 곱셈을 위해 만들어졌다.

기본적인 곱셈 방법

두 자연수의 십진수 표기가 배열에 주어진다고 할 때, 이 둘을 곱한 결과를 계산하는 가장 기본적인 방법은 아래 그림과 같다

이 과정을 코드로 곧장 옮깃 것이 아래와 같다

/* 두 큰수를 곱하는 O(n^2) 시간 알고리즘*/

// num[]의 자릿수 올림을 처리한다
void nomalize(vector<int>& num) {
	num.push_back(0);
    
    // 자릿수 올림 처리
    for (int i=0; i<num.size(); i++) {
    	if (num[i] < 0) {
        	int borrow = (abs(num[i])) + 9 / 10;
            num[i+1] -= borrow;
            num[i] += borrow * 10;
        } else {
 			num[i+1] += num[i]/10;
            num[i] %= 10;
    	}
    }
    while(num.size() > 1 && num.back() == 0) num.pop_back();
}
// 두 긴 자연수의 곱을 반환
// 각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어있음
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
	vector<int> c(a.size() + b.size() + 1, 0);
    for (int i=0; i<a.size(); i++) {
    	for (int j=0; j<b.size(); j++) {
        	c[i+j] += a[i] *j[j];
        }
    }
	normalize(c);
    return c;
}

이 알고리즘의 시간복잡도는 두 정수 배열의 길이가 모두 n이라고 할떄 O(n^2)이다.