ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Karatsuba algorithm
    Algorithm/분할정복 2020. 1. 21. 16:51
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    //카라츠바의 빠른 정수 곱셈 알고리즘
     
    //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 == 0return vector<int>();
        //기저 사례: a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다
        if(an < 50return 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*b1
        vector<int> z2 = karatsuba(a1, b1);
        //z0 = a0*b0
        vector<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

    댓글

Designed by Tistory.