vint.cpp

#include "vint.h"

#if defined(NDEBUG) || defined(QT_NO_DEBUG)
#define assume(cond) do { if (!(cond)) __builtin_unreachable(); } while (0)
#define assert_d(cond) {}
#else
#include <cassert>
#define assume(cond) assert(cond)
#define assert_d(cond) assert(cond)
#endif
#define LIKELY(x) __builtin_expect(!!(x), true)
#define UNLIKELY(x) __builtin_expect(!!(x), false)

#define LOW(x) (x & MAX_MAXV_INT_LOWER_HALF)
#define HIGH(x) (x >> (MAXV_INT_BIT_SIZE/2))
#define COMBINE(h, l) ((h << (MAXV_INT_BIT_SIZE/2)) + l)

#define ILOG2S(x) ((sizeof(sizeint) * 8 - 1) - S_MSB_FIND(x))
#define ILOG2V(x) ((sizeof(maxuint) * 8 - 1) - V_MSB_FIND(x))

vint::vint()
{
    valSize = 1;
    integer = (maxuint*)malloc(sizeof (maxuint));
}

vint::vint(maxint i)
{
    valSize = 1;
    integer = (maxuint*)malloc(sizeof (maxuint));
    if(i < 0)
    {
        sign = Negative;
        integer[0] = -i;
    }
    else
    {
        sign = Positive;
        integer[0] = i;
    }
}

vint::vint(maxuint i)
{
    valSize = 1;
    integer = (maxuint*)malloc(sizeof (maxuint));
    sign = Positive;
    integer[0] = i;
}

vint::vint(stdint i)
{
    valSize = 1;
    integer = (maxuint*)malloc(sizeof (maxuint));
    if(i < 0)
    {
        sign = Negative;
        integer[0] = -i;
    }
    else
    {
        sign = Positive;
        integer[0] = i;
    }
}

vint::vint(stduint i)
{
    valSize = 1;
    integer = (maxuint*)malloc(sizeof (maxuint));
    sign = Positive;
    integer[0] = i;
}

vint::vint(const vint &c)
{
    valSize = c.valSize;
    sign = c.sign;
    integer = (maxuint*)malloc(valSize * sizeof (maxuint));
    std::memcpy(integer, c.integer, valSize * sizeof (maxuint));
}

vint &vint::operator=(const vint &c)
{
    free(integer);
    valSize = c.valSize;
    sign = c.sign;
    integer = (maxuint*)malloc(valSize * sizeof (maxuint));
    std::memcpy(integer, c.integer, valSize * sizeof (maxuint));
    return *this;
}

vint &vint::operator=(maxint i)
{
    free(integer);
    valSize = 1;
    integer = (maxuint*)malloc(sizeof (maxuint));
    if(i < 0)
    {
        sign = Negative;
        integer[0] = -i;
    }
    else
    {
        sign = Positive;
        integer[0] = i;
    }
    return *this;
}

vint &vint::operator=(maxuint i)
{
    free(integer);
    valSize = 1;
    integer = (maxuint*)malloc(sizeof (maxuint));
    sign = Positive;
    integer[0] = i;
    return *this;
}

vint &vint::operator=(stdint i)
{
    return operator=(maxint(i));
}

vint &vint::operator=(stduint i)
{
    return operator=(maxuint(i));
}

vint::~vint()
{
    free(integer);
}

vint::operator bool() const
{
    assume(valSize > 0);
    for(sizeint i(0); i < valSize; i++)
    {
        if(integer[i])
            return true;
    }
    return false;
}

#ifdef AUTHORIZE_EXTERNAL_ACCESS_TO_VINT
sizeint vint::getValSize() const
{
    return valSize;
}

bool vint::getSign() const
{
    return sign;
}

maxuint* vint::getInteger() const
{
    return integer;
}

void vint::setSign(bool sign)
{
    this->sign = (Sign)sign;
}

void vint::setSize(sizeint s)
{
    resize(s);
}

void vint::setInteger(sizeint size, maxuint* newInteger)
{
    free(integer);
    valSize = size;
    integer = newInteger;
}

void vint::copyInteger(sizeint size, maxuint* newInteger)
{
    free(integer);
    valSize = size;
    integer = (maxuint*)malloc(sizeof (maxuint));
    memcpy(integer, newInteger, valSize * sizeof(maxuint));
}
#endif

vint::operator maxuint() const
{
    return integer[0];
}

vint::operator maxint() const
{
    if(sign == Positive)
        return integer[0];
    else
        return -((maxint)integer[0]);
}

vint::operator stduint() const
{
    return integer[0];
}

vint::operator stdint() const
{
    if(sign == Positive)
        return integer[0];
    else
        return -((maxint)integer[0]);
}

vint &vint::operator+=(const vint &a)
{
    add(a, Sign::Positive);
    return *this;
}

vint &vint::operator+=(maxint i)
{
    add(i, Sign::Positive);
    return *this;
}

vint &vint::operator+=(stdint i)
{
    return operator+=(maxint(i));
}

vint &vint::operator+=(maxuint i)
{
    addAbs(i);
    return *this;
}

vint &vint::operator+=(stduint i)
{
    return operator+=(maxuint(i));
}

vint &vint::operator-=(const vint &a)
{
    add(a, Sign::Negative);
    return *this;
}

vint &vint::operator-=(maxint i)
{
    add(i, Sign::Negative);
    return *this;
}

vint &vint::operator-=(stdint i)
{
    return operator-=(maxint(i));
}

vint &vint::operator-=(maxuint i)
{
    removeAbs(i);
    return *this;
}

vint &vint::operator-=(stduint i)
{
    return operator-=(maxuint(i));
}

vint &vint::operator*=(const vint &a)
{
    *this = multiply(*this, a);
    return *this;
}

vint &vint::operator*=(maxint i)
{
    *this = multiply(*this, i);
    return *this;
}

vint &vint::operator*=(stdint i)
{
    return operator*=(maxint(i));
}

vint &vint::operator*=(maxuint i)
{
    *this = multiply(*this, i);
    return *this;
}

vint &vint::operator*=(stduint i)
{
    return operator*=(maxuint(i));
}

vint &vint::operator/=(const vint &a)
{
    *this = divide(*this, a);
    return *this;
}

vint &vint::operator/=(maxint i)
{
    *this = divide(*this, i);
    return *this;
}

vint &vint::operator/=(stdint i)
{
    return operator/=(maxint(i));
}

vint &vint::operator/=(maxuint i)
{
    *this = divide(*this, i);
    return *this;
}

vint &vint::operator/=(stduint i)
{
    return operator/=(maxuint(i));
}

vint &vint::operator%=(const vint &a)
{
    *this = modulo(*this, a);
    return *this;
}

vint &vint::operator%=(maxint i)
{
    *this = modulo(*this, i);
    return *this;
}

vint &vint::operator%=(stdint i)
{
    return operator%=(maxint(i));
}

vint &vint::operator%=(maxuint i)
{
    *this = modulo(*this, i);
    return *this;
}

vint &vint::operator%=(stduint i)
{
    return operator%=(maxuint(i));
}

vint &vint::operator<<=(maxuint i)
{
    if(i >= MAXV_INT_BIT_SIZE)
    {
        if(i % MAXV_INT_BIT_SIZE)
        {
            *this = this->leftShiftMax(i / MAXV_INT_BIT_SIZE).leftShift(i % MAXV_INT_BIT_SIZE);
        }
        else
        {
            *this = this->leftShiftMax(i / MAXV_INT_BIT_SIZE);
        }
    }
    else
    {
        if(i % MAXV_INT_BIT_SIZE)
        {
            *this = this->leftShift(i % MAXV_INT_BIT_SIZE);
        }
    }
    return *this;
}

vint &vint::operator<<=(stduint i)
{
    return operator<<=(maxuint(i));
}

vint &vint::operator<<=(maxint i)
{
    return operator<<=(maxuint(i));
}

vint &vint::operator<<=(stdint i)
{
    return operator<<=(maxint(i));
}

vint &vint::operator>>=(maxuint i)
{
    if(i >= MAXV_INT_BIT_SIZE)
    {
        if(i % MAXV_INT_BIT_SIZE)
        {
            *this = this->rightShiftMax(i / MAXV_INT_BIT_SIZE).rightShift(i % MAXV_INT_BIT_SIZE);
        }
        else
        {
            *this = this->rightShiftMax(i / MAXV_INT_BIT_SIZE);
        }
    }
    else
    {
        if(i % MAXV_INT_BIT_SIZE)
        {
            *this = this->rightShift(i % MAXV_INT_BIT_SIZE);
        }
    }
    return *this;
}

vint &vint::operator>>=(stduint i)
{
    return operator>>=(maxuint(i));
}

vint &vint::operator>>=(maxint i)
{
    return operator>>=(maxuint(i));
}

vint &vint::operator>>=(stdint i)
{
    return operator>>=(maxint(i));
}

vint &vint::operator&=(const vint &a)
{
    sizeint minSize(V_min(a.valSize, valSize));
    assume(minSize > 0);
    sizeint i(0);
    for(; i < minSize; i++)
    {
        integer[i] &= a.integer[i];
    }
    assume(valSize > 0);
    for(; i < valSize; i++)
    {
        integer[i] = 0;
    }
    return *this;
}

vint &vint::operator&=(maxint i)
{
    return operator&=(maxuint(i));
}

vint &vint::operator&=(stdint i)
{
    return operator&=(maxuint(i));
}

vint &vint::operator&=(maxuint i)
{
    integer[0] &= i;
    assume(valSize > 0);
    for(sizeint i(1); i < valSize; i++)
    {
        integer[i] = 0;
    }
    return *this;
}

vint &vint::operator&=(stduint i)
{
    return operator&=(maxuint(i));
}

vint &vint::operator|=(const vint &a)
{
    if(valSize < a.valSize)
        resize(a.valSize);
    sizeint minSize(V_min(a.valSize, valSize));
    assume(minSize > 0);
    for(sizeint i(0); i < minSize; i++)
    {
        integer[i] |= a.integer[i];
    }
    return *this;
}

vint &vint::operator|=(maxint i)
{
    return operator|=(maxuint(i));
}

vint &vint::operator|=(stdint i)
{
    return operator|=(maxuint(i));
}

vint &vint::operator|=(maxuint i)
{
    integer[0] |= i;
    return *this;
}

vint &vint::operator|=(stduint i)
{
    return operator|=(maxuint(i));
}

vint &vint::operator^=(const vint &a)
{
    if(valSize < a.valSize)
        resize(a.valSize);
    sizeint minSize(V_min(a.valSize, valSize));
    assume(minSize > 0);
    for(sizeint i(0); i < minSize; i++)
    {
        integer[i] ^= a.integer[i];
    }
    return *this;
}

vint &vint::operator^=(maxint i)
{
    return operator^=(maxuint(i));
}

vint &vint::operator^=(stdint i)
{
    return operator^=(maxuint(i));
}

vint &vint::operator^=(maxuint i)
{
    integer[0] ^= i;
    return *this;
}

vint &vint::operator^=(stduint i)
{
    return operator^=(maxuint(i));
}

vint vint::operator~() const
{
    vint copy(*this);
    assume(valSize > 0);
    for(sizeint i(0); i < valSize; i++)
    {
        copy.integer[i] = ~integer[i];
    }
    return copy;
}

vint &vint::operator--()
{
    operator-=(1);
    return *this;
}

vint vint::operator--(int)
{
    vint old = *this;
    operator--();
    return old;
}

vint &vint::operator++()
{
    operator+=(1);
    return *this;
}

vint vint::operator++(int)
{
    vint old = *this;
    operator++();
    return old;
}

void vint::invertSign()
{
    sign = INV_SIGN(sign);
}

vint::vint(sizeint vs, vint::Sign s, maxuint *i)
{
    valSize = vs;
    sign = s;
    integer = i;
}

vint::vint(const vint &high, const vint &low)
{
    assume(high.valSize == low.valSize);
    assume(high.sign == Positive);
    assume(high.sign == Positive);
    valSize = high.valSize * 2;
    sign = Positive;
    integer = (maxuint*)malloc(valSize * sizeof (maxuint));
    std::memcpy(integer, low.integer, low.valSize * sizeof (maxuint));
    std::memcpy(integer + low.valSize, high.integer, high.valSize * sizeof (maxuint));
}

vint::vint(const vint &upper, const vint &high, const vint &low)
{
    assume(upper.valSize == high.valSize);
    assume(upper.valSize == low.valSize);
    assume(upper.sign == Positive);
    assume(high.sign == Positive);
    assume(low.sign == Positive);
    valSize = upper.valSize * 4;
    sign = Positive;
    integer = (maxuint*)malloc(valSize * sizeof (maxuint));
    std::memcpy(integer, low.integer, low.valSize * sizeof (maxuint));
    std::memcpy(integer + low.valSize, high.integer, high.valSize * sizeof (maxuint));
    std::memcpy(integer + low.valSize + high.valSize, upper.integer, upper.valSize * sizeof (maxuint));
    std::memset(integer + low.valSize + high.valSize + upper.valSize, 0, upper.valSize * sizeof (maxuint));
}

vint::vint(const vint &highHigh, const vint &highLow, const vint &lowHigh, const vint &lowLow)
{
    assume(highHigh.valSize == highLow.valSize);
    assume(highHigh.valSize == lowHigh.valSize);
    assume(highHigh.valSize == lowLow.valSize);
    assume(highHigh.sign == Positive);
    assume(highLow.sign == Positive);
    assume(lowHigh.sign == Positive);
    assume(lowLow.sign == Positive);
    valSize = highHigh.valSize * 4;
    sign = Positive;
    integer = (maxuint*)malloc(valSize * sizeof (maxuint));
    std::memcpy(integer, lowLow.integer, lowLow.valSize * sizeof (maxuint));
    std::memcpy(integer + lowLow.valSize, lowHigh.integer, lowHigh.valSize * sizeof (maxuint));
    std::memcpy(integer + lowLow.valSize + lowHigh.valSize, highLow.integer, highLow.valSize * sizeof (maxuint));
    std::memcpy(integer + lowLow.valSize + lowHigh.valSize + highLow.valSize, highHigh.integer, highHigh.valSize * sizeof (maxuint));
}

void vint::set(sizeint vs, vint::Sign s, maxuint *i)
{
    valSize = vs;
    sign = s;
    integer = i;
}

void vint::set(maxuint v)
{
    valSize = 1;
    sign = Positive;
    integer = (maxuint*)malloc(sizeof (maxuint));
    integer[0] = v;
}

void vint::set(const vint &v)
{
    maxuint *i((maxuint*)malloc(v.valSize * sizeof (maxuint)));
    std::memcpy(i, v.integer, v.valSize * sizeof(maxuint));
    set(v.valSize, v.sign, i);
}

void vint::set(const vint &high, const vint &low)
{
    maxuint *i((maxuint*)malloc((high.valSize + low.valSize) * sizeof (maxuint)));
    std::memcpy(i, low.integer, low.valSize * sizeof(maxuint));
    std::memcpy(i + low.valSize, high.integer, high.valSize * sizeof(maxuint));
    set(high.valSize + low.valSize, high.sign, i);
}

void vint::freeVintArray(vint *array, int size)
{
    while (size) {
        size--;
        array[size].~vint();
    }
    free(array);
}

void vint::resize(sizeint newSize)
{
    integer = (maxuint*)std::realloc(integer, newSize * sizeof (maxuint));
    if(newSize > valSize)
        memset(((char*)integer) + valSize * MAXV_INT_BYTE_SIZE, 0, (newSize - valSize) * MAXV_INT_BYTE_SIZE);
    valSize = newSize;
}

void vint::resizeUnsafe(sizeint newSize)
{
    integer = (maxuint*)std::realloc(integer, newSize * sizeof (maxuint));
    valSize = newSize;
}

void vint::add(const vint &a, vint::Sign sign)
{
    if(this->sign ^ (a.sign ^ sign))
        removeAbs(a);
    else
        addAbs(a);
}

void vint::add(maxint i, vint::Sign sign)
{
    if(this->sign ^ ((i < 0) ^ sign))
        removeAbs(i);
    else
        addAbs(i);
}

void vint::addAbs(const vint &a)
{
    if(valSize < a.valSize)
        resize(a.valSize);
    sizeint size(V_min(valSize, a.valSize));
    assume(size > 0);
    maxuint carry = 0;
    for (sizeint i = 0; i < size; i++) {
      maxuint tmp(a.integer[i] + carry);
      integer[i] += tmp;
      carry = (tmp < carry) + (integer[i] < tmp);
    }
    if(UNLIKELY(carry))
    {
        if(valSize == size)
            resize(valSize * 2);
        integer[size] += 1;
    }
}

void vint::removeAbs(const vint &a)
{
    if(valSize < a.valSize)
        resize(a.valSize);
    maxuint borrow = 0;
    if(absStrictSuperiority(*this, a))
    {
        //largest = this;
        //smallest = &a;
        for (sizeint i(0); i < a.valSize; ++i) {
            maxuint tmp((i < valSize ? integer[i] : 0) - borrow);
            integer[i] = tmp - a.integer[i];
            borrow = tmp < a.integer[i];
        }
        if(LIKELY(valSize > a.valSize))
            integer[a.valSize] -= borrow;
    }
    else
    {
        //largest = &a;
        //smallest = this;
        for (sizeint i(0); i < valSize; ++i) {
            maxuint tmp((i < a.valSize ? a.integer[i] : 0) - borrow);
            maxuint res(tmp - integer[i]);
            borrow = tmp < integer[i];
            integer[i] = res;
        }
        if(UNLIKELY(borrow)) {
            resize(valSize * 2);
            integer[valSize] -= borrow;
        }
        invertSign();
    }
}

void vint::addAbs(maxuint i)
{
    assume(valSize > 0);
    integer[0] += i;
    maxuint carry = (integer[0] < i);
    sizeint c(1);
    while(carry)
    {
        if(UNLIKELY(valSize == c))
        {
            resize(valSize * 2);
            integer[c] = 1;
            return;
        }
        integer[c]++;
        carry = (1 < carry) + (integer[c] < 1);
        c++;
    }
}

void vint::removeAbs(maxuint i)
{
    assume(valSize > 0);
    if(absStrictSuperiority(*this, i))
    {
        maxuint borrow = (integer[0] < i);
        integer[0] -= i;
        sizeint c(1);
        while(borrow)
        {
            if(UNLIKELY(valSize == c))
            {
                resize(valSize * 2);
                integer[c] = 1;
                return;
            }
            borrow = (integer[c] == 0);
            integer[c]--;
            c++;
        }
    }
    else
    {
        integer[0] = i - integer[0];
        invertSign();
    }
}

bool vint::absEquality(const vint &a, const vint &b)
{
    const vint *largest, *smallest;
    if(a.valSize > b.valSize)
    {
        largest = &a;
        smallest = &b;
    }
    else
    {
        largest = &b;
        smallest = &a;
    }
    assume(a.valSize > 0);
    assume(b.valSize > 0);
    for(sizeint i(largest->valSize-1); i >= smallest->valSize; i--)
    {
        if(LIKELY(largest->integer[i]))
            return false;
    }
    for(sizeint i(smallest->valSize); i > 0; i--)
    {
        if(UNLIKELY(largest->integer[i-1] == smallest->integer[i-1]))
            continue;
        return false;
    }
    return true;
}

bool vint::absEquality(const vint &a, maxuint b)
{
    assume(a.valSize > 0);
    for(sizeint i(a.valSize-1); i >= 1; i--)
    {
        if(LIKELY(a.integer[i]))
            return false;
    }
    return a.integer[0] == b;
}

bool vint::absEquality(maxuint a, const vint &b)
{
    return absEquality(b, a);
}

bool vint::absStrictSuperiority(const vint &a, const vint &b)
{
    const vint *largest, *smallest;
    bool inverted;
    if(a.valSize > b.valSize)
    {
        largest = &a;
        smallest = &b;
        inverted = false;
    }
    else
    {
        largest = &b;
        smallest = &a;
        inverted = true;
    }
    assume(a.valSize > 0);
    assume(b.valSize > 0);
    for(sizeint i(largest->valSize-1); i >= smallest->valSize; i--)
    {
        if(LIKELY(largest->integer[i]))
            return !inverted;
    }
    for(sizeint i(smallest->valSize); i > 0; i--)
    {
        if(UNLIKELY(largest->integer[i-1] == smallest->integer[i-1]))
            continue;
        return a.integer[i-1] > b.integer[i-1];
    }
    return false;
}

bool vint::absStrictSuperiority(const vint &a, maxuint b)
{
    assume(a.valSize > 0);
    for(sizeint i(a.valSize-1); i >= 1; i--)
    {
        if(LIKELY(a.integer[i]))
            return true;
    }
    return a.integer[0] > b;
}

bool vint::absStrictSuperiority(maxuint a, const vint &b)
{
    assume(b.valSize > 0);
    for(sizeint i(b.valSize-1); i >= 1; i--)
    {
        if(LIKELY(b.integer[i]))
            return false;
    }
    return a > b.integer[0];
}

vint vint::multiply(const vint &a, const vint &b)
{
    vint v(multiplyAbs(a, b));
    v.sign = (Sign)(a.sign ^ b.sign);
    return v;
}

vint vint::multiplyAbs(const vint &a, const vint &b)
{
    if(a.valSize < b.valSize)
    {
        vint copy(a);
        copy.resize(b.valSize);
        return karatsuba(copy, b);
    }
    else if(a.valSize > b.valSize)
    {
        vint copy(b);
        copy.resize(a.valSize);
        return karatsuba(a, copy);
    }
    return karatsuba(a, b);
}

vint vint::multiply(maxuint a, maxuint b)
{
    maxuint aLow, aHigh, bLow, bHigh;
    aLow = LOW(a);
    bLow = LOW(b);
    aHigh = HIGH(a);
    bHigh = HIGH(b);

    maxuint carry;
    maxuint resultLow(aLow * bLow), resultMiddle1(aHigh * bLow), resultMiddle2(aLow * bHigh), resultHigh(aHigh * bHigh);
    maxuint resultMiddle(resultMiddle1 + resultMiddle2);
    carry = resultMiddle < resultMiddle2;
    resultHigh += carry << (MAXV_INT_BIT_SIZE/2);
    resultLow += resultMiddle << (MAXV_INT_BIT_SIZE/2);
    carry = resultLow < (resultMiddle << (MAXV_INT_BIT_SIZE/2));
    resultHigh += carry;
    resultHigh += resultMiddle >> (MAXV_INT_BIT_SIZE/2);

    if(resultHigh)
    {
        maxuint* result = (maxuint*)malloc(2 * sizeof(maxuint));
        result[0] = resultLow;
        result[1] = resultHigh;
        return vint(2, Positive, result);
    }
    else
    {
        return vint(resultLow);
    }
}

vint vint::multiply(const vint &a, maxint b)
{
    vint v(multiplyAbs(a, maxuint(V_abs(b))));
    v.sign = (Sign)(a.sign ^ (b < 0));
    return v;
}

vint vint::multiply(const vint &a, maxuint b)
{
    vint v(multiplyAbs(a, b));
    v.sign = a.sign;
    return v;
}

vint vint::multiplyAbs(const vint &a, maxuint b)
{
    assume(a.valSize > 0);
    vint v(multiply(a.integer[0], b));
    if(v.valSize < a.valSize)
        v.resize(a.valSize);
    for(sizeint i(1); i < a.valSize; i++)
    {
        v += multiply(a.integer[i], b).leftShiftMax(i);
    }
    return v;
}

//https://en.wikipedia.org/wiki/Karatsuba_algorithm
vint vint::karatsuba(const vint &a, const vint &b)
{
    assume(a.valSize == b.valSize);

    if(a.valSize == 1) //&& b.valSize == 1
    {
        return multiply(a.integer[0], b.integer[0]);
    }

    assume(a.valSize % 2 == 0);
    assume(b.valSize % 2 == 0);

    vint highA, lowA, highB, lowB;
    a.split(lowA, highA);
    b.split(lowB, highB);
    lowA.sign = Positive;
    highA.sign = Positive;
    lowB.sign = Positive;
    highB.sign = Positive;

    vint z0(karatsuba(lowA, lowB));
    z0.sign = Positive;
    vint z2(karatsuba(highA, highB));
    z2.sign = Positive;
    vint aAdd(lowA + highA), bAdd(lowB + highB);
    vint z1;
    if(UNLIKELY(aAdd.valSize == a.valSize))
    {
        aAdd.split(lowA, highA);
        if(UNLIKELY(bAdd.valSize == b.valSize))
        {
            bAdd.split(lowB, highB);
            z1 = karatsubaCarry(lowA, lowB, true, true);
        }
        else
        {
            z1 = karatsubaCarry(lowA, bAdd, true, false);
        }
    }
    else
    {
        if(UNLIKELY(bAdd.valSize == b.valSize))
        {
            bAdd.split(lowB, highB);
            z1 = karatsubaCarry(aAdd, lowB, false, true);
        }
        else
        {
            z1 = karatsuba(aAdd, bAdd);
        }

    }
    z1.sign = Positive;

    return (z2.leftShiftMax(a.valSize)) + ((z1 - z2 - z0).leftShiftMax(a.valSize/2)) + z0;
}

vint vint::karatsubaCarry(const vint &a, const vint &b, bool aC, bool bC)
{
    assume(a.valSize == b.valSize);
    vint p(karatsuba(a, b));
    if(aC)
    {
        p += b.leftShiftMax(b.valSize);
    }
    if(bC)
    {
        p += a.leftShiftMax(a.valSize);
    }
    if(aC && bC)
    {
        p += vint(1).leftShiftMax(a.valSize*2);
    }
    return p;
}

void vint::split(vint &low, vint &high) const
{
    if(valSize <= 1)
        asm("NOP");
    assume(valSize > 1);
    assume(valSize % 2 == 0);
    sizeint halfSize(valSize/2);
    low.resizeUnsafe(halfSize);
    high.resizeUnsafe(halfSize);
    for(sizeint i(0); i < halfSize; i++)
    {
        low.integer[i] = integer[i];
        high.integer[i] = integer[i+halfSize];
    }
}

void vint::splitUnsafe(vint &low, vint &high) const
{
    assume(valSize > 1);
    assume(valSize % 2 == 0);
    sizeint halfSize(valSize/2);
    low.set(halfSize, sign, (maxuint*)malloc(halfSize * sizeof(maxuint)));
    high.set(halfSize, sign, (maxuint*)malloc(halfSize * sizeof(maxuint)));
    for(sizeint i(0); i < halfSize; i++)
    {
        low.integer[i] = integer[i];
        high.integer[i] = integer[i+halfSize];
    }
}

void vint::split(vint &lowLow, vint &lowHigh, vint &highLow, vint &highHigh) const
{
    assume(valSize > 1);
    assume(valSize % 4 == 0);
    sizeint quadSize(valSize/4);
    lowLow.resizeUnsafe(quadSize);
    lowHigh.resizeUnsafe(quadSize);
    highLow.resizeUnsafe(quadSize);
    highHigh.resizeUnsafe(quadSize);
    for(sizeint i(0); i < quadSize; i++)
    {
        lowLow.integer[i] = integer[i];
        lowHigh.integer[i] = integer[i+quadSize];
        highLow.integer[i] = integer[i+quadSize*2];
        highHigh.integer[i] = integer[i+quadSize*3];
    }
}

void vint::splitUnsafe(vint &lowLow, vint &lowHigh, vint &highLow, vint &highHigh) const
{
    assume(valSize > 1);
    assume(valSize % 4 == 0);
    sizeint quadSize(valSize/4);
    lowLow.set(quadSize, sign, (maxuint*)malloc(quadSize * sizeof(maxuint)));
    lowHigh.set(quadSize, sign, (maxuint*)malloc(quadSize * sizeof(maxuint)));
    highLow.set(quadSize, sign, (maxuint*)malloc(quadSize * sizeof(maxuint)));
    highHigh.set(quadSize, sign, (maxuint*)malloc(quadSize * sizeof(maxuint)));
    for(sizeint i(0); i < quadSize; i++)
    {
        lowLow.integer[i] = integer[i];
        lowHigh.integer[i] = integer[i+quadSize];
        highLow.integer[i] = integer[i+quadSize*2];
        highHigh.integer[i] = integer[i+quadSize*3];
    }
}

vint vint::leftShiftMax(sizeint i) const
{
    assume(i > 0);
    sizeint currentSize(valSize);
    while (!integer[currentSize-1]) {
        currentSize--;
        if(!currentSize)
            return vint(maxuint(0));
    }
    sizeint targetSize(currentSize + i);
    sizeint iLog(1 << ILOG2S(targetSize));
    if(targetSize != iLog)
        targetSize = iLog << 1;
    maxuint* shifted((maxuint*)calloc(targetSize, sizeof(maxuint)));
    memcpy(shifted + i, integer, currentSize * sizeof(maxuint));
    return vint(targetSize, sign, shifted);
}

vint vint::rightShiftMax(sizeint i) const
{
    assume(i > 0);
    if(i >= valSize)
        return vint(maxuint(0));
    vint copy(valSize, sign, (maxuint*)calloc(valSize, sizeof(maxuint)));
    memcpy(copy.integer, integer + i, (valSize - i) * sizeof(maxuint));
    //memset(copy.integer + valSize - i, 0, i * sizeof(maxuint));
    return copy;
}

vint vint::leftShift(sizeint i) const
{
    assume(i > 0);
    assume(i < MAXV_INT_BIT_SIZE);
    sizeint ri(MAXV_INT_BIT_SIZE-i);
    vint copy(*this);
    if(copy.integer[copy.valSize - 1])
    {
        if(i > sizeint(V_MSB_FIND(copy.integer[copy.valSize - 1])))
        {
            copy.resize(copy.valSize * 2);
        }
    }
    copy.integer[copy.valSize-1] <<= i;
    for(sizeint s(copy.valSize-1); s > 0; s--)
    {
        copy.integer[s] |= copy.integer[s-1] >> ri;
        copy.integer[s-1] <<= i;
    }
    return copy;
}

vint vint::rightShift(sizeint i) const
{
    assume(i > 0);
    assume(i < MAXV_INT_BIT_SIZE);
    sizeint ri(MAXV_INT_BIT_SIZE-i);
    vint copy(*this);
    copy.integer[0] >>= i;
    for(sizeint s(1); s < valSize; s++)
    {
        copy.integer[s-1] |= copy.integer[s] << ri;
        copy.integer[s] >>= i;
    }
    return copy;
}

vint vint::divide(const vint &a, const vint &b)
{
    vint v(burnikelZieglerDivide(a, b));
    v.sign = (Sign)(a.sign ^ b.sign);
    return v;
}

vint vint::modulo(const vint &a, const vint &b)
{
    vint v(burnikelZieglerModulo(a, b));
    v.sign = a.sign;
    return v;
}

vint vint::burnikelZieglerDivide(const vint &a, const vint &b)
{
    vint* buffer((vint*)malloc(2 * sizeof(vint)));
    burnikelZiegler(a, b, buffer);
    vint quotient(buffer[0]);
    freeVintArray(buffer, 2);
    return quotient;
}

vint vint::burnikelZieglerModulo(const vint &a, const vint &b)
{
    vint* buffer((vint*)malloc(2 * sizeof(vint)));
    burnikelZiegler(a, b, buffer);
    vint remainder(buffer[1]);
    freeVintArray(buffer, 2);
    return remainder;
}

//Found a PDF regarding that method and downloaded it at some point but I sadly can't find it again on the Internet to properly put a link here
//[quotient, remainder]
void vint::burnikelZiegler(vint a, vint b, vint *outputBuffer)
{
    //Error: dividing by 0
    assert_d((bool)b);
    sizeint bRequiredSize(V_max(a.valSize/2, b.valSize));
    if(a.valSize != bRequiredSize*2)
    {
        a.resize(bRequiredSize*2);
    }
    else if(b.valSize != bRequiredSize)
    {
        b.resize(bRequiredSize);
    }
    sizeint maxShiftL(0), shiftL;
    while (!b.integer[b.valSize - maxShiftL - 1]) {
        maxShiftL++;
    }
    shiftL = V_MSB_FIND(b.integer[b.valSize - maxShiftL - 1]);
    b <<= MAXV_INT_BIT_SIZE * maxShiftL + shiftL;
    assert_d(b.integer[b.valSize - 1] >> 63);
    assert_d((bool)b);
    sizeint aInitialSize(a.valSize);
    a <<= MAXV_INT_BIT_SIZE * maxShiftL + shiftL;
    if(a.valSize < aInitialSize)
        a.resize(aInitialSize);
    maxuint* carries((maxuint*)calloc(a.valSize, sizeof (maxuint)));
    if(a.valSize == bRequiredSize*4)
    {
        vint* buffer((vint*)malloc(12 * sizeof(vint)));
        vint aHighHigh, aHighLow, aLowHigh, aLowLow;
        a.split(aLowLow, aLowHigh, aHighLow, aHighHigh);
        aHighHigh.sign = Positive;
        aHighLow.sign = Positive;
        aLowHigh.sign = Positive;
        aLowLow.sign = Positive;
        bZDivTwoLongDigitsByOne(aHighHigh, aHighLow, b, buffer, carries, b.valSize*3);
        buffer[0].sign = Positive;
        buffer[1].sign = Positive;
        buffer[2].sign = Positive;
        buffer[3].sign = Positive;
        if(a.valSize == 4)
        {
            assert_d(!(bool)buffer[2]);
            bZDivTwoLongDigitsByOne(buffer[3], aLowHigh, b, buffer+4, carries, b.valSize*2);
            buffer[4].sign = Positive;
            buffer[5].sign = Positive;
            buffer[6].sign = Positive;
            buffer[7].sign = Positive;
            assert_d(!(bool)buffer[6]);
            bZDivTwoLongDigitsByOne(buffer[7], aLowLow, b, buffer+8, carries, b.valSize);
            buffer[8].sign = Positive;
            buffer[9].sign = Positive;
            buffer[10].sign = Positive;
            buffer[11].sign = Positive;
            assert_d(!(bool)buffer[0]);
            assert_d(!(bool)buffer[4]);
            assert_d(!(bool)buffer[8]);
            outputBuffer[0].set(vint(buffer[1], buffer[5], buffer[9])); //q
        }
        else
        {
            bZDivTwoLongDigitsByOne(vint(buffer[2], buffer[3]), aLowHigh, b, buffer+4, carries, b.valSize*2);
            buffer[4].sign = Positive;
            buffer[5].sign = Positive;
            buffer[6].sign = Positive;
            buffer[7].sign = Positive;
            bZDivTwoLongDigitsByOne(vint(buffer[6], buffer[7]), aLowLow, b, buffer+8, carries, b.valSize);
            buffer[8].sign = Positive;
            buffer[9].sign = Positive;
            buffer[10].sign = Positive;
            buffer[11].sign = Positive;
            outputBuffer[0].set(vint(vint(buffer[0], buffer[1]), vint(buffer[4], buffer[5]), vint(buffer[8], buffer[9]))); //q
        }
        outputBuffer[1].set(vint(buffer[10], buffer[11])); //r
        outputBuffer[1] >>= MAXV_INT_BIT_SIZE * maxShiftL + shiftL;
        freeVintArray(buffer, 12);
    }
    else //a.valSize == bRequiredSize*2
    {
        vint* buffer((vint*)malloc(4 * sizeof(vint)));
        vint aHigh, aLow;
        a.split(aLow, aHigh);
        aLow.sign = Positive;
        aHigh.sign = Positive;
        bZDivTwoLongDigitsByOne(aHigh, aLow, b, buffer, carries, b.valSize);
        buffer[0].sign = Positive;
        buffer[1].sign = Positive;
        buffer[2].sign = Positive;
        buffer[3].sign = Positive;
        outputBuffer[0].set(vint(buffer[0], buffer[1])); //q
        outputBuffer[1].set(vint(buffer[2], buffer[3])); //r
        outputBuffer[1] >>= MAXV_INT_BIT_SIZE * maxShiftL + shiftL;
        freeVintArray(buffer, 4);
    }
    vint carriesVint(a.valSize, Positive, carries);
    outputBuffer[0] += carriesVint;
}

//aHigh, aLow, b require Nbits
//[quotient high (N/2)bits, quotient low (N/2)bits, remainder high (N/2)bits, remainder low (N/2)bits]
void vint::bZDivTwoLongDigitsByOne(vint const& aHigh, vint const& aLow, vint const& b, vint *outputBuffer, maxuint* carries, sizeint carryPos)
{
    if(!((bool)aHigh) && aLow < b)
    {
        outputBuffer[0].set(0);
        outputBuffer[1].set(0);
        if(aLow.valSize == 1)
        {
            outputBuffer[2].set(0); //aHigh == 0
            outputBuffer[3].set(aLow.integer[0]);
        }
        else
        {
            aLow.splitUnsafe(outputBuffer[3], outputBuffer[2]); //aHigh == 0
            outputBuffer[0].resize(outputBuffer[2].valSize);
            outputBuffer[1].resize(outputBuffer[2].valSize);
        }
    }
    else if(b.valSize == 1)
    {
        assume(aHigh.valSize == 1);
        assume(aLow.valSize == 1);
        maxuint buffer[5];
        bZDivTwoDigitsByOne(aHigh.integer[0], aLow.integer[0], b.integer[0], buffer);
        outputBuffer[0].set(buffer[0]);
        outputBuffer[1].set(COMBINE(buffer[1], buffer[2]));
        outputBuffer[2].set(0);
        outputBuffer[3].set(COMBINE(buffer[3], buffer[4]));
    }
    else
    {
        vint* buffer((vint*)malloc(6 * sizeof(vint)));
        vint aHighHigh, aHighLow, aLowHigh, aLowLow, bHigh, bLow;
        aHigh.split(aHighLow, aHighHigh);
        aHighHigh.sign = Positive;
        aHighLow.sign = Positive;
        aLow.split(aLowLow, aLowHigh);
        aLowHigh.sign = Positive;
        aLowLow.sign = Positive;
        b.split(bLow, bHigh);
        bHigh.sign = Positive;
        bLow.sign = Positive;
        bZDivThreeLongHalvesByTwo(aHighHigh, aHighLow, aLowHigh, bHigh, bLow, buffer, carries, carryPos);
        outputBuffer[0].set(buffer[0]);
        bZDivThreeLongHalvesByTwo(buffer[1], buffer[2], aLowLow, bHigh, bLow, buffer+3, carries, carryPos-1);
        outputBuffer[1].set(buffer[3]);
        outputBuffer[2].set(buffer[4]);
        outputBuffer[3].set(buffer[5]);
        freeVintArray(buffer, 6);
    }

    //std::cout << "\nA= " << to_hex(vint(aHigh, aLow)) << "\nB= " << to_hex(b) << "\nQ= " << to_hex(vint(outputBuffer[0], outputBuffer[1]))<< "\nR= " << to_hex(vint(outputBuffer[2], outputBuffer[3])) << std::endl;
}

//aUpper, aHigh, aLow, bHigh, bLow require (N/2)bits
//[quotient (N/2)bits, remainder high (N/2)bits, remainder low (N/2)bits]
void vint::bZDivThreeLongHalvesByTwo(vint const& aUpper, vint const& aHigh, vint const& aLow, vint const& bHigh, vint const& bLow, vint *outputBuffer, maxuint* carries, sizeint carryPos)
{
    //vint aUaH(aUpper, aHigh);
    //aUaH.sign = Positive;
    //vint q(aUaH / bHigh);
    vint* buffer((vint*)malloc(4 * sizeof(vint)));
    bZDivTwoLongDigitsByOne(aUpper, aHigh, bHigh, buffer, carries, carryPos);
    vint q, c;
    if(aUpper.valSize == 1)
    {
        if(UNLIKELY((bool)buffer[0]))
        {
            assert_d(buffer[0] == 1);
            carries[carryPos]++;
        }
        assert_d(!((bool)buffer[2]));
        q = buffer[1];
        c = buffer[3];
    }
    else
    {
        q = vint(buffer[0], buffer[1]);
        c = vint(buffer[2], buffer[3]);
    }
    q.sign = Positive;
    c.sign = Positive;
    vint d(q*bLow);
    d.sign = Positive;
    vint caL(c, aLow);
    caL.sign = Positive;
    if(UNLIKELY(caL < d)) //Borrow
    {
        --q;
        vint b(bHigh, bLow);
        b.sign = Positive;
        caL += b;
        if(UNLIKELY(caL < d)) //Borrow
        {
            --q;
            caL += b;
        }
    }
    vint r(caL - d);
    r.sign = Positive;
    outputBuffer[0].set(q);
    r.splitUnsafe(outputBuffer[2], outputBuffer[1]);
    outputBuffer[1].sign = Positive;
    outputBuffer[2].sign = Positive;
    freeVintArray(buffer, 4);
}

//aHigh, aLow, b require 64bits
//[quotient upper 1b, quotient high 32b, quotient low 32b, remainder high 32b, remainder low 32b]
void vint::bZDivTwoDigitsByOne(maxuint aHigh, maxuint aLow, maxuint b, maxuint* outputBuffer)
{
    //    (1) Let [a1,a2]=AH, [a3,a4]=AL, and [b1,b2]=B;
    //    (2) [q1,R]=DivThreeHalvesByTwo(a1,a2,a3,b1,b2);
    //    (3) Let [r1,r2]=R;
    //    (4) [q2,S]=DivThreeHalvesByTwo(r1,r2,a4,b1,b2);
    //    (5) Return the quotient Q=[q1,q2] and the remainder S;

    maxuint buffer[4];
    maxuint bHigh(HIGH(b)), bLow(LOW(b));
    bZDivThreeHalvesByTwo(HIGH(aHigh), LOW(aHigh), HIGH(aLow), bHigh, bLow, buffer);
    outputBuffer[0] = buffer[0];
    assert_d(outputBuffer[0] <= MAX_MAXV_INT_LOWER_HALF);
    outputBuffer[1] = buffer[1];
    assert_d(outputBuffer[1] <= MAX_MAXV_INT_LOWER_HALF);
    bZDivThreeHalvesByTwo(buffer[2], buffer[3], LOW(aLow), bHigh, bLow, buffer);
    outputBuffer[1] += buffer[0];
    assert_d(outputBuffer[1] <= MAX_MAXV_INT_LOWER_HALF);
    outputBuffer[2] = buffer[1];
    assert_d(outputBuffer[2] <= MAX_MAXV_INT_LOWER_HALF);
    outputBuffer[3] = buffer[2];
    assert_d(outputBuffer[3] <= MAX_MAXV_INT_LOWER_HALF);
    outputBuffer[4] = buffer[3];
    assert_d(outputBuffer[4] <= MAX_MAXV_INT_LOWER_HALF);
}

//aUpper, aHigh, aLow, bHigh, bLow require 32bits
//[quotient high 1b, quotient low 32b, remainder high 32b, remainder low 32b]
void vint::bZDivThreeHalvesByTwo(maxuint aUpper, maxuint aHigh, maxuint aLow, maxuint bHigh, maxuint bLow, maxuint* outputBuffer)
{
    assume(bHigh >= 0x80000000);
    assume(bHigh <= 0xFFFFFFFF);
    assume(aUpper <= 0xFFFFFFFF);
    assume(aHigh <= 0xFFFFFFFF);
    assume(aLow <= 0xFFFFFFFF);
    assume(bLow <= 0xFFFFFFFF);

    //    (6) Divide q = [a1,a2]/b1;
    //    (7) Let c=[a1,a2]-q*b1;
    //    (8) D = q*b2;
    //    (9) Let R:=[r1,r2]=[c,a3]-D
    //    (10) if (R<0) { // q is too large by at least one
    //    (11) q--;
    //    (12) R+=B;
    //    (13) if (R<0) { // q is still too large
    //    (14) q--;
    //    (15) R+=B; // now R is correct
    //    (16) }
    //    (17) }
    //    (18) Return the quotient q and the remainder R;

    maxuint aUaH(COMBINE(aUpper, aHigh));
    maxuint q(aUaH / bHigh);
    maxuint c(aUaH - q*bHigh);
    maxuint d(q*bLow);
    maxuint caL(COMBINE(c, aLow));
    if(UNLIKELY(caL < d)) //Borrow
    {
        q--;
        maxuint b(COMBINE(bHigh, bLow));
        caL += b;
        if(UNLIKELY(caL < d)) //Borrow
        {
            q--;
            caL += b;
        }
    }
    maxuint r(caL - d);
    outputBuffer[0] = HIGH(q);
    assert_d(outputBuffer[0] <= MAX_MAXV_INT_LOWER_HALF);
    outputBuffer[1] = LOW(q);
    assert_d(outputBuffer[1] <= MAX_MAXV_INT_LOWER_HALF);
    outputBuffer[2] = HIGH(r);
    assert_d(outputBuffer[2] <= MAX_MAXV_INT_LOWER_HALF);
    outputBuffer[3] = LOW(r);
    assert_d(outputBuffer[3] <= MAX_MAXV_INT_LOWER_HALF);
}

bool vint::toBoolWithoutLow(sizeint i) const
{
    assume(valSize > 0);
    for(; i < valSize; i++)
    {
        if(integer[i])
            return true;
    }
    return false;
}

std::ostream &operator<<(std::ostream &os, const vint& value)
{
    os << to_string(value);
    return os;
}

bool operator<(const vint &a, const vint &b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return false;
    //a != 0 || b != 0
    if(a.sign == vint::Positive && b.sign == vint::Negative)
        return false;
    else if(a.sign == vint::Negative && b.sign == vint::Positive)
        return true;
    else if(a.sign == vint::Positive && b.sign == vint::Positive)
        return vint::absStrictSuperiority(b, a);
    else
        return vint::absStrictSuperiority(a, b);
}

bool operator<(maxint a, const vint &b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return false;
    //a != 0 || b != 0
    if((a >= 0) && b.sign == vint::Negative)
        return false;
    else if((a <= 0) && b.sign == vint::Positive)
        return true;
    else if((a >= 0) && b.sign == vint::Positive)
        return vint::absStrictSuperiority(b, a);
    else
        return vint::absStrictSuperiority(-a, b);
}

bool operator<(const vint &a, maxint b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return false;
    //a != 0 || b != 0
    if(a.sign == vint::Positive && (b <= 0))
        return false;
    else if(a.sign == vint::Negative && (b >= 0))
        return true;
    else if(a.sign == vint::Positive && (b >= 0))
        return vint::absStrictSuperiority(b, a);
    else
        return vint::absStrictSuperiority(a, -b);
}

bool operator<(maxuint a, const vint &b)
{
    if(b.sign == vint::Negative)
        return false;
    return vint::absStrictSuperiority(b, a);
}

bool operator<(const vint &a, maxuint b)
{
    if(a.sign == vint::Negative)
        return true;
    return vint::absStrictSuperiority(b, a);
}

bool operator<(stdint a, const vint &b)
{
    return operator<(maxint(a), b);
}

bool operator<(const vint &a, stdint b)
{
    return operator<(a, maxint(b));
}

bool operator<(stduint a, const vint &b)
{
    return operator<(maxuint(a), b);
}

bool operator<(const vint &a, stduint b)
{
    return operator<(a, maxuint(b));
}

bool operator>(const vint &a, const vint &b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return false;
    //a != 0 || b != 0
    if(a.sign == vint::Positive && b.sign == vint::Negative)
        return true;
    else if(a.sign == vint::Negative && b.sign == vint::Positive)
        return false;
    else if(a.sign == vint::Positive && b.sign == vint::Positive)
        return vint::absStrictSuperiority(a, b);
    else
        return vint::absStrictSuperiority(b, a);
}

bool operator>(maxint a, const vint &b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return false;
    //a != 0 || b != 0
    if((a >= 0) && b.sign == vint::Negative)
        return true;
    else if((a <= 0) && b.sign == vint::Positive)
        return false;
    else if((a >= 0) && b.sign == vint::Positive)
        return vint::absStrictSuperiority(a, b);
    else
        return vint::absStrictSuperiority(b, -a);
}

bool operator>(const vint &a, maxint b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return false;
    //a != 0 || b != 0
    if(a.sign == vint::Positive && (b <= 0))
        return true;
    else if(a.sign == vint::Negative && (b >= 0))
        return false;
    else if(a.sign == vint::Positive && (b >= 0))
        return vint::absStrictSuperiority(a, b);
    else
        return vint::absStrictSuperiority(-b, a);
}

bool operator>(maxuint a, const vint &b)
{
    if(b.sign == vint::Negative)
        return true;
    return vint::absStrictSuperiority(a, b);
}

bool operator>(const vint &a, maxuint b)
{
    if(a.sign == vint::Negative)
        return false;
    return vint::absStrictSuperiority(a, b);
}

bool operator>(stdint a, const vint &b)
{
    return operator>(maxint(a), b);
}

bool operator>(const vint &a, stdint b)
{
    return operator>(a, maxint(b));
}

bool operator>(stduint a, const vint &b)
{
    return operator>(maxuint(a), b);
}

bool operator>(const vint &a, stduint b)
{
    return operator>(a, maxuint(b));
}

bool operator<=(const vint &a, const vint &b)
{
    if(a < b)
        return true;
    return a == b;
}

bool operator<=(maxint a, const vint &b)
{
    if(a < b)
        return true;
    return a == b;
}

bool operator<=(const vint &a, maxint b)
{
    if(a < b)
        return true;
    return a == b;
}

bool operator<=(maxuint a, const vint &b)
{
    if(a < b)
        return true;
    return a == b;
}

bool operator<=(const vint &a, maxuint b)
{
    if(a < b)
        return true;
    return a == b;
}

bool operator<=(stdint a, const vint &b)
{
    return operator<=(maxint(a), b);
}

bool operator<=(const vint &a, stdint b)
{
    return operator<=(a, maxint(b));
}

bool operator<=(stduint a, const vint &b)
{
    return operator<=(maxuint(a), b);
}

bool operator<=(const vint &a, stduint b)
{
    return operator<=(a, maxuint(b));
}

bool operator>=(const vint &a, const vint &b)
{
    if(a > b)
        return true;
    return a == b;
}

bool operator>=(maxint a, const vint &b)
{
    if(a > b)
        return true;
    return a == b;
}

bool operator>=(const vint &a, maxint b)
{
    if(a > b)
        return true;
    return a == b;
}

bool operator>=(maxuint a, const vint &b)
{
    if(a > b)
        return true;
    return a == b;
}

bool operator>=(const vint &a, maxuint b)
{
    if(a > b)
        return true;
    return a == b;
}

bool operator>=(stdint a, const vint &b)
{
    return operator>=(maxint(a), b);
}

bool operator>=(const vint &a, stdint b)
{
    return operator>=(a, maxint(b));
}

bool operator>=(stduint a, const vint &b)
{
    return operator>=(maxuint(a), b);
}

bool operator>=(const vint &a, stduint b)
{
    return operator>=(a, maxuint(b));
}

bool operator==(const vint &a, const vint &b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return true;
    if(a.sign != b.sign)
        return false;
    return vint::absEquality(a, b);
}

bool operator==(maxint a, const vint &b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return true;
    if((a < 0) != b.sign)
        return false;
    return vint::absEquality(V_abs(a), b);
}

bool operator==(const vint &a, maxint b)
{
    if(UNLIKELY((!(bool)a) && (!(bool)b)))
        return true;
    if(a.sign != (b < 0))
        return false;
    return vint::absEquality(a, V_abs(b));
}

bool operator==(maxuint a, const vint &b)
{
    if(b.sign == vint::Negative)
        return ((!(bool)a) && (!(bool)b));
    return vint::absEquality(a, b);
}

bool operator==(const vint &a, maxuint b)
{
    if(a.sign == vint::Negative)
        return ((!(bool)a) && (!(bool)b));
    return vint::absEquality(a, b);
}

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

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

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

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

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

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

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

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

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

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

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

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

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

vint operator+(const vint &a, const vint &b)
{
    vint r(a);
    r += b;
    return r;
}

vint operator+(maxint a, const vint &b)
{
    vint r(b);
    r += a;
    return r;
}

vint operator+(const vint &a, maxint b)
{
    return operator+(b, a);
}

vint operator+(maxuint a, const vint &b)
{
    vint r(b);
    r += a;
    return r;
}

vint operator+(const vint &a, maxuint b)
{
    return operator+(b, a);
}

vint operator+(stdint a, const vint &b)
{
    return operator+(maxint(a), b);
}

vint operator+(const vint &a, stdint b)
{
    return operator+(a, maxint(b));
}

vint operator+(stduint a, const vint &b)
{
    return operator+(maxuint(a), b);
}

vint operator+(const vint &a, stduint b)
{
    return operator+(a, maxuint(b));
}

vint operator-(const vint &a, const vint &b)
{
    vint r(a);
    r -= b;
    return r;
}

vint operator-(maxint a, const vint &b)
{
    vint r(b);
    r.invertSign();
    r += a;
    return r;
}

vint operator-(const vint &a, maxint b)
{
    vint r(a);
    r -= b;
    return r;
}

vint operator-(maxuint a, const vint &b)
{
    vint r(b);
    r.invertSign();
    r += a;
    return r;
}

vint operator-(const vint &a, maxuint b)
{
    vint r(a);
    r -= b;
    return r;
}

vint operator-(stdint a, const vint &b)
{
    return operator-(maxint(a), b);
}

vint operator-(const vint &a, stdint b)
{
    return operator-(a, maxint(b));
}

vint operator-(stduint a, const vint &b)
{
    return operator-(maxuint(a), b);
}

vint operator-(const vint &a, stduint b)
{
    return operator-(a, maxuint(b));
}

vint operator*(const vint &a, const vint &b)
{
    return vint::multiply(a, b);
}

vint operator*(maxint a, const vint &b)
{
    return operator*(b, a);
}

vint operator*(const vint &a, maxint b)
{
    return vint::multiply(a, b);
}

vint operator*(maxuint a, const vint &b)
{
    return operator*(b, a);
}

vint operator*(const vint &a, maxuint b)
{
    return vint::multiply(a, b);
}

vint operator*(stdint a, const vint &b)
{
    return operator*(maxint(a), b);
}

vint operator*(const vint &a, stdint b)
{
    return operator*(a, maxint(b));
}

vint operator*(stduint a, const vint &b)
{
    return operator*(maxuint(a), b);
}

vint operator*(const vint &a, stduint b)
{
    return operator*(a, maxuint(b));
}

vint operator/(const vint &a, const vint &b)
{
    return vint::divide(a, b);
}

vint operator/(maxint a, const vint &b)
{
    return vint::divide(a, b);
}

vint operator/(const vint &a, maxint b)
{
    return vint::divide(a, b);
}

vint operator/(maxuint a, const vint &b)
{
    return vint::divide(a, b);
}

vint operator/(const vint &a, maxuint b)
{
    return vint::divide(a, b);
}

vint operator/(stdint a, const vint &b)
{
    return operator/(maxint(a), b);
}

vint operator/(const vint &a, stdint b)
{
    return operator/(a, maxint(b));
}

vint operator/(stduint a, const vint &b)
{
    return operator/(maxuint(a), b);
}

vint operator/(const vint &a, stduint b)
{
    return operator/(a, maxuint(b));
}

vint operator%(const vint &a, const vint &b)
{
    return vint::modulo(a, b);
}

vint operator%(maxint a, const vint &b)
{
    return vint::modulo(a, b);
}

vint operator%(const vint &a, maxint b)
{
    return vint::modulo(a, b);
}

vint operator%(maxuint a, const vint &b)
{
    return vint::modulo(a, b);
}

vint operator%(const vint &a, maxuint b)
{
    return vint::modulo(a, b);
}

vint operator%(stdint a, const vint &b)
{
    return operator%(maxint(a), b);
}

vint operator%(const vint &a, stdint b)
{
    return operator%(a, maxint(b));
}

vint operator%(stduint a, const vint &b)
{
    return operator%(maxuint(a), b);
}

vint operator%(const vint &a, stduint b)
{
    return operator%(a, maxuint(b));
}

vint operator<<(const vint &a, maxint b)
{
    vint r(a);
    r <<= b;
    return r;
}

vint operator<<(const vint &a, maxuint b)
{
    vint r(a);
    r <<= b;
    return r;
}

vint operator<<(const vint &a, stdint b)
{
    vint r(a);
    r <<= b;
    return r;
}

vint operator<<(const vint &a, stduint b)
{
    vint r(a);
    r <<= b;
    return r;
}

vint operator>>(const vint &a, maxint b)
{
    vint r(a);
    r >>= b;
    return r;
}

vint operator>>(const vint &a, maxuint b)
{
    vint r(a);
    r >>= b;
    return r;
}

vint operator>>(const vint &a, stdint b)
{
    vint r(a);
    r >>= b;
    return r;
}

vint operator>>(const vint &a, stduint b)
{
    vint r(a);
    r >>= b;
    return r;
}

vint operator-(const vint &a)
{
    vint v(a);
    v.invertSign();
    return v;
}

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

vint operator&(maxint a, const vint &b)
{
    return operator&(maxuint(a), b);
}

vint operator&(const vint &a, maxint b)
{
    return operator&(b, a);
}

vint operator&(maxuint a, const vint &b)
{
    vint r(b);
    r &= a;
    return r;
}

vint operator&(const vint &a, maxuint b)
{
    return operator&(b, a);
}

vint operator&(stdint a, const vint &b)
{
    return operator&(maxint(a), b);
}

vint operator&(const vint &a, stdint b)
{
    return operator&(a, maxint(b));
}

vint operator&(stduint a, const vint &b)
{
    return operator&(maxuint(a), b);
}

vint operator&(const vint &a, stduint b)
{
    return operator&(a, maxuint(b));
}

vint operator|(const vint &a, const vint &b)
{
    vint r(a);
    r |= b;
    return r;
}

vint operator|(maxint a, const vint &b)
{
    return operator|(maxuint(a), b);
}

vint operator|(const vint &a, maxint b)
{
    return operator|(b, a);
}

vint operator|(maxuint a, const vint &b)
{
    vint r(b);
    r |= a;
    return r;
}

vint operator|(const vint &a, maxuint b)
{
    return operator|(b, a);
}

vint operator|(stdint a, const vint &b)
{
    return operator|(maxint(a), b);
}

vint operator|(const vint &a, stdint b)
{
    return operator|(a, maxint(b));
}

vint operator|(stduint a, const vint &b)
{
    return operator|(maxuint(a), b);
}

vint operator|(const vint &a, stduint b)
{
    return operator|(a, maxuint(b));
}

vint operator^(const vint &a, const vint &b)
{
    vint r(a);
    r ^= b;
    return r;
}

vint operator^(maxint a, const vint &b)
{
    return operator^(maxuint(a), b);
}

vint operator^(const vint &a, maxint b)
{
    return operator^(b, a);
}

vint operator^(maxuint a, const vint &b)
{
    vint r(b);
    r ^= a;
    return r;
}

vint operator^(const vint &a, maxuint b)
{
    return operator^(b, a);
}

vint operator^(stdint a, const vint &b)
{
    return operator^(maxint(a), b);
}

vint operator^(const vint &a, stdint b)
{
    return operator^(a, maxint(b));
}

vint operator^(stduint a, const vint &b)
{
    return operator^(maxuint(a), b);
}

vint operator^(const vint &a, stduint b)
{
    return operator^(a, maxuint(b));
}

std::string to_string(const vint &v)
{
    return to_stringB(v, 10);
}

std::string to_string(const vint &v, stdint base)
{
    assume(base >= 2);
    assume(base <= 36);
    if(base == 2 || base == 4 || base == 16)
        return to_string22(v, base);
    else if(base == 8 || base == 32)
        return to_string2(v, base);
    return to_stringB(v, base);
}

std::string to_stringB(const vint &v, stdint base)
{
    assume(base >= 2);
    assume(base <= 36);
    if (!(bool)v) return "0";
    vint temp(v), r;
    std::string str;
    str.reserve(temp.valSize * MAXV_INT_BIT_SIZE * 20 / 64 + 1);
    while ((bool)temp) {
        euclideanDivision(temp, base, temp, r);
        //assert_d(r < base);
        str.push_back("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[(maxuint)(r)]);
    }
    if (v.sign == vint::Negative) {
        str.push_back('-');
    }
    std::reverse(str.begin(), str.end());
    return str;
}

std::string to_string2(const vint &v, stdint base)
{
    assume(base == 2 || base == 4 || base == 8 || base == 16 || base == 32);
    if (!(bool)v) return "0";
    stdint baseLog(ILOG2V(base));
    stdint baseLogAnd((1 << baseLog) - 1);
    vint temp(v);
    maxuint r;
    std::string str;
    sizeint shift(0);
    str.reserve(temp.valSize * MAXV_INT_BIT_SIZE * 20 / 64 + 1);
    while (temp.toBoolWithoutLow() || (temp.integer[0] >> shift)) {
        //r = mod2(temp, base);
        r = ((temp.integer[0] >> shift) & baseLogAnd);
        shift += baseLog;
        if(shift + baseLog > MAXV_INT_BIT_SIZE) {
            temp >>= shift;
            shift = 0;
        }
        //assert_d(r < base);
        str.push_back("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[r]);
    }
    if (v.sign == vint::Negative) {
        str.push_back('-');
    }
    std::reverse(str.begin(), str.end());
    return str;
}

std::string to_string22(const vint &v, stdint base)
{
    assume(base == 2 || base == 4 || base == 16);
    if (!(bool)v) return "0";
    stdint baseLog(ILOG2V(base));
    stdint baseLogAnd((1 << baseLog) - 1);
    vint temp(v);
    maxuint r;
    std::string str;
    sizeint index(0);
    sizeint shift(0);
    str.reserve(temp.valSize * MAXV_INT_BIT_SIZE * 20 / 64 + 1);
    while (temp.toBoolWithoutLow(index+1) || (temp.integer[index] >> shift)) {
        //r = mod2(temp, base);
        r = ((temp.integer[index] >> shift) & baseLogAnd);
        shift += baseLog;
        if(shift + baseLog > MAXV_INT_BIT_SIZE) {
            index++;
            shift = 0;
        }
        //assert_d(r < base);
        str.push_back("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[r]);
    }
    if (v.sign == vint::Negative) {
        str.push_back('-');
    }
    std::reverse(str.begin(), str.end());
    return str;
}

void euclideanDivision(const vint &a, const vint &b, vint &q, vint &r)
{
    vint* buffer((vint*)malloc(2 * sizeof(vint)));
    vint::burnikelZiegler(a, b, buffer);
    q = buffer[0];
    q.sign = (vint::Sign)(a.sign ^ b.sign);
    r = buffer[1];
    r.sign = a.sign;
    vint::freeVintArray(buffer, 2);
}

vint mod2(const vint &a, const vint &b)
{
    assert_d((bool)b);
    assert_d(b == (vint(1) << ilog2(b)));
    sizeint cutoff;
    maxuint mask;
    for(cutoff = b.valSize; cutoff > 0; cutoff--)
    {
        if((bool)b.integer[cutoff-1])
            break;
    }
    assert_d(cutoff);
    sizeint targetSize(cutoff);
    cutoff--;
    mask = ((1 << ILOG2V(b.integer[cutoff])) - 1);
    sizeint iLog(1 << ILOG2S(targetSize));
    if(targetSize != iLog)
        targetSize = iLog << 1;
    maxuint* mod((maxuint*)calloc(targetSize, sizeof(maxuint)));
    vint copy(targetSize, a.sign, mod);
    memcpy(mod, a.integer, targetSize * sizeof(maxuint));
    copy.integer[cutoff] &= mask;
    return copy;
}

maxuint mod2(const vint &a, maxuint b)
{
    assume(b);
    assume(b == (maxuint)(1 << (maxuint)ILOG2V(b)));
    //return vint(a.integer[0] % b);
    return (a.integer[0] & ((1 << ILOG2V(b)) - 1)); //Faster, compiler doesn't optimize despite the assume
}

maxuint mod2(const vint &a, maxint b)
{
    return mod2(a, (maxuint)V_abs(b));
}

maxuint mod2(const vint &a, stduint b)
{
    return mod2(a, (maxuint)b);
}

maxuint mod2(const vint &a, stdint b)
{
    return mod2(a, (maxint)b);
}

//https://stackoverflow.com/questions/22281661/what-is-the-fastest-way-to-find-the-gcd-of-two-numbers
vint gcd(vint a, vint b)
{
    vint::Sign sign(a.sign);
    if(!(bool)b) {
        return a;
    }
    if(!(bool)a) {
        b.sign = sign;
        return b;
    }
    a.sign = vint::Positive;
    b.sign = vint::Positive;

    maxuint k(V_min(countLSBZeros(a), countLSBZeros(b)));
    a >>= k;
    b >>= k;

    // Dividing a by 2 until a becomes odd
    a >>= countLSBZeros(a);

    // From here on, 'a' is always odd.
    do
    {
        // If b is even, remove all factor of 2 in b
        b >>= countLSBZeros(b);

        // Now a and b are both odd.
        // Swap if necessary so a <= b,
        // then set b = b - a (which is even).
        if (a > b)
        {
            swap(a, b);
        }
        b -= a;
        assert_d(b.sign == vint::Positive || !(bool)b);
    }while ((bool)b);

    // restore common factors of 2
    a <<= k;
    a.sign = sign;
    return a;
}

vint abs(const vint &a)
{
    vint copy(a);
    copy.sign = vint::Positive;
    return copy;
}

vint pow(vint a, maxuint exp)
{
    vint result(1);

    while(true)
    {
        if (exp & 1)
            result *= a;
        exp >>= 1;
        if (!exp)
            break;
        a *= a;
    }

    return result;
}

vint max(const vint &a, const vint &b)
{
    if(a > b)
        return a;
    else
        return b;
}

vint min(const vint &a, const vint &b)
{
    if(a < b)
        return a;
    else
        return b;
}

vint sign(const vint &x)
{
    if(x.sign == vint::Positive)
        return vint(1);
    else
        return vint(-1);
}

sizeint ilog2(const vint &x)
{
    assert_d((bool)x);
    sizeint cutoff;
    for(cutoff = x.valSize; cutoff > 0; cutoff--)
    {
        if((bool)x.integer[cutoff-1])
            break;
    }
    assert_d(cutoff);
    cutoff--;
    return cutoff * MAXV_INT_BIT_SIZE + ILOG2V(x.integer[cutoff]);
}

sizeint vSize(const vint& x)
{
    sizeint currentSize(x.valSize);
    while (!x.integer[currentSize-1]) {
        currentSize--;
        if(!currentSize)
            return 1;
    }
    return currentSize;
}

sizeint vCapacity(const vint& x)
{
    return x.valSize;
}

sizeint reduceCapacity(vint& x)
{
    sizeint targetSize(vSize(x));
    sizeint iLog(1 << ILOG2S(targetSize));
    if(targetSize != iLog)
        targetSize = iLog << 1;
    x.resize(targetSize);
    return targetSize;
}

void swap(vint& a, vint& b)
{
    sizeint valSizeT(b.valSize);
    b.valSize = a.valSize;
    a.valSize = valSizeT;

    vint::Sign signT(b.sign);
    b.sign = a.sign;
    a.sign = signT;

    maxuint* integerT(b.integer);
    b.integer = a.integer;
    a.integer = integerT;
}

sizeint countLSBZeros(const vint& x)
{
    sizeint endByte(0);
    while (!x.integer[endByte] && endByte < x.valSize) {
        endByte++;
    }
    if(endByte == x.valSize)
        return x.valSize * MAXV_INT_BIT_SIZE;
    return endByte * MAXV_INT_BIT_SIZE + V_LSB_FIND(x.integer[endByte]);
}