karatsuba

// Karatsuba.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <random>
#include <limits>
#include <ctime>
using namespace std;
random_device rd;
mt19937_64 eng(rd());
uniform_int_distribution<long long> distr;
using verylong = vector <long long>;

// заранее считаем, что генерируемые числа существуют в формате от младших разрядов к старшим

void addZeros(verylong &one, verylong &two) {
    if (one.size() < two.size())
        for (int i = one.size(); i < two.size(); i++ )
            one.push_back(0);
    if (one.size() > two.size())
        for (int i = two.size(); i < one.size(); i++)
            two.push_back(0);
    if (one.size() % 2 != 0) {
        one.push_back(0);
        two.push_back(0);
    }
}
verylong summary(verylong a, verylong b) {
    addZeros(a, b);
    verylong c; int temp=0;
    for (int i = 0; i < a.size(); i++) {
        c.push_back(((a[i] + b[i] + temp) % 10) );
        if (a[i] + b[i] + temp >= 10) temp = 1;
        else temp = 0;
    }
    return c;
}

verylong sub(verylong a, verylong b) {
    addZeros(a, b);
    verylong c; int temp=0;
    for (int i = 0; i < a.size(); i++) {

        if (a[i] - b[i] - temp < 0) {
            a[i] += 10;
            c.push_back((a[i] - b[i] - temp));
            temp = 1;
        }
        else {
            c.push_back((a[i] - b[i] - temp));
            temp = 0;
        }
    }
    return c;
}

void split(verylong num, verylong& part1, verylong& part2) {
    for (int i = 0; i < num.size()/2; i++)
        part2.push_back(num[i]);
    for (int i = num.size()/2; i < num.size(); i++)
        part1.push_back(num[i]);
}
verylong addZerocForKaratsuba(verylong num, long long n) {
    verylong temp;
    temp.resize(num.size() + n);
    for (int i = 0; i < n; i++) temp[i] = 0;
    for (int i = n; i < temp.size(); i++) temp[i] = num[i - n];
    return temp;
}
verylong karatsuba(verylong x, verylong y) {
    verylong a, b, c, d;


    if (x.size() == 1 && y.size() == 1) {
        long long temp = x[0] * y[0];
        verylong result;
        if (temp > 10) {
            result.resize(2);
            result[0] = temp / 10;
            result[1] = temp % 10;
        }
        else {
            result.resize(1);
            result[0] = temp;

        }
        return result;
    }
    long long n = x.size();
    addZeros(x, y);
    split(x, a, b);
    split(y, c, d);
    verylong karatcubaAC = karatsuba(a, c); verylong karatcubaBD = karatsuba(b, d);
    verylong term1= addZerocForKaratsuba(karatcubaAC, n);
    verylong term2 = addZerocForKaratsuba(sub(karatsuba(summary(a, b), summary(c, d)), summary(karatcubaAC, karatcubaBD)), n / 2);
    verylong term3 = karatcubaBD;
    return summary(summary(term1, term2), term3);
}
int main()
{
    srand(time(NULL));
    verylong X; verylong Y;
    long long int width = 3;
    const int tests = 1000;
    /*for (int i = 0; i < tests; i++) {*/
        /*width = distr(eng);*/
        for (int j = 0; j < width; j++) {
            X.push_back(rand() % 10);
            Y.push_back(rand() % 10);
        }

    /*}*/
        verylong katat = karatsuba(X, Y);
        for (int k = 0; k < width; k++)
            cout << X[k];
        cout << endl;
        for (int k = 0; k < width; k++)
            cout << Y[k];
        for (int k = 0; k < width; k++)
            cout << katat[k];

}