karatsuba algorithm

큰 수의 곱을 수행할 때 사용되는 karatsuba algorithm은 divide and conquer algorithm 을 통해 시간 복잡도를 줄인 algorithm 입니다.

https://ko.wikipedia.org/wiki/카라추바_알고리즘

두 수의 길이가 an과 bn 이라 할 때 일반적인 곱셈법은 O(an*bn) 이라할 때

 karatsuba algorithm은 두 수를 각각 반씩 나눠 네 개의 조각으로 만든 후 네 번의 곱을 세 번으로 줄여 시간 복잡도를 줄이는 방법을 사용했습니다.

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
#pragma region helper func
//a += b * (10^k)
void addForKaratsuba(vector<int>& a, const vector<int>& b, int k)
{
    int aSize = a.size();
    int bSize = b.size();
    int count = max(aSize, bSize + k);
 
    int tempK = k;
    for (int i = 0; i < count; i++)
    {
        if (tempK <= 0)
        {
            if (bSize + k - i > 0)
            {
                if (aSize - i > 0)
                {
                    int sum = a[i] + b[i - k];
                    if (sum >= 10)
                    {
                        a[i] = sum % 10;
 
                        if (aSize > i + 1)
                            a[i + 1] += 1;
                        else
                        {
                            a.push_back(1);
                            aSize++;
                        }
                    }
                    else
                        a[i] = sum;
 
                }
                else
                {
                    a.push_back(b[i - k]);
                    aSize++;
                }
            }
        }
        else
        {
            if (aSize - i <= 0)
            {
                a.push_back(0);
                aSize++;
            }
        }
        tempK--;
    }
}
 
//a -= b. a >= b 를 가정.
void subtractForKaratsuba(vector<int>& a, const vector<int>& b)
{
    if (a.size() < b.size())
        return;
    int aSize = a.size();
    int bSize = b.size();
    for (int i = 0; i < aSize; i++)
    {
        if (bSize - i > 0)
        {
            int ret = a[i] - b[i];
 
            if (ret <= -1)
            {
                ret = a[i] + 10 - b[i];
                a[i + 1] -= 1;
            }
 
            a[i] = ret;
        }
    }
}
 
void normalize(vector<int>& numbers)
{
    numbers.push_back(0);
    for (int i = 0; i < numbers.size() - 1; i++)
    {
        if (numbers[i] >= 0)
        {
            numbers[i + 1] += numbers[i] / 10;
            numbers[i] %= 10;
        }
        else
        {
            int borrow = (abs(numbers[i]) + 9) / 10;
            numbers[i + 1] -= borrow;
            numbers[i] += borrow * 10;
        }
    }
    while (numbers.size() > 1 && numbers.back() == 0)
        numbers.pop_back();
}
#pragma endregion
 
vector<int> multiplyNaive(const vector<int>& a, const vector<int>& b)
{
    vector<int> ret(a.size() + b.size() + 1, 0);
    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < b.size(); j++)
            ret[i + j] += a[i] * b[j];
    }
 
    normalize(ret);
    return ret;
}
 
vector<int> karatsuba(const vector<int>& a, const vector<int>& b)
{
    int an = a.size(), bn = b.size();
 
    if (an < bn)
        return karatsuba(b, a);
 
    if (an == 0 || bn == 0)
        return vector<int>();
 
    if (an <= 10)
        return multiplyNaive(a, b);
 
    int half = an / 2;
 
    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 * b1
    vector<int> z2 = karatsuba(a1, b1);
    //z0 = a0 * b0
    vector<int> z0 = karatsuba(a0, b0);
 
    //a0 = a0 + a1
    //b0 = b0 + b1
    addForKaratsuba(a0, a1, 0);
    addForKaratsuba(b0, b1, 0);
 
    //z1 = (a0 * b0) - z0 - z2;
    vector<int> z1 = karatsuba(a0, b0);
    subtractForKaratsuba(z1, z0);
    subtractForKaratsuba(z1, z2);
 
    //ret = z0 + z1 * 10^half + z2 * 10^(half * 2)
    vector<int> ret;
    addForKaratsuba(ret, z0, 0);
    addForKaratsuba(ret, z1, half);
    addForKaratsuba(ret, z2, half + half);
    return ret;
}
 
string multiply(string& strA, string& strB)
{
    vector<int> a;
    vector<int> b;
 
    for (string::size_type i = strA.size(); i > 0; i--)
        a.push_back(strA[i - 1] - '0');
    for (string::size_type i = strB.size(); i > 0; i--)
        b.push_back(strB[i - 1] - '0');
 
    vector<int> answer = karatsuba(a, b);
 
    string ret = "";
 
    for (int i = answer.size() - 1; i >= 0; i--)
        ret += to_string(answer[i]);
 
    return ret;
}
 
int main()
{
    cout << multiply(string("57957435165759068546235724743689"), string("45808567254727890871135784")) << endl;
 
    system("pause");
    return 0;
}