Incomplete long arithmetics

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <csignal>

using std::cout;
using std::endl;
using vint = std::vector<int>;

int const kBase = 100;
size_t const kPrecision = 10;

std::ostream & operator<<(std::ostream & out, vint xs)
{
    for (auto it = xs.rbegin(); it != xs.rend(); ++it)
    {
        if (*it < 10 && it != xs.rbegin())
            out << '0';
        out << *it;
    }
    return out;
}

vint operator+(vint const & a, vint const & b)
{
    if (a.size() == 0)
        return b;
    if (b.size() == 0)
        return a;

    vint result;
    result.reserve(std::max(a.size(), b.size()) + 1);

    bool carry = false;
    for (size_t i = 0, j = 0; i < a.size() || j < b.size(); ++i, ++j)
    {
        auto x = i >= a.size() ? 0 : a[i];
        auto y = j >= b.size() ? 0 : b[j];
        auto sum = x + y + carry;
        sum -= (carry = sum >= kBase) * kBase;
        result.push_back(sum);
    }
    if (carry)
        result.push_back(1);

    return result;
}

vint operator-(vint const & a, vint const & b)
{
    if (a.size() == 0)
        return b;
    if (b.size() == 0)
        return a;

    vint result;

    size_t carry = 0;
    bool borrow = false;
    for (size_t i = 0; i < a.size(); ++i)
    {
        auto y = i >= b.size() ? 0 : b[i];
        int sub;
        if (carry > 0)
        {
            sub = a[i] + kBase - y - 1;
            --carry;
        }
        else
        {
            if (a[i]-borrow >= y)
            {
                sub = a[i]-borrow - y;
                borrow = false;
            }
            else
            {
                while (a[i + ++carry] == 0);
                sub = a[i]-borrow + kBase - y;
                --carry;
                borrow = true;
            }
        }
        result.push_back(sub);
    }
    for (auto it = result.rbegin(); it != result.rend() && *it == 0;)
        result.erase(--(it++).base());

    return result;
}

static vint multiplyHelper(vint const & a, int x, size_t shift)
{
    vint result;
    result.reserve(a.size() + 1 + shift);

    for (size_t i = 0; i < shift; ++i)
        result.push_back(0);

    int carry = 0;
    for (size_t i = 0; i < a.size(); ++i)
    {
        auto prod = a[i] * x + carry;
        carry = prod / kBase;
        prod %= kBase;
        result.push_back(prod);
    }
    if (carry != 0)
        result.push_back(carry);
//    while (carry != 0)
//    {
//        result.push_back(carry % kBase);
//        carry /= kBase;
//    }

    return result;
}

vint operator*(vint const & a, vint const & b)
{
    if (a.size() == 0 || b.size() == 0)
        return {};

    vint result {};
    for (size_t i = 0; i < b.size(); ++i)
        result = result + multiplyHelper(a, b[i], i);

    return result;
}

bool operator==(vint const & a, vint const & b)
{
    if (a.size() != b.size())
    {
        return false;
    }
    for (size_t i = 0; i < a.size(); ++i)
    {
        if (a[i] != b[i])
            return false;
    }
    return true;
}

bool operator!=(vint const & a, vint const & b)
{
    return !(a == b);
}

vint shiftRight(vint x, size_t n)
{
    for (size_t i = 0; i < n; ++i)
        x.insert(x.begin(), 0);
    return x;
}

vint shiftLeft(vint x, size_t n)
{
    for (size_t i = 0; i < n; ++i)
        x.erase(x.begin());
    return x;
}

vint operator/(vint const & a, vint const & b)
{    
    if (a.size() == 0)
        return {};
    if (b.size() == 0)
        raise(SIGFPE);

    size_t shift = b.size() + kPrecision;
    vint two {2};
    two = shiftRight(two, shift);
    vint x {1};
    x = shiftRight(x, kPrecision);
    vint b1 = shiftRight(b, shift);

    vint oldX;
    do
    {
        oldX = x;
        x = shiftLeft(x * (two - shiftLeft(b1 * x, shift)), shift);
    }
    while (x != oldX);

    return shiftLeft(x * a, shift);
}

vint operator%(vint const & a, vint const & b)
{
    return a - (a / b) * b;
}

int main()
{
    {
        vint a {25, 34, 12};
        vint b {87, 16};

        vint q = a / b;
        vint r = a % b;
        cout << a << " = " << b << " * " << q << " + " << r << endl;
    }
    {
        vint a {34, 18, 98, 45, 34, 9, 4, 32, 25, 34, 12};
        vint b {88, 43, 5, 87, 16};

        vint q = a / b;
        vint r = a % b;
        cout << a << " = " << b << " * " << q << " + " << r << endl;
    }

}