[Algorithm] 분할정복(2) - Multiplication

🤔 분할정복

분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다.

 

이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다.

 

이번 포스팅에서는 분할정복의 Multiplication 예시를 알아보겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Multiplication

두 n 비트 이진수인 $x$와 $y$를 곱하는 문제를 해결해보겠습니다.

 

분할정복 기법을 사용하여 이론적으로 더 빠른 알고리즘을 디자인 하는 방법에 대해 알아보겠습니다.

 

편의상 $n$은 2의 거듭제곱 꼴이라 가정하고, $x$의 왼쪽 $n/2$ 비트 부분과 나머지 부분을 각각 $x_L, x_R$이라고 하겠습니다.

 

마찬기자로 $y_L, y_R$을 정의하겠습니다.

 

$x = 1 0 1 1 0 1 1 0,  y = 1 0 0 1 1 1 0 0$라는 예시를 통해 Multiplication을 진행해보겠습니다.

 

 

 

 

$x_L, x_R, y_L, y_R$은 각각의 정의에 의해 $x, y$를 아래와 같이 나타낼 수 있습니다.

 

$$x = 2^{\frac{n}{2}}x_L + x_R$$

$$x = 2^{\frac{n}{2}}y_L + y_R$$

 

따라서 $x*y = (2^{\frac{n}{2}}x_L + x_R)(2^{\frac{n}{2}}y_L + y_R) = 2^nx_Ly_L + 2^{\frac{n}{2}}(x_Ly_R + x_Ry_L) + x_Ry_R$로 나타낼 수 있습니다.

 

이때 $x * y$은 Main Problem $x_Ly_L, x_Ly_R, x_Ry_L, x_Ry_R$은 Subproblem 이라고 할 수 있습니다.

 

위의 식에 따라 $x, y$를 곱하는 문제는 두 $n/2$ 비트 이진수를 곱하는 Subproblem 4개 + shift연산 $n + n/2$번 add연산 3번으로 구성됩니다.

 

따라서 두 $n$비트 이진수 $x, y$를 곱하는데 걸리는 시간을 $T(n)$이라고 했을 때

 

$$T(n) = 4T(n/2) + O(n)$$

 

라는 식으로 나타낼 수 있습니다.

 

이때 Master Theorem에서 $a = 4, b = 2, d = 1$을 의미하므로 $T(n) = O(n^2)$이 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Gauss's Trick

더 빠른 알고리즘을 알아보기 위해 위의 식을 조금 변형해주는 방법을 사용했습니다.

 

이를 우리는 'Gauss's Trick'이라고 부릅니다

 

 $x*y = (2^{\frac{n}{2}}x_L + x_R)(2^{\frac{n}{2}}y_L + y_R) = 2^nx_Ly_L + 2^{\frac{n}{2}}(x_Ly_R + x_Ry_L) + x_Ry_R$

 

의 식에서 $(x_Ly_R + x_Ry_L)$를 $(x_L + x_R)(y_L + y_R) - x_Ly_L - x_Ry_R$이라고 변형합니다.

 

또한 $(x_L + x_R)(y_L + y_R) = x_Ly_R + x_Ry_L + x_Ly_L + x_Ry_R$이라는 성질을 이용하면 $x, y$의 곱은 두 n비트 이진수를 곱하는 subproblem 3개{$(x_L + x_R)(y_L + y_R), x_Ly_L, x_Ry_R$} 과 기타 $O(n)$연산들로 구할 수 있습니다.

 

이를 수도 코드로 나타내면 아래와 같이 나타낼 수 있습니다.

 

 

 

$x, y$를 곱하는데 걸리는 시간을 $T(n)$이라고 하면 $T(n) = 3T(n/2) + O(n)$입니다.

 

위 식의 일반해는 Master Theorem에 의해 $T(n) = O(n^{log_23) ≈ O(n^{1.59})$가 됩니다.

 

 

 

현재 제일 빠른 알고리즘은 $O(nlogn)$알고리즘이라고 합니다.

 

참고로 알아두세용.