[Algorithm Strategies] 06. Divide & Conquer - Karatsuba Multipy

1. Divide & Conquer

1.1 Karatsuba Multipy - Example Program

1.1.1 Problem

- 빠른 곱셈 알고리즘으로, 두 개의 정수를 곱하는 알고리즘

   - 32비트 정수 둘을 곱할 때 쓰는 것이 아닌 수백자리, 나아가 수만 자리는 되는 큰 숫자들을 다룰 때 주로 사용

     - 이 곱셈 알고리즘을 적용하기 전 기존의 곱셈 알고리즘을 설명

1.1.1.1 O(n²) Mutiply

vector<int> DivideConquer::multiply(const vector<int>& a, const vector<int>& b);

 -  곱셈을 진행할 때 일반적인 정수형 변수가 아닌 정수형 배열을 입력받는 점을 확인

   - 이 배열들은 곱할 수의 각 자릿수를 맨 아래 자리부터 저장, 이렇게 순서를 뒤집으면 입출력할 때는 불편

     - 주어진 자릿수의 크기를 쉽게 구할 수 있다는 장점 존재

 - 따라서 C에 모든 값을 곱한 데이터 저장 및 Normalize 함수 실행

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] * b[i];
normalize(c);

1.1.1.2 Normalize

void DivideConquer::normalize(vector<int>& num);

 - 1개의 값을 추가하여 반복문에 대해 초과되지 않게 설정하고 자릿수 올림 설정

num.push_back(0);
for (int i = 0; i + 1 < num.size(); i++) { /* ... */ }

   - 음수의 경우 앞의 자리수를 빌려 뒤에서 값을 사용할 수 있도록 설정

     - 양수의 경우 10보다 큰 경우의 수의 값이 들어올 경우 나눈 후 앞의 값에 더해주고 원래 값은 나머지 값으로 설정

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; }

   - 배열의 마지막이 0인 경우 0을 빼고 반환

while (num.size() > 1 && num.back() == 0) num.pop_back();

1.1.2 Algorithm Strategy

- 카리츠바의 빠른 곱셈 알고리즘은 두 수를 각각 절반으로 쪼개 a와 b가 각각 256자리 수라면 128자리를 저장

   - a = a₁ X 10¹²⁸ + a₀ & b = b₁ X 10¹²⁸ + b₀

     - 카리츠바는 이 떄 a X b를 네 개의 조각을 이용해 표현

       - a X b = a1 X b1 X 10¹²⁸ +(a1 X b0 + a0 X b1) X 10¹²⁸ + a0 X b0

 - 이 방법에서 큰 정수 두 개를 한 번 곱하는 대신, 절반 크기로 나눈 작은 조각 네 번을 곱함

   - 이대로 각각을 재귀 호출해서 해결하면 분할 정복 알고리즘을 사용 가능

 - 카라츠바가 발견한 것은 다음과 같이 a X b를 표현했을 때 네 번 대신 세번의 곱셉으로 이 값을 계산

   - (a0 + a1) X (b0 + b1) = a0 X b0 + (a1 * b0 + a0 X b1) + a1 X b1

     - 위의 곱셈을 통해 두개를 곱하여 파란색의 값과 빨간색의 값을 빼면 값을 구할 수 있음

 - 따라서 이 과정의 곱셈을 세 번밖에 쓰지 않음, 세 결과를 적절히 조합해 원래 두 수의 답을 구해낼 수 있음

1.1.3 implementation

vector<int> DivideConquer::Karatsuba(const vector<int>& a, const vector<int>& b);

 - a가 b보다 크지 않는 경우만 활용할 수 있도록 설정하기 위해 큰 값이 있는 경우 변경하여 설정

   - 종료조건이 0이거나 50보다 작은경우 다른 것을 활용하거나 종료

int an = a.size(), bn = b.size(); if (an < bn) return Karatsuba(b, a);
if (an == 0 || bn == 0) return vector<int>(); if (an < 50) return multiply(a, b);

 - 위에서 설명했듯이 a0, a1, b0, b1를 생성하여 계산에 활용할 수 있도록 설정

   - 설정한 값을 이용하여 위에서 구한 3가지 곱셈 중 2가지를 활용할 수 있으므로 곱셈 진행

int half = an / 2;
vector<int> a0(a.begin(), a.begin() + half); vector<int> a1(a.begin() + half, a.end());
vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

vector<int> z2 = Karatsuba(a1, b1); vector<int> z0 = Karatsuba(a0, b0);

   - (a0 + a1) X (b0 + b1)를 계산하여 위에서 곱한 2가지 값을 뺀 경우 마지막 한 조각인 마지막 값을 만들 수 있음

/* a += b * 10^k */ addTo(a0, a1, 0); addTo(b0, b1, 0);	
vector<int> z1 = Karatsuba(a0, b0);
/* a -= b */ subFrom(z1, z0); subFrom(z1, z2);

 - 마지막으로 모든 값을 더해주게 된다면 값을 구할 수 있음

vector<int> ret; addTo(ret, z0, 0); addTo(ret, z1, half); addTo(ret, z2, half + half);