[C/C++] 큰 수의 곱셈 (karatsuba, 카라츄바)

개념은 별로 안 어려운거 같은데, 막상 짜려니 너무 힘들다..

개념

속도 O(n^log3)

B진법의 m자릿 수를 가진 X와 Y라는 수가 주어질 때,

 

 

 

 

 

#include <iostream>
using namespace std;
 
char temp[300001];
 
class Vector {
public:
    int _cap;
    int size;
    int *values;
    
    Vector() {
        size  = 0;
        _cap = 32;
        values = new int[_cap];
    }
 
    Vector(int cap) {
        size = cap;
        _cap = cap;
        values = new int[_cap];
        for(register int i = 0; i < _cap; ++i) values[i] = 0;
    }
 
    void push_back(int key) {
        if(size == _cap) {
            int *temp = new int[_cap * 2];
            for (register int i = 0; i < _cap; ++i) {
                temp[i] = values[i];
            }
            _cap = _cap << 1;
            delete[] values;
            values = temp;
        }
        values[size++] = key;
    }
 
    int get_top() {
        return values[size -1];
    }
 
    int pop() {
        return values[--size];
    }
};
 
//end is always bigger than start.
Vector str_cpy(Vector &arr, int start, int end) {
    int size = end-start;
    Vector temp; 
    for (register int i = start; i < end; ++i) {
        temp.push_back(arr.values[i]);
    }
    return temp;
}
 
void str_reverse(Vector &arr) {
    register int i = -1;
    for (i = 0; i < arr.size; ++i) {
        temp[i] = arr.values[i];
    }
    for (i = 0; i < arr.size; ++i) {
        arr.values[i] = temp[arr.size - i - 1];
    }
}
 
void carry(Vector &a) {
    for (register int i = 0; i < a.size; ++i) {
        a.values[i + 1] += a.values[i] / 10;
        a.values[i] %= 10;
    }
    while(a.size != 0 && a.get_top() == 0) a.pop();
}
 
void borrow(Vector &a) {
    for (register int i = 0; i < a.size; ++i) {
        if(a.values[i] < 0) {
                int borrow = (-a.values[i] + 9) / 10;
                a.values[i + 1] -= borrow;
                a.values[i] += borrow * 10;
        }
    }
    while(a.size != 0 && a.get_top() == 0)a.pop();
}
 
Vector add(Vector &a, Vector &b) {
    int len = a.size > b.size ? a.size : b.size;
    Vector res;
    register int i;
    for (i = 0; i < len; ++i) {
        res.push_back(a.values[i] + b.values[i]);
    }
    carry(res);
    return res;
}
 
Vector add(Vector &a, Vector &b, int k) {
    int len = a.size > b.size + k ? a.size : b.size + k;
    Vector res(len + 1);
    register int i;
    for (i = 0; i < a.size; ++i) {
        res.values[i] = a.values[i];
    }
    for (i = 0; i < b.size; ++i) {
        res.values[i + k] += b.values[i];
    }
    carry(res);
    return res;
}
 
// a must be bigger than b.
Vector subtract(Vector &a, Vector &b) {
    Vector res;
    register int i;
    for (i = 0; i < a.size; ++i) {
        res.push_back(a.values[i] - b.values[i]);
    }
    borrow(res);
    return res;
}
 
Vector multiply_normally(Vector &a, Vector &b){
    Vector res(a.size + b.size);
    for (register int i = 0; i < a.size; ++i) {
        for (register int j = 0; j < b.size; ++j) {
            res.values[i + j] += a.values[i] * b.values[j];
        }
    }
    carry(res);
    return res;
}
 
Vector multiply_karatsuba(Vector &a, Vector &b) {
    if (a.size < b.size) return multiply_karatsuba(b, a);
    if (a.size < 50) return multiply_normally(a,b);
    int m = (a.size + 1) / 2;
    Vector x0 = str_cpy(a, 0, m);
    Vector x1 = str_cpy(a, m, 2 * m);
    Vector y0 = str_cpy(b, 0, m);
    Vector y1 = str_cpy(b, m, 2 * m);
 
    Vector k1 = multiply_karatsuba(x0, x1);
    Vector k2 = multiply_karatsuba(y0, y1);
    x0 = add(x0, x1);
    y0 = add(y0, y1);
    Vector k3 = multiply_karatsuba(x0, y0);
    x0 = add(k1, k2);
    x1 = subtract(k3, x0);
 
    Vector res;
    res = add(k1, x1, m);
    res = add(res, k2, 2 * m);
    return res;
}
 
void init(Vector &a, Vector &b) {
    cin >> temp;
    register int i = -1;
    while (temp[++i] != 0) {
        a.push_back(temp[i] - '0');
    }
    str_reverse(a);
 
    cin >> temp;
    i = -1;
    while (temp[++i] != 0) {
        b.push_back(temp[i] - '0');
    }
    str_reverse(b);
}
 
int main() {
    Vector A;
    Vector B;
    init(A, B);
    Vector res;
    // algorithm();
    if (A.size > 50) {
        res = multiply_karatsuba(A, B);
    } else {
        res = multiply_normally(A, B);
    }
    str_reverse(res);
    for(int i = 0; i < res.size; ++i) {
        printf("%c", res.values[i] + '0');
    }
    return 0;
}