Bignum

#include <iostream>
#include <string>
using namespace std;

typedef unsigned int UI;

// Bignum lib
class Bignum;
string adding(string, string);
string add(string, string);
string multiplique(string, string);
string multi(string, string);
string multiplique_small(string, string);
string multi_small(string, string);
string subtracting(string, string);
string subtr(string, string);
string remove_zeroes(string);
string str_reverse(string);
string divide(string, string);
string div(string, string);
string modulo(string, string);
string mod(string, string);
string power(string, string);
string powe(string, string);
string bigger(string, string);
bool compare(string, string, string);
string intToStr(int);
int strToInt(string);
string remove1stchar(string);
string dodajzera(string, string);

class Bignum
{
// values
public:
    string value;
    string value_abs;
private:
    string value_bin;
    string value_oct;
    string value_hex;
// flags
public:
    bool zero; // value = 0
    bool positive; // value > 0
    bool negative; // value < 0
//constructor
    Bignum();
    Bignum(const Bignum&);
    Bignum(const char[]);
    Bignum(string);
    Bignum(int);
// methodes
private:
    void clear(); // clear all values and flags
public:
    void set_new_value(string);
    void update_flags();

    // overloaded math operators
    //bignum & bignum
    //1 char
    string operator+(const Bignum& number) const
    {
        return adding(this->value, number.value);
    }
    string operator-(const Bignum& number) const
    {
        return subtracting(this->value, number.value);
    }
    string operator*(const Bignum& number) const
    {
        return multiplique(this->value, number.value);
    }
    string operator/(const Bignum& number) const
    {
        return divide(this->value, number.value);
    }
    string operator%(const Bignum& number) const
    {
        return modulo(this->value, number.value);
    }
    //2 chars
    string operator+=(const Bignum& number)
    {
        this->set_new_value(adding(this->value, number.value));
        return this->value;
    }
    string operator-=(const Bignum& number)
    {
        this->set_new_value(subtracting(this->value, number.value));
        return this->value;
    }
    string operator*=(const Bignum& number)
    {
        this->set_new_value(multiplique(this->value, number.value));
        return this->value;
    }
    string operator/=(const Bignum& number)
    {
        this->set_new_value(divide(this->value, number.value));
        return this->value;
    }
    string operator%=(const Bignum& number)
    {
        this->set_new_value(modulo(this->value, number.value));
        return this->value;
    }
    // bignum & int
    string operator+(const int& number) const
    {
        return adding(this->value, intToStr(number));
    }
    string operator-(const int& number) const
    {
        return subtracting(this->value, intToStr(number));
    }
    string operator*(const int& number) const
    {
        return multiplique(this->value, intToStr(number));
    }
    string operator/(const int& number) const
    {
        return divide(this->value, intToStr(number));
    }
    string operator%(const int& number) const
    {
        return modulo(this->value, intToStr(number));
    }
    //2 chars
    string operator+=(const int& number)
    {
        this->set_new_value(adding(this->value, intToStr(number)));
        return this->value;
    }
    string operator-=(const int& number)
    {
        this->set_new_value(subtracting(this->value, intToStr(number)));
        return this->value;
    }
    string operator*=(const int& number)
    {
        this->set_new_value(multiplique(this->value, intToStr(number)));
        return this->value;
    }
    string operator/=(const int& number)
    {
        this->set_new_value(divide(this->value, intToStr(number)));
        return this->value;
    }
    string operator%=(const int& number)
    {
        this->set_new_value(modulo(this->value, intToStr(number)));
        return this->value;
    }
    // bignum & string
    string operator+(const string& number) const
    {
        return adding(this->value, number);
    }
    string operator-(const string& number) const
    {
        return subtracting(this->value, number);
    }
    string operator*(const string& number) const
    {
        return multiplique(this->value, number);
    }
    string operator/(const string& number) const
    {
        return divide(this->value, number);
    }
    string operator%(const string& number) const
    {
        return modulo(this->value, number);
    }
    //2 chars
    string operator+=(const string& number)
    {
        this->set_new_value(adding(this->value, number));
        return this->value;
    }
    string operator-=(const string& number)
    {
        this->set_new_value(subtracting(this->value, number));
        return this->value;
    }
    string operator*=(const string& number)
    {
        this->set_new_value(multiplique(this->value, number));
        return this->value;
    }
    string operator/=(const string& number)
    {
        this->set_new_value(divide(this->value, number));
        return this->value;
    }
    string operator%=(const string& number)
    {
        this->set_new_value(modulo(this->value, number));
        return this->value;
    }

    //other operators
    string operator=(const string& number)
    {
        this->set_new_value(number);
        return this->value;
    }
    string operator=(const int& number)
    {
        this->set_new_value(intToStr(number));
        return this->value;
    }
    string &operator++()
    {
        this->set_new_value(adding(this->value, "1"));
        return this->value;
    }
    string operator++(int)
    {
        Bignum copy1 = (*this);
        this->set_new_value(adding(this->value, "1"));
        return copy1.value;
    }
    string &operator--()
    {
        this->set_new_value(subtracting(this->value, "1"));
        return this->value;
    }
    string operator--(int)
    {
        Bignum copy1 = (*this);
        this->set_new_value(subtracting(this->value, "1"));
        return copy1.value;
    }
    string &operator-()
    {
        this->set_new_value(((this->value[0] == '-') ? (remove1stchar(this->value)) : ('-' + this->value)));
        return this->value;
    }
    //bignum
    bool operator==(const Bignum& number)
    {
        return compare(this->value, "==", number.value);
    }
    bool operator!=(const Bignum& number)
    {
        return compare(this->value, "!=", number.value);
    }
    bool operator>(const Bignum& number)
    {
        return compare(this->value, ">", number.value);
    }
    bool operator<(const Bignum& number)
    {
        return compare(this->value, "<", number.value);
    }
    bool operator>=(const Bignum& number)
    {
        return compare(this->value, "=>", number.value);
    }
    bool operator<=(const Bignum& number)
    {
        return compare(this->value, "<=", number.value);
    }
    //string
    bool operator==(const string& number)
    {
        return compare(this->value, "==", number);
    }
    bool operator!=(const string& number)
    {
        return compare(this->value, "!=", number);
    }
    bool operator>(const string& number)
    {
        return compare(this->value, ">", number);
    }
    bool operator<(const string& number)
    {
        return compare(this->value, "<", number);
    }
    bool operator>=(const string& number)
    {
        return compare(this->value, "=>", number);
    }
    bool operator<=(const string& number)
    {
        return compare(this->value, "<=", number);
    }
    //int
    bool operator==(const int& number)
    {
        return compare(this->value, "==", intToStr(number));
    }
    bool operator!=(const int& number)
    {
        return compare(this->value, "!=", intToStr(number));
    }
    bool operator>(const int& number)
    {
        return compare(this->value, ">", intToStr(number));
    }
    bool operator<(const int& number)
    {
        return compare(this->value, "<", intToStr(number));
    }
    bool operator>=(const int& number)
    {
        return compare(this->value, "=>", intToStr(number));
    }
    bool operator<=(const int& number)
    {
        return compare(this->value, "<=", intToStr(number));
    }
    //unsigned int
    bool operator==(const UI& number)
    {
        return compare(this->value, "==", intToStr(number));
    }
    bool operator!=(const UI& number)
    {
        return compare(this->value, "!=", intToStr(number));
    }
    bool operator>(const UI& number)
    {
        return compare(this->value, ">", intToStr(number));
    }
    bool operator<(const UI& number)
    {
        return compare(this->value, "<", intToStr(number));
    }
    bool operator>=(const UI& number)
    {
        return compare(this->value, "=>", intToStr(number));
    }
    bool operator<=(const UI& number)
    {
        return compare(this->value, "<=", intToStr(number));
    }
    operator string()
    {
        return this->value;
    }
    operator int()
    {
        return strToInt(this->value);
    }
    operator UI()
    {
        return (UI)strToInt(this->value);
    }
};

ostream& operator<<(ostream &out, const Bignum &num)
{
    return out <<num.value;
}
istream& operator>>(istream &in, Bignum &num)
{
    string a;
    in >> a;
    num.set_new_value(a);
    return in;
}

//int and string & Bignum global overloads
// int & bignum
string operator+(const int& number, const Bignum& number2)
{
    return adding(intToStr(number), number2.value);
}
string operator-(const int& number, const Bignum& number2)
{
    return subtracting(intToStr(number), number2.value);
}
string operator*(const int& number, const Bignum& number2)
{
    return multiplique(intToStr(number), number2.value);
}
string operator/(const int& number, const Bignum& number2)
{
    return divide(intToStr(number), number2.value);
}
string operator%(const int& number, const Bignum& number2)
{
    return modulo(intToStr(number), number2.value);
}
// bignum & string
string operator+(const string& number, const Bignum& number2)
{
    return adding(number, number2.value);
}
string operator-(const string& number, const Bignum& number2)
{
    return subtracting(number, number2.value);
}
string operator*(const string& number, const Bignum& number2)
{
    return multiplique(number, number2.value);
}
string operator/(const string& number, const Bignum& number2)
{
    return divide(number, number2.value);
}
string operator%(const string& number, const Bignum& number2)
{
    return modulo(number, number2.value);
}
//2 chars
string operator+=(string& number, const Bignum& number2)
{
    number = adding(number, number2.value);
    return number;
}
string operator-=(string& number, const Bignum& number2)
{
    number = subtracting(number, number2.value);
    return number;
}
string operator*=(string& number, const Bignum& number2)
{
    number = multiplique(number, number2.value);
    return number;
}
string operator/=(string& number, const Bignum& number2)
{
    number = divide(number, number2.value);
    return number;
}
string operator%=(string& number, const Bignum& number2)
{
    number = modulo(number, number2.value);
    return number;
}
//int
bool operator==(const int& number, const Bignum& number2)
{
    return compare(intToStr(number), "==", number2.value);
}
bool operator!=(const int& number, const Bignum& number2)
{
    return compare(intToStr(number), "!=", number2.value);
}
bool operator>(const int& number, const Bignum& number2)
{
    return compare(intToStr(number), ">", number2.value);
}
bool operator<(const int& number, const Bignum& number2)
{
    return compare(intToStr(number), "<", number2.value);
}
bool operator>=(const int& number, const Bignum& number2)
{
    return compare(intToStr(number), "=>", number2.value);
}
bool operator<=(const int& number, const Bignum& number2)
{
    return compare(intToStr(number), "<=", number2.value);
}
//string
bool operator==(const string& number, const Bignum& number2)
{
    return compare(number, "==", number2.value);
}
bool operator!=(const string& number, const Bignum& number2)
{
    return compare(number, "!=", number2.value);
}
bool operator>(const string& number, const Bignum& number2)
{
    return compare(number, ">", number2.value);
}
bool operator<(const string& number, const Bignum& number2)
{
    return compare(number, "<", number2.value);
}
bool operator>=(const string& number, const Bignum& number2)
{
    return compare(number, "=>", number2.value);
}
bool operator<=(const string& number, const Bignum& number2)
{
    return compare(number, "<=", number2.value);
}

Bignum::Bignum()
{
    this->clear();
}
Bignum::Bignum(const Bignum& a)
{
    this->clear();
    this->set_new_value(a.value);
}
Bignum::Bignum(string a)
{
    this->clear();
    this->set_new_value(a);
}
Bignum::Bignum(const char a[])
{
    string b = a;
    this->clear();
    this->set_new_value(b);
}
Bignum::Bignum(int a)
{
    this->clear();
    this->set_new_value(intToStr(a));
}

string powe(string a, string b)
{
    //interface
    return power(a, b);
}
string power(string a, string b)
{
    Bignum c;
    c = a;
    for(int i = 1; i < strToInt(b); i++)
        c *= a;
    return c.value;
}
void Bignum::clear()
{
    this->value = "0";
    this->value_abs = "0";
    this->value_bin = "0";
    this->value_oct = "0";
    this->value_hex = "0";
    this->update_flags();
    return;
}
void Bignum::set_new_value(string a)
{
    this->value = a;
    this->value_abs = remove1stchar(a);
    this->update_flags();
}

void Bignum::update_flags()
{
    if(this->value == "0")
    {
        this->zero = true;
        this->positive = false;
        this->negative = false;
    }
    if(this->value[0] == '-')
    {
        this->zero = false;
        this->positive = false;
        this->negative = true;
    }
    if(this->value[0] != '-')
    {
        this->zero = false;
        this->positive = true;
        this->negative = false;
    }
}

string sumofdigits(Bignum a)
{
    Bignum b;
    b = 0;
    for(unsigned i = 0; i < a.value.length(); i++)
        b += a.value[i] - '0';
    return b.value;
}

string remove1stchar(string a)
{
    if(a[0] == '-')
        a.erase(0, 1);
    return a;
}

string str_reverse(string a)
{
    string b;
    for(int i = a.length()-1; i >= 0; i--)
        b += a[i];
    return  b;
}

string remove_zeroes(string a)
{
    string b;
    int length = a.length();
    int n_zero_pos = length;
    for(int i = 0; i < length; i++)
        if(a[i] != '0')
        {
            n_zero_pos = i;
            break;
        }
    if(n_zero_pos == length) return "0";

    for(int i = n_zero_pos; i < length; i++)
        b += a[i];
    return b;
}

string adding(string a, string b)
{
    if(a[0] != '-' && b[0] != '-') return add(a, b);
    if(a[0] == '-' && b[0] == '-') return '-' + add(remove1stchar(a), remove1stchar(b));
    if(a[0] != '-' && b[0] == '-') return subtracting(a, remove1stchar(b));
    if(a[0] == '-' && b[0] != '-') return subtracting(b, remove1stchar(a));
    return "";
}

string add(string a, string b)
{
    int length = max(a.length(), b.length());
    a = str_reverse(a);
    b = str_reverse(b);
    if(a.length() != b.length())
        ((a.length() > b.length()) ? (b) : (a)).resize(length, '0');
    string c;
    c.resize(length + 1);

    for(int i = 0; i < length; i++)
        c[i] = a[i] - '0' + b[i];

    for(int i = 0; i < length; i++)
        if(c[i] > '9')
        {
            c[i] -= 10;
            c[i+1]++;
        }
    c[length] += '0';
    return remove_zeroes(str_reverse(c));
}

string subtracting(string a, string b)
{
    if(a[0] != '-' && b[0] != '-')
    {
        if(compare(a, ">=", b)) return subtr(a, b);
        if(compare(a, "<=", b)) return '-' + subtr(b, a);
    }
    if(a[0] == '-' && b[0] == '-') return adding(a, remove1stchar(b));
    if(a[0] != '-' && b[0] == '-') return adding(a, remove1stchar(b));
    if(a[0] == '-' && b[0] != '-') return '-' + adding(remove1stchar(a), b);
    return "";
}

string subtr(string a, string b)
{
    int length = max(a.length(), b.length());
    a = str_reverse(a);
    b = str_reverse(b);
    if(a.length() != b.length())
        ((a.length() > b.length()) ? (b) : (a)).resize(length, '0');
    string c;
    c.resize(length);

    for(int i = 0; i < length; i++)
        c[i] = a[i] + '0' - b[i];

    for(int i = 0; i < length; i++)
        if(c[i] < '0')
        {
            c[i] += 10;
            c[i+1]--;
        }
    return remove_zeroes(str_reverse(c));
}

string bigger(string a, string b)
{
    if(a == b) return a;
    if(a.length() != b.length())
        return ((a.length() > b.length()) ? (a) : (b));
    int i = 0;
    while(a[i] == b[i])
        i++;
    return ((a[i] > b[i]) ? (a) : (b));
}

string smaller(string a, string b)
{
    return ((a == bigger(a, b)) ? (b) : (a));
}

Bignum bigger(Bignum a, Bignum b)
{
    return ((a.value == bigger(a.value, b.value)) ? (a) : (b));
}

Bignum smaller(Bignum a, Bignum b)
{
    return ((a.value == bigger(a.value, b.value)) ? (b) : (a));
}

string multiplique(string a, string b)
{
    Bignum c = smaller(a, b);
    if(c < 501) return multiplique_small(a, b);
    if(a[0] != '-' && b[0] != '-') return multi(a, b);
    if(a[0] == '-' && b[0] == '-') return multi(remove1stchar(a), remove1stchar(b));
    if(a[0] != '-' && b[0] == '-') return '-' + multi(a, remove1stchar(b));
    if(a[0] == '-' && b[0] != '-') return '-' + multi(remove1stchar(a), b);
    return "";
}

int mnozeniecharow(char a, char b)
{
    return (a-'0')*(b-'0');
}

string multi(string a, string b)
{
    if(a == "0" || b == "0") return "0";
    string pom = bigger(a, b);
    b = smaller(a, b);
    a = pom;
    Bignum w = 0;
    a = str_reverse(a);
    b = str_reverse(b);
    for(int c = 0; c < a.length(); c++)
        for(int d = 0; d < b.length(); d++)
            w += dodajzera(intToStr(mnozeniecharow(a[c], b[d])), intToStr(c+d));
    return w.value;
}

bool compare(string a, string comp, string b)
{
    if(comp == "==" || comp == ">=" || comp == "<=")
        if(a == b) return true;
    if(comp == "==") return false;
    if(comp == "!=") return true;
    string bigger_num = bigger(a, b);
    if((comp == ">" || comp == ">=") && bigger_num == a) return true;
    if((comp == "<" || comp == "<=") && bigger_num == b) return true;
    return false;
}

string divide(string a, string b)
{
    if(a[0] != '-' && b[0] != '-') return div(a, b);
    if(a[0] == '-' && b[0] == '-') return div(remove1stchar(a), remove1stchar(b));
    if(a[0] != '-' && b[0] == '-') return '-' + div(a, remove1stchar(b));
    if(a[0] == '-' && b[0] != '-') return '-' + div(remove1stchar(a), b);
    return "";
}

string div(string a, string b)
{
    string xtimes = "0";
    while(compare(a, ">=", b))
    {
        a = subtracting(a, b);
        xtimes = adding(xtimes, "1");
    }
    return xtimes;
}

string modulo(string a, string b)
{
    if(a[0] != '-' && b[0] != '-') return mod(a, b);
    if(a[0] == '-' && b[0] == '-') return remove1stchar(adding(b, mod(remove1stchar(a), remove1stchar(b))));
    if(a[0] != '-' && b[0] == '-') return mod(a, remove1stchar(b));
    if(a[0] == '-' && b[0] != '-') return subtracting(b, mod(remove1stchar(a), b));
    return "";
}

string mod(string a, string b)
{
    while(compare(a, ">=", b))
        a = subtracting(a, b);
    return a;
}

string dodajzera(string a, string b)
{
    string c;
    for(int i = strToInt(b); i > 0; i--)
        c+='0';
    c = a + c;
    return c;
}

string intToStr(int n)
{
    string tmp;
    if(n < 0)
    {
        tmp = "-";
        n = -n;
    }
    if(n > 9)
        tmp += intToStr(n / 10);
    tmp += n % 10 + 48;
    return tmp;
}

int strToInt(string s)
{
    int tmp = 0;
    unsigned i = 0;
    bool m = false;
    if(s[0] == '-')
    {
        m = true;
        i++;
    }
    for(; i < s.size(); i++)
        tmp = 10 * tmp + s[i] - 48;
    return m ? -tmp : tmp;
}

Bignum nwd(Bignum a, Bignum b)
{
    if(a > b) a -= b;
    else if (b > a) b -= a;
    return ((a == b) ? (a) : (nwd(a, b)));
}

/*
Bignum nwd(Bignum a, Bignum b)
{
    Bignum c;
    while(b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
*/

Bignum nww(Bignum a, Bignum b)
{
    //return (a/nwd(a, b)*b);
    return a;
}

string multiplique_small(string a, string b)
{
    if(a[0] != '-' && b[0] != '-') return multi_small(a, b);
    if(a[0] == '-' && b[0] == '-') return multi_small(remove1stchar(a), remove1stchar(b));
    if(a[0] != '-' && b[0] == '-') return '-' + multi_small(a, remove1stchar(b));
    if(a[0] == '-' && b[0] != '-') return '-' + multi_small(remove1stchar(a), b);
}

string multi_small(string a, string b)
{
    string w = a;
    while(subtracting(b, "1") != "0")
    {
        b = subtracting(b, "1");
        w = adding(w, a);
    }
    return w;
}