카라츠바 곱셈 알고리즘에 대해

  • AlgoPrince
    AlgoPrince

    책에 addTo함수와 subFrom 함수가 나와있지 않아서 직접 구현했고
    karatsuba는 책에 있는 그대로 적었는데 그냥 multiply로 계산한 것과 값이 다르게 나와 여쭤봅니다.

    처음에는 addTo나 subFrom에 문제가 있겠거니 생각해서 디버깅 다 해봤는데 굉장히 잘 돌아갑니다.

    코드 첨부합니다.

    void addTo(vector<int>& a, const vector<int>& b, int k) { // 10^k만큼 b에 곱한 값을 a에 곱한다.
    unsigned m = a.size();
    unsigned n = b.size();

    if (a.size() < k) {

        for (unsigned i = 0; i < k - m; ++i)
            a.push_back(0);
        for (unsigned i = 0; i < n; ++i)
            a.push_back(b[i]);
    }
    else {
        for (unsigned i = 0; i < min(m - k, n); ++i) {
            a[i + k] += b[i];
        }
        if (m < n + k)
            for (unsigned i = m - k; i < n; ++i)
                a.push_back(b[i]);
    }
}
void subFrom(vector<int>& a, const vector<int>& b) { // b.size() < a.size()라고 가정.
    for (unsigned i = 0; i < b.size(); ++i) {
        a[i] -= b[i];
    }
}

    그리고 카라츠바 곱셈 알고리즘은 책에 나와있는 대로 이렇게 짰습니다.

    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 <= 50) return multiply(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());

    vector<int> z2 = karatsuba(a1, b1);

    vector<int> z0 = karatsuba(a0, b0);

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

    vector<int> z1 = karatsuba(a0, b0);

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


    vector<int> ret;
    addTo(ret, z0, 0);
    addTo(ret, z1, half);
    addTo(ret, z2, half + half);
    return ret;
}

    가장 큰 문제점은 카라츠바로 계산했을 때 노멀라이즈가 되지 않고 음수가 포함되어 나온다는 것입니다. 계산 시간은 확실히 빠르지만 왜 그런지 이유를 찾지 못하고 있습니다.


    7년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.