-
Karatsuba algorithmAlgorithm/분할정복 2020. 1. 21. 16:51123456789101112131415161718192021222324252627282930313233343536373839//카라츠바의 빠른 정수 곱셈 알고리즘//a += b * (10^k);를 구현한다void addTo(vector<int>& a, const vector<int>& b, int k);//a -= b;를 구현한다. a >= b를 가정한다.void subFrom(vector<int>& a, const vector<int>& b);//두 긴 정수의 곱을 반환한다.vector<int> karatsuba(const vector<int>& a, const vector<int>& b){int an = a.size(); bn = b.size();//a가 b보다 짧을 경우 둘을 바꾼다if(an < bn) return karatsuba(b, a);//기저 사례: a나 b가 비어 있는 경우if(an == 0 || bn == 0) return vector<int>();//기저 사례: a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다if(an < 50) return multiply(a, b);int half = an / 2;//a와 b를 밑에서 half 자리와 나머지로 분리한다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());//z2 = a1*b1vector<int> z2 = karatsuba(a1, b1);//z0 = a0*b0vector<int> z0 = karatsuba(a0, b0);//a0 = a0+a1; b0 = b0+b1;addTo(a0, a1, 0); addTo(b0, b1, 0);//z1 = (a0*b0)-z0-z2;vector<int> z1 = karatsuba(a0, b0);subFrom(z1, z0);subFrom(z1, z2);//ret = z0 + z1*10^half + z2*10^(half*2)vector<int> ret;addTo(ret, z0, 0);addTo(ret, z1, half);addTo(ret, z2, half*2);return ret;}
cs Karatsuba algorithm
빠른 정수 곱셈 알고리즘
시간복잡도
프로그래밍 대회에서 배우는 알고리즘 문제해결전략1