종만북::카라츠바 알고리즘 정답편 + 포스팅의 사본

상태: 정리완료

구현완료

    z2 값에 미리 10^(half+half) 를 곱해버려서 생긴 문제 하나,
    언제나 an == half + half 일 것이라는 헛된 추측으로 생긴 문제 하나.

    왜 an 을 사용하면 안되고 half + half 를 사용해야 하는가?
    a,b가 9자리 수라고 가정하자,
    a = a1 * 10^4 + a0 (이때, a1은 4자리, a0은 5자리)
    b도 마찬가지.
    따라서,
    a * b = a0b0 * 10^8 + (a0b1 + a1b0) * 10^4 + a1b1
    여기에서 10^8 의 8이 곧 half+half를 의미하게 된다.

내 코드 :: apss_7_big_mult_karatsuba.cp

#include"apss_7_big_mult_slow.h"

vctor<char> karatsuba(vector<char>& a, vector<char>& b);
extern void normalize(vector<char>& num);
extern vector<char> slow_mult(const vector<char>& a, const vector<char>& b);
// helper functions
vector<char> operator+(const vector<char>& a, const vector<char>& b);
vector<char> operator-(const vector<char>& a, const vector<char>& b);
vector<char> pow10(const vector<char>& a, int amt);
istream& operator>>(istream& ist, vector<char>& a);
ostream& operator<<(ostream& os, const vector<char>& a);

int main(void)
{
    vector<char> a, b;
    cin >> a >> b;
    cout << a << '\n' << b << '\n';
    cout << karatsuba(a, b) << '\n';
    return 0;
}
vector<char> karatsuba(vector<char>& a, vector<char>& b)
{
    int an = a.size(), bn = b.size();
    if (an < bn)
        return karatsuba(b, a);
    // base condition : a 또는 b가 비어있는 경우
    if (an == 0 || bn == 0)
        return vector<char>();
    // base condition : a 가 비교적 짧은 경우, 일반 mult로 해결한다.
    if (bn < 5)
        return slow_mult(a, b);

    // a, b를 half 자리와 그 나머지로 분리한다.
    int half = an / 2;
    vector<char> a0 {a.begin(), a.begin()+half};
    vector<char> a1 {a.begin()+half, a.end()};
    vector<char> b0 {b.begin(), b.begin() + min(b.size(), (size_t)half)};
    vector<char> b1 {b.begin() + min(b.size(), (size_t)half), b.end()};

    // a * b == z0 + z1*pow(10,half) + z2*pow(10, half+half) 이때,
    // z0 = a0 * b0
    // z2 = a1 * b1
    // z1 = (a1*b0 + a0*b1) OR ( (a0+a1)*(b0+b1) - z0 - z2 )
    vector<char> z0 = karatsuba(a0, b0);
    vector<char> z2 = karatsuba(a1, b1);

    a0 = a0 + a1;
    b0 = b0 + b1;
    vector<char> z1 = karatsuba(a0, b0) - z0 - z2;
    z1 = pow10(z1, half);
    z2 = pow10(z2, half+half);

    vector<char> ret(0);
    ret = ret + z0 + z1 + z2;
    return ret;
}

내 코드 :: apss_7_big_mult_slow.cpp

/*
    카라츠바의 빠른 곱셈 알고리즘을 시작하기에 앞서,
    일반적으로 곱셈을 수행하는 방식을 그대로 코드에 적용
    시켜보자.
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cmath>
#include<cstdlib>
#include<sys/types.h>

using namespace std;

vector<char> slow_mult(const vector<char>& a, const vector<char>& b);
void normalize(vector<char>& num);
//
//   int main(void)
//   {
//       vector<char> a{4,3,2,1};
//       vector<char> b{8,7,6,5};
//       vector<char> ret = slow_mult(a, b);
//       for (int i = ret.size()-1; i >= 0; --i)
//       {
//           cout << static_cast<int>(ret[i]) << ' ';
//       }
//       printf("\n");
//       return 0;
//   }
// two vectors index is equal to power of 10
// a[i] means a's i'th digit. (==a[i] * 10^i)
vector<char> slow_mult(const vector<char>& a, const vector<char>& b)
{
    vector<char> ret( a.size()+ b.size() + 1, 0 );

    // do multiply each indices
    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < b.size(); j++)
        {
            ret[i+j] += a[i] * b[j];
        }
    }

    // when simple multiply is over,
    // you should NORMALIZE this,
    // because each index might bigger than 10
    normalize(ret);

    return ret;
}
// 자릿수 올림을 처리
void normalize(vector<char>& num)
{
    num.push_back(0);
    for (int i = 0; i < num.size(); i++)
    {
        if (num[i] < 0)
        {
            char borrow = (abs(static_cast<int>(num[i])) + 9) / 10;
            num[i+1] -= borrow;
            num[i] += borrow * 10;
        }
        else
        {
            num[i+1] += num[i] / 10;
            num[i] %= 10;
        }
    }
    while(num.size() > 1 && num.back() == 0) num.pop_back();
}