[Algorithm] Karatsuba Algorithm

Karatsuba 알고리즘..

간단히 소개하자면 큰수에 대한 효율적인 곱셈 알고리즘

N자리 K진수 A, B가 주어졌을 때, 두 수의 곱을 연산하는데 쓰이는 알고리즘.
long long 자료형의 범위(-9223372036854775808 - 9223372036854775807) 즉 최소 N이 20넘어가는 순간부터는 이런 특이한 알고리즘을 사용하지 않으면 계산이 안될것 같다..

이 알고리즘의 특이한 점은 수를 하나의 정수 자료형에 두고 사용하는게 아니라 배열에 넣어놓고 연산해서 연산 도중 B값을 넘거나, 0보다 작아지는 경우에 대해 직접적으로 처리를 해주어야 한다는 점인거 같다.

이 알고리즘을 사용하지 않고 단순히 수학적으로 계산을 하게 된다면

위와 같은 방식으로 계산이 될것이고 이경우 코드는 아래와 같이 표형될것 같다..

_vector<lld> multiply(_vector<lld>& a, _vector<lld>& b) { int aLen = a.size(); int bLen = b.size(); _vector<lld> ret(aLen + bLen, 0); for (int i = 0; i < aLen; ++i) { for (int j = 0; j < bLen; ++j) { int multi = a[i] * b[j]; ret[i + j + 1] += multi / BASE; ret[i + j] += multi % BASE; } } return ret; }

이 방법의 경우 N이 커지는 경우 이차원 배열을 모두 돌아줘야 해서 O(N^2)의 시간 복잡도를 가지게 된다.
만약 N이 만단위가 넘어간다면 상당히 비효율적인 알고즘이 될것 같다,...

Karatsuba 알고리즘을 소개하자면,

(1)에 의하면 O(N/2)연산이 4번 발생하고 (3)에 의해 수식을 정리하면 (2)와 같이 표현될수 있다.
(2)에 의하면 O(N/2)연산이 3번 발생하게 되어서 수행시간을 단출할 수 있다.

결과적으로 Z를 해당하는 인덱스에 집어넣어 주면 N자리 K진수의 곱의결과를 구할 수 있다.
* 인덱스의 값이 K진수의 차수라고 생각하면 인덱스를 계산하기가 쉽다.

F(N) = 3F(N/2) + XN
시간 복잡도 계산을 위한 점화식은 위와 같은데 X값은 A,B를 나누는 방법이나 더하는 방식에 따라 달라 질 수 있을것 같다.
이에 따라 발생할수 있는 시간 복잡도는 O(N^logN)이 된다..

다시 돌아가서.. Karatsuba 알고리즘의 구현 방법에 대해 알아보자면
기본적으로 분할 정복 기법이 사용되어 구현이 되는데

첫번째로 기저사례에 대해 알아보자면 보통의 경우 분할 정복에서 기저사례는 나누어지지 않을때까지 나눈 상태를 의미 하는데 Karatsuba의 경우는 너무 많이 나누는 경우 배열을 쪼개고 할당하고 다시 연산하는 과정에서 부하가 걸릴 수도 있기 때문에 적당히 작은 크기를 선정해야 한다.

다른 예제에서도 그렇고 이번에 했을떄는 배열의 크기가 50보다 작거나 같은 경우에 기저사례로 보고 그 경우에 처음에 소개 했던 O(N^2) 방법을 사용하여 곱셈을 수행하도록 했다. 그래도 N이 50정도이면 2500번정도만 반복문이 수행되어 적당할것 같다.

두번째로 분할의 경우, N자리 입력된 배열 A, B를 반으로 나누어서 위에서 소개한 연산을 수행 시켜서 Z값들을 연산시키면 된다.
이 과정에서 N개 짜리 배열을 반으로 나누는 연산, N/2개 짜리 배열을 더하고, 빼는 연산, 마지막으로 N/2개 짜리 배열을 곱하는 연산이 수행되는데 이떄 N/2개짜리 배열에 대한 Karatsuba연산을 3번 호출하게 된다.

마지막으로 정복은, Z값들을 인덱스에 맞춰서 더해주는 연산은 앞서 소개한 수식에서 보이는 것 처럼 0, m, 2m번째 인덱스를 베이스로 두고 Z값 배열을 결과배열에 추가해주면 된다.

위 내용에 대한 구현 사항은 아래와 같다

#include <stdio.h> #include <malloc.h> #define lld long long #define MAX_LENGTH 300000 #define BASE 10 template <class T> class _vector{ private: . . . }; #define abs(n) ((n < 0) ? -n : n) #define min(a, b) ((a < b) ? a : b) void printNum(_vector<lld>& num) { for (int i = num.size() - 1; 0 <= i; --i) { printf("%lld ", num[i]); } printf("\n"); } void normalize(_vector<lld>& num) { int size = num.size(); for (int i = 0; i < size - 1; ++i) { if (num[i] > BASE) { num[i + 1] += num[i] / BASE; num[i] %= BASE; } else if (num[i] < 0) { int borrow = (abs(num[i]) + (BASE - 1)) / BASE; num[i + 1] -= borrow; num[i] += borrow * BASE; } } while (num.size() > 1 && num.back() == 0) { num.pop_back(); } } _vector<lld> multiply(_vector<lld>& a, _vector<lld>& b) { int aLen = a.size(); int bLen = b.size(); _vector<lld> ret(aLen + bLen, 0); for (int i = 0; i < aLen; ++i) { for (int j = 0; j < bLen; ++j) { ret[i + j] += a[i] * b[j]; } } normalize(ret); return ret; } void addTo(_vector<lld>& a, _vector<lld>& b, int k) { int originalALen = a.size(); int bSize = b.size(); if (originalALen < bSize + k) { a.resize(bSize + k); } a.push_back(0); int aSize = a.size(); for (int i = originalALen; i < aSize; ++i) { a[i] = 0; } for (int i = 0; i < bSize; ++i) { a[i + k] += b[i]; } normalize(a); } void subFrom(_vector<lld>& a, _vector<lld>& b) { int bSize = b.size(); for (int i = 0; i < bSize; ++i) { a[i] -= b[i]; } normalize(a); } _vector<lld> karatsuba(_vector<lld>& a, _vector<lld>& b) { int aLen = a.size(), bLen = b.size(); if (aLen < bLen) { return karatsuba(b, a); } if (aLen == 0 || bLen == 0) { return _vector<lld>(); } if (aLen <= 50) { return multiply(a, b); } int half = aLen / 2; _vector<lld> a0(a, 0, half); _vector<lld> a1(a, half, aLen); _vector<lld> b0(b, 0, min(b.size(), half)); _vector<lld> b1(b, min(b.size(), half), bLen); _vector<lld> z2 = karatsuba(a1, b1); _vector<lld> z0 = karatsuba(a0, b0); addTo(a0, a1, 0); addTo(b0, b1, 0); _vector<lld> z1 = karatsuba(a0, b0); subFrom(z1, z0); subFrom(z1, z2); _vector<lld> ret(z2.size() + half * 2, 0); addTo(ret, z0, 0); addTo(ret, z1, half); addTo(ret, z2, half * 2); return ret; }

STL이 제한되지 않는다면 vector 라이브러리를 직접 가져다가 동일 로직을 수행시키면 될것 같은데
이번에 시험 봤던 환경은 STL이 제한되어 나른대로 짝퉁 _vector를 구현해서 사용했다.
include-note.tistory.com/entry/STL-vector

[STL] vector

이 알고리즘에 대한 전체 구현은 아래 링크에 있고
github.com/KyungminYu/Algorithm/blob/master/algorithm/karatsuba.cpp

KyungminYu/Algorithm

추가적으로 곱셈 문제를 풀어보려고 했다....
www.acmicpc.net/problem/13277

13277번: 큰 수 곱셈

그런데 이 문제는 Karatsuba 알고리즘으론 풀수가 없다고 한다,,, 이름이 큰수 곱셈이라 가능할줄 알았는데 이거보다 더 빠른 FFT(고속 푸리에 변환)라는 알고리즘을 사용해야 한다고 한다..