분할정복 알고리즘 - 큰수 곱셈

두 수를 곱할 경우 우리는 그 두 수의 각자리수를 곱하고 덧셈한다.

만약 두 수 가 큰 수라면 연산 횟수가 많아져 O(n^2)의 시간이 걸린다.

이 문제를 해결하는 것이 바로 카라바츠 알고리즘 이다.

카라바츠 알고리즘

분할정복으로 큰 두수의 곱셈을 처리한다. 

일반적인 두 수 A와 B의 곱셈을 나타내어보자. 두 수의 자릿수가 n인 경우,

m = n / 2 ( 자릿수의 반)

A = a1 * 10 ^ m + a0

B = b1 * 10 ^ m + b0

A * B = (a1 * 10 ^ m + a0) * (b1 * 10 ^ m + b0) = a1*b1*(10 ^ 2m) + a1 * (10 ^ m) * b0 + a0*b1*(10^m) + a0*b0
= a1*b1*(10^2m) + (a1*b0 + a0*b1) * (10^m) + a0*b0

이와 같은 과정을 거쳐서 두 수의 곱셈을 구하려면 총 4번의 곱셈이 필요하다. 

a1*b1*(10^2m) + (a1*b0 + a0*b1) * (10^m) + a0*b0

하지만 카라바츠의 알고리즘을 사용하면 다음과 같다.

z2 = a1 * b1, z0 = a0 * b0, z1 = (a1 + a0)*(b1 + b0) - z2 - z0

(a1 + a0)*(b1 + b0) = a1 * b1 + a1 * b0 + a0 * b1 + a0 * b0
(a1*b0 + a0*b1) = (a1 + a0)*(b1 + b0) - a1 * b1 - a0 * b0 = (a1 + a0)*(b1 + b0) - z2 - z0

z0, z1, z2라는 변수로 위와 같이 값을 정의해준다.

a1*b1*(10^2m) + (a1b0 + a0b1) * 10m + a0b0 = z1*(10 ^ 2m) + z1*(10^m) + z0

이와 같이 카라바츠 알고리즘을 사용하면 위에선 4번이던 곱셈을 이젠 3번의 곱셈으로 구해낼 수 있다.

방법	곱셈 횟수	시간복잡도
일반 곱셈	4개	O(n²)
카라츠바	3개	O(n^log₂3) ≈ O(n^1.585)