[분할정복/카라츠바 알고리즘] 곱셈 최적화! 카라츠바 알고리즘에 대해 알아보자

기본 단계

카라추바 알고리즘의 기본 단계는 큰 두 수 x와 y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다.

x와 y를 B진법의 n자리수라고 하자. n보다 작은 양수 m에 대해 다음과 같이 x, y를 쪼갤 수 있다.

x = x₁B^m + x₀

y = y₁B^m + y₀

(단, x₀과 y₀는 B^m보다 작다.)

z₂ = x₁y₁

z₁ = x₁y₀ + x₀y₁

z₀ = x₀y₀

라고 할 때, x와 y의 곱은

xy = (x₁B^m + x₀)(y₁B^m + y₀)

= z₂ B^2m + z₁ B^m + z₀

이 식은 4번의 곱셈을 해야한다. 카라추바는 덧셈을 몇 번 함으로써, xy를 3번의 곱셈을 통해 구할 수 있다는 걸 알았다.

 

z₂ = x₁y₁ 라 하자.

z₀ = x₀y₀ 라 하자.

z₁ = (x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀) - x₁y₁ - x₀y₀ = x₁y₀ + x₀y₁

이므로

z₁ = (x₁ + x₀)(y₁ + y₀) − z₂ − z₀ 라 할 수 있다.

 

예

B = 10 이라하고, m = 2 라 하자. 1234와 5678의 곱을 구하고 싶으면,

12 34 = 12 × 10² + 34

56 78 = 56 × 10² + 78

z₂ = 12 × 56 = 672

z₀ = 34 × 78 = 2652

z₁ = (12 + 34)(56 + 78) − z₂ − z₀ = 46 × 134 − 672 − 2652 = 2840

결과 = z₂ × 10^2×2 + z₁ × 10² + z₀ = 672 × 10000 + 2840 × 100 + 2652 = 7006652

우선, 우리 개발자의 영원한 친구 위키백과에서 확인해봅시다!

위의 식을 어떻게 코드로 구현하면 될까요?

역시 분할 정복인 만큼 '재귀 함수'로 구현하는 것이 편합니다.

카라츠바 알고리즘에 의하면, 큰 수 A가 m자리 수라고 하고 하면, 다음과 같이 표현될 수 있습니다.

 

half = m / 2 라고 하면,

z2 * 10^ (half + half) + z1 * 10 ^ (half) + z0

 

즉, 카라츠바 알고리즘에서 가장 중요한 것은 자리수를 이등분하여 x1, x2, y1, y2를 정해서

z0, z1, z2를 다시 카라츠바 알고리즘을 이용해서 구하는 것입니다!

 

이를 위해서는 각 자리수마다 덧셈과 뺄셈을 만들어 주는 것이 필요합니다.

참고로, add() 함수의 뒤에 int k 를 넣은 이유는 z2, z1과 같은 경우는 half 만큼 자리수의 위치를 스위칭해서 더해줘야 하기 때문입니다.

 

또한, 기저 사례를 위해서 

의 시간복잡도를 가지는 보통의 곱셈 방식을 구현합니다.

 

아래는 전체적인 코드입니다! 

참고로 각 자리의 올림은 하지 않은 상태입니다. 

이는 마지막 결과에서 벡터마다 10으로 나눈 값을 다음 자리수에 더해주면서 올림을 시행하면 됩니다.

반대로 자리수에 남아있는 값은 벡터마다 %10 으로 모듈라 연산을 해주면 됩니다.

 

참고로 이 코드에선 보이지 않지만, main문에서 reverse를 수행하고 카라츠바를 수행했습니다.

(리버스를 해 놓고 실행해야 0000 과 같이 앞에 0이 오는 경우를 pop_back으로 처리하기 쉽기 때문입니다.)

 

 

typedef vector<int> VEC;
 
VEC multi(VEC& A, VEC& B)
{
    int s1 = A.size();
    int s2 = B.size();
 
    VEC res;  
    res.resize(s1 + s2 - 1, 0);
 
    for (int i = 0; i < s1; i++)
    {
        for (int j = 0; j < s2; j++)
        {
            res[i + j] += A[i] * B[j];
        }
    }
    return res;
}
 
void add(vector<int>& vec1, vector<int>& vec2, int k)
{    
    int s = max(vec2.size() + k, vec1.size());
 
    vec1.resize(s, 0);
    vec2.resize(s, 0);
 
    for (int i = 0; i < s - k; i++)
    {
        vec1[i + k] += vec2[i];
    }
    
}
 
void sub(vector<int>& vec1, vector<int>& vec2)
{
    int s = max(vec1.size(),vec2.size());
 
    vec1.resize(s, 0);
    vec2.resize(s, 0);
 
    for (int i = 0; i < s; i++) vec1[i] -= vec2[i];
}
 
VEC Karatsuba(VEC& A, VEC& B)
{
    if (A.size() < 50)
    {
        VEC res;
        res = multi(A,B);
        return res;
    }
 
    int half = A.size() / 2;
    
    if (A.empty() || B.empty()) return VEC();
 
    VEC a1 = VEC(A.begin(), A.begin() + half);
    VEC a0 = VEC(A.begin() + half, A.end());
    VEC b1 = VEC(B.begin(), B.begin() + min(half, B.size()));
    VEC b0 = VEC(B.begin() + min(half, B.size()), B.end());
 
    VEC z0, z1, z2;
    
    z0 = Karatsuba(a0, b0);
    z2 = Karatsuba(a1, b1);
    
    add(a0, a1, 0);
    add(b0, b1, 0);
 
    z1 = Karatsuba(a0, b0);
    sub(z1, z0);
    sub(z1, z2);
 
    VEC res;
    add(res, z2, 0);
    add(res, z1, half);
    add(res, z0, half + half);
 
    return res;
}

각 자리수에 맞게 벡터의 배열에 넣으면 가장 편리한 점은 multi() 함수에서 확인할 수 있습니다.

두 벡터의 인덱스의 합이 바로 두 자리수 곱이 들어가야할 자리수 위치로 만들수 있기 때문입니다.

 

그럼 카라츠바 알고리즘의 시간복잡도를 계산해봅시다.

 

기저 사례가 자리수 50으로 되어있지만, 자리수가 1이 되어야 한다고 가정하겠습니다.

각 자리수를 2 등분 하므로, 둘 중 자리수가 큰 값을 n 이라고 한다면, 단계는 총

입니다.

그리고, 단계마다 3개로 나누어지기 때문에, 시간 복잡도는 

이 됩니다.

 

여기서, 예전에 중학교에서 배웠던 로그 지식을 약간 활용해서

 

을 얻을 수 있습니다! (프로그래밍의 새계에선 log밑이 2인 것이 default!)

 

따라서 시간복잡도는 

입니다. 

이는 

보다 빠른 알고리즘임을 알 수 있습니다.