카라츠바 알고리즘 (Karatsuba algorithm)

카라츠바 알고리즘의 간략한 설명이다.

원래 $a \times b$를 할 때 시간복잡도는 $O(N^2)$이다. (a, b의 길이는 모두 $N$)

이를 Divide & Conquer 로 줄일 수 있는데, 

 

편의를 위하여 $N=20$이라 하자.

 

 

구현이 젤 중요하다.

1.  LIM : 어느정도 이상은 카라츠바의 상수가 매우 크기 때문에 $O(N^2)$의 곱셈이 유리하다. 나는 이를 1000정도로 설정했다.

2. CUT : 이게 젤 중요하다. 그냥 각 자리 수를 벡터에 넣고 카라츠바를 돌리면 $O(N^{log3})$ 에 300,000을 넣은 값으로 10초 정도 걸려야 답이 나온다. 하지만 8자리씩 묶어서 넣으면 그만큼 N이 줄어듬으로 훨씬 낫다. 나는 이를 1e8정도로 설정해서 1억 진법을 따랐다.

3. 포인터 주고받기 : 그냥 벡터를 함수 인자로 주고받지 않고, const vector<int>& a; 이런 식으로 참조형을 주고받아 시간을 절약했다.

최대 248 ms 까지 절약할 수 있었다.

시간 복잡도 : $O(N^{log3})$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define MAXN 300000
#define CUT 8
#define DEC 100000000
#define LIM 1000

string sa, sb;
vector<ll> va, vb;

void convert(string s, vector<ll>& v)
{
    int i, j;
    for(i=s.size()-1; i>=0; i-=CUT)
    {
        ll now=0;
        for(j=max(i-CUT+1, 0); j<=i; j++) now=now*10+s[j]-'0';
        v.push_back(now);
    }
}

vector<ll> mult(const vector<ll>& a, const vector<ll>& b)
{
    vector<ll> ret(a.size()+b.size()+1, 0);
    int i, j;
    for(i=0; i<a.size(); i++) for(j=0; j<b.size(); j++) ret[i+j]+=a[i]*b[j];
    for(i=0; i<ret.size(); i++) if(ret[i]>=DEC)
    {
        ret[i+1]+=ret[i]/DEC;
        ret[i]%=DEC;
    }
    return ret;
}

void addTo(vector<ll>& a, const vector<ll>& b, int k)
{
    if(a.size()<b.size()+k) a.resize(b.size()+k);
    a.push_back(0);

    int i;
    for(i=0; i<b.size(); i++) a[i+k]+=b[i];
    for(i=0; i<a.size(); i++) if(a[i]>=DEC)
    {
        a[i+1]+=a[i]/DEC;
        a[i]%=DEC;
    }

    for(i=a.size()-1; i>=0 && a[i]==0; i--) a.pop_back();
}

void subFrom(vector<ll>& a, const vector<ll>& b)
{
    int i;
    for(i=0; i<b.size(); i++) a[i]-=b[i];
    for(i=0; i<a.size(); i++) if(a[i]<0)
    {
        a[i]+=DEC;
        a[i+1]-=1;
    }

    for(i=a.size()-1; i>=0 && a[i]==0; i--) a.pop_back();
}

vector<ll> karatsuba(const vector<ll>& a, const vector<ll>& b)
{
    int sa = a.size(), sb = b.size();
    if(sa<sb) return karatsuba(b, a);
    if(sa==0 || sb==0) return vector<ll>();
    if(sa<=LIM) return mult(a, b);

    int mid = sa/2;
    vector<ll> a0 = vector<ll>(a.begin(), a.begin()+mid);
    vector<ll> a1 = vector<ll>(a.begin()+mid, a.end());
    vector<ll> b0 = vector<ll>(b.begin(), min(b.begin()+mid, b.end()));
    vector<ll> b1 = vector<ll>(min(b.begin()+mid, b.end()), b.end());


    vector<ll> z0 = karatsuba(a0, b0);
    vector<ll> z1 = karatsuba(a1, b1);

    addTo(a0, a1, 0);
    addTo(b0, b1, 0);

    vector<ll> z2 = karatsuba(a0, b0);

    subFrom(z2, z0);
    subFrom(z2, z1);

    vector<ll> ret;
    addTo(ret, z0, 0);
    addTo(ret, z2, mid);
    addTo(ret, z1, mid+mid);

    return ret;
}

void print(vector<ll>& v)
{
    int i, j;
    //for(i=0; i<v.size(); i++) printf("%lld ", v[i]); printf("\n");

    for(i=v.size()-1; i>=0 && v[i]==0; i--) v.pop_back();
    if(v.empty()) { printf("0"); return; }
    printf("%lld", v[i]);
    for(i--; i>=0; i--)
    {
        for(j=DEC/10; j>=1; j/=10) printf("%lld", v[i]/j%10);
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin>>sa>>sb;
    convert(sa, va);
    convert(sb, vb);

    vector<ll> ans = karatsuba(va, vb);
    print(ans);
    return 0;
}
​