Big Int

已经上传 github ：https://github.com/mrh929/BigInt

Introduction

一个用C++编写的大整数运算器，使用了类的方法以及符号重载的方式来管理各种计算符号。

ostream & operator << (ostream &os, BigInt a);//重载输出流
BigInt operator << (BigInt a, int b);//以下是各种符号的符号重载
BigInt operator >> (BigInt a, int b);
bool operator > (BigInt a, BigInt b);
bool operator >= (BigInt a, BigInt b);
bool operator < (BigInt a, BigInt b);
bool operator <= (BigInt a, BigInt b);
bool operator == (BigInt a, BigInt b);
bool operator != (BigInt a, BigInt b);
BigInt operator + (BigInt a, BigInt b);
BigInt operator - (BigInt a, BigInt b);
BigInt operator * (BigInt a, BigInt b);
BigInt operator / (BigInt a, BigInt b);
BigInt operator % (BigInt a, BigInt b);
bool absolute_cmp(BigInt a, BigInt b);//绝对值比较
BigInt pushup(BigInt &a);//进位函数，方便更新处理加法和乘法之后的结果
BigInt pushdown(BigInt &a);//借位函数，方便更新处理减法与除法之后的前导零

由于计算要满足 语义完备性， 我们可以将 ＞ ＜ ＝ 之类的符号只实现其中两个，另一个用前面两个符号的逻辑表达式来表示。这样可以减小算法编写量。

比如我的取模运算就是利用 *a % b = a - (a / b b)** 的算式来进行的，目的是尽量减少重复计算的编写，避免语义重复导致代码冗杂。

这里的除法应用了试根法，通过不断减去除数，直到结果小于等于0，减去除数的次数便是最终的结果。

Example

2^2048 量级

X= 12482264789495844167952743674345192058347658696244846024506086756017404270329316853273041017249678950066348595640122013326388180800571171673805957545645811138822997641052783783643217674156834480484155675467569932624307075411108488522509264028054521773056807183216239690927306363502717731691081745037043661929912687363727319054138337027541053221928309092332845113037444417624930690136431627266175440870332546279455634900371634225967525289205393311361381052800131349877664888848787057588470069212633123461825711669157225916604667745476377157310522514234303671161858238888360921077671217358198370531988343589559604876284

Y= 1280730864615811759821132949087528726325520041739385671708858051142109630967299023961230758400337351772390265280394429009926875184005772035344541944036323178042973490581385536990180703449459150513955554549596768053810110112451980299436720866146499950924670995962445917972409391039058909325472146973088609382932848054367560562133611270686707661165793779566207985413463940767202953610885199897580866376092558784820762217980107705915440804143477818053671563647690424246811327119924020088286709086413582886779320723275600807886717409943439676762548169766661227661132724874836952052156168392209434986629771081555443608284

m= 26276671267336699549929786692210641894085878508699738341408482869283000463006609816748150758887020789500336306584836616160250372409642949310833789547133401665674848173946416217142121019602682188968147765629440590913830497348564644309060269315465932613732738758615722069669745219203052852800610504371627718589337502423268449548364104210930215810677840459085169776897907731873142754299180658298179972639899398242262850797386228967175906205170668840014770506566561161713676741346132712253755150416478986782691455647303372766626483759402251334751219513662706582839143768502897185844861757936312109408176137579367017788106

还是能在六分钟之内跑出来。

（主要是除法用了试根法，导致计算时间大大增长）

Code

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std; 

const int Digit_Per_Num = 1;
//digits to be stored into an int(accept range:(1-2));
class BigInt{
    public:
        int num[1000]; // both int and longlong are valid
        int n;
        int neg;// is it a negative number
        BigInt(){
            this->n = this->neg = this->num[0] = 0;
        }
        BigInt(string);
        BigInt operator -(){
            this->neg ^= 1;
            return *this;
        }

        string to_binary_string();

};

ostream & operator << (ostream &os, BigInt a);
BigInt operator << (BigInt a, int b);
BigInt operator >> (BigInt a, int b);
bool operator > (BigInt a, BigInt b);
bool operator >= (BigInt a, BigInt b);
bool operator < (BigInt a, BigInt b);
bool operator <= (BigInt a, BigInt b);
bool operator == (BigInt a, BigInt b);
bool operator != (BigInt a, BigInt b);
BigInt operator + (BigInt a, BigInt b);
BigInt operator - (BigInt a, BigInt b);
BigInt operator * (BigInt a, BigInt b);
BigInt operator / (BigInt a, BigInt b);
BigInt operator % (BigInt a, BigInt b);
bool absolute_cmp(BigInt a, BigInt b);
BigInt pushup(BigInt &a);
BigInt pushdown(BigInt &a);

BigInt::BigInt(string s){
    if(s.substr(0,1).c_str()[0] == '-'){
        s = s.substr(1);
        neg = 1;
    }else neg = 0;

    while(s.substr(0,1).c_str()[0] == '0')
        s = s.substr(1);
    // to cut off leading zero

    this->n = 0;
    while(1){
        if(s.size() >= Digit_Per_Num+1){
            this->num[this->n++] = atoi(s.substr(s.size() - Digit_Per_Num).c_str());
            s = s.substr(0, s.size() - Digit_Per_Num);
        }else{
            this->num[this->n] = atoi(s.c_str());
            break;
        }
    }

    pushup(*this);
}

string BigInt::to_binary_string(){
    string out;
    BigInt temp = *this;
    BigInt t;

    int neg = 0;
    if(temp < BigInt("0"))
        neg = 1;
    temp.neg = 0;

    while(temp != BigInt("0")){
        t = temp % BigInt("2");
        if(t.num[0] == 1)
            out = "1" + out;
        else
            out = "0" + out;
        temp = temp / BigInt("2");
    }

    if(neg)
        out = "-" + out;

    return out;
}

ostream & operator << (ostream &os, BigInt a){
    if(a.neg)
        os << "-";
    // os << a.neg? "-":" ";
    // negative operator

    os << a.num[a.n];
    // the first one digit has no leading zero

    for(int i = a.n-1; i+1; i--)
        os << setfill('0') << setw(Digit_Per_Num) << a.num[i];
        // add leading zero(s)
    os << ""; // I don't know why this must be put here;
}

BigInt operator + (BigInt a, BigInt b){
    BigInt BI("0");

    // if one is below 0 and the other is above 0, then sub them
    if(a.neg != b.neg){
        b = -b;
        return a - b;
    }

    BI.neg = a.neg;
    const int mod = pow(10, Digit_Per_Num);
    int i = 0, flag = 0, ci = 0;
    while(a.n >= i || b.n >= i || flag){
        flag = false;
        if(a.n < i) a.num[i] = 0;
        if(b.n < i) b.num[i] = 0;

        BI.num[i] = a.num[i] + b.num[i] + ci;
        ci = BI.num[i] / mod;

        if(ci)//carry
            flag = true;
        BI.num[i] %= mod;
        BI.n = i++;
    }
    pushup(BI);
    return BI;
}

BigInt operator - (BigInt a, BigInt b){
    BigInt BI;
    if(a.neg == b.neg){
        if(absolute_cmp(a, b))
            return -(b-a);
    }else{
        b = -b;
        return a + b;
    }

    BI.neg = a.neg;
    const int mod = pow(10, Digit_Per_Num);
    int i = 0, ci = 0;
    while(a.n >= i || b.n >= i){
        if(a.n < i) a.num[i] = 0;
        if(b.n < i) b.num[i] = 0;

        BI.num[i] = a.num[i] - b.num[i] + ci;

        if(BI.num[i] < 0){
            BI.num[i] += mod;
            ci = -1;
        }else ci = 0;

        BI.n = i++;
    }

    // to cut off leading zero(s)
    pushdown(BI);
    pushup(BI);
    return BI;
}

BigInt operator * (BigInt a, BigInt b){
    BigInt BI("0");

    if(absolute_cmp(b, a))
        return b * a;

    for(int i = 0; i <= a.n; i++){
        BigInt t = b;
        t.neg = 0;
        int p = a.num[i];
        for(int j = 0; j <= b.n; j++)
            t.num[j] *= p;
        pushup(t);

        t = t << i;
        BI = BI + t;
    }

    BI.neg = a.neg != b.neg;
    pushup(BI);

    return BI;
}

BigInt operator / (BigInt a, BigInt b){
    BigInt q;
    const BigInt ZERO;
    if(b == ZERO)
        throw "Division by zero condition!";

    // if a < b
    if(absolute_cmp(a, b))
        return ZERO;

    q.neg = a.neg != b.neg;
    a.neg = b.neg = 0;

    int flag = 1; 
    BigInt t = b << (a.n - b.n);

    while(1){
        while(a >= t){
            if(flag){
                q.n = t.n - b.n;
                flag = 0;
                for(int i = 0; i <= q.n; i++)
                    q.num[i] = 0;
            }
            q.num[t.n - b.n]++;
            a = a - t;
        }

        if((a.n == b.n && a.num[a.n] < b.num[b.n]) || a.n < b.n)
            break;

        t = t >> 1;
    }

    return q;
}

BigInt operator % (BigInt a, BigInt b){
    return a - (a/b)*b;
}

bool operator < (BigInt a, BigInt b){
    if(a.neg != b.neg)
        return a.neg == true;

    if(a.neg == false){
        return absolute_cmp(a, b);
    }else
        return !absolute_cmp(a, b);
}

bool operator > (BigInt a, BigInt b){
    return !(a<b) && a!=b;
}

bool operator == (BigInt a, BigInt b){
    return a.neg==b.neg && !absolute_cmp(a,b) && !absolute_cmp(b,a);
}

bool operator != (BigInt a, BigInt b){
    return !(a==b);
}

bool operator <= (BigInt a, BigInt b){
    return !(a>b);
}

bool operator >= (BigInt a, BigInt b){
    return !(a<b);
}

BigInt operator << (BigInt a, int b){
    if(b == 0)
        return a;

    BigInt BI;
    BI.neg = a.neg;
    for(int i = 0; i <= a.n; i++)
        BI.num[i+b] = a.num[i];
    for(int i = 0; i <= b-1; i++)
        BI.num[i] = 0;

    BI.n = a.n + b;
    return BI;      
}

BigInt operator >> (BigInt a, int b){
    if(b == 0)
        return a;
    BigInt BI("0");

    //result is 0
    if(b >= a.n + 1)
        return BI;

    BI.neg = a.neg;
    for(int i = b; i <= a.n; i++)
        BI.num[i-b] = a.num[i];

    BI.n = a.n - b;
    return BI;
}

// to judge if |a| < |b|
bool absolute_cmp(BigInt a, BigInt b){
    if(a.n != b.n)
        return a.n < b.n;
    for(int i = a.n; i+1; i--)
        if(a.num[i] != b.num[i])
            return a.num[i] < b.num[i];
    return false;
}

BigInt pushup(BigInt &a){
    if(a.n == 0 && a.num[0] == 0){
        a.neg = 0;
        return a;
    }

    int mod = pow(10, Digit_Per_Num);
    int ci = 0;
    for(int i = 0; i <= a.n; i++){
        a.num[i] += ci;
        ci = a.num[i] / mod;
        a.num[i] %= mod;        
    }

    if(ci)
        a.num[++a.n] = ci;

    // to cut off leading zero(s)
    pushdown(a);
}

BigInt pushdown(BigInt &a){
    int i = a.n;
    while(i){
        if(a.num[i--] == 0)
            a.n--;
        else break;
    }

    return a;
}

BigInt pow(BigInt x, BigInt y, BigInt mod){
    BigInt base = x % mod;
    BigInt r("1");
    const BigInt ZERO("0");
    const BigInt TWO("2");

    while(y != ZERO){
        if(y.num[0] & 1) r = (r * base) % mod;
        base = (base * base) % mod;
        y = y / TWO;
    }

    return r;
}

int main(){
    string s;

    cout << "please input a:";
    cin >> s;
    BigInt a(s);
    cout << "please input b:";
    cin >> s;
    BigInt b(s);
    cout << "you just input:" << endl << endl;
    cout << "a =     " << a << endl << endl;
    cout << "b =     " << b << endl << endl;

    cout << "a + b = (binary) " << (a + b).to_binary_string() << endl << endl;

    cout << "a - b = " << a - b << endl << endl;
    cout << "a * b = " << a * b << endl << endl;
    cout << "a / b = " << a / b << endl << endl;
    cout << "remainder:" << a - (a/b)*b << endl;
    //cout << "a / b = " << "0" << endl << "remainder:" << "123456789" << endl;

    cout << endl << endl;
    cout << "please input x, y, m which stands for x^y mod m:" << endl;
    cin >> s;
    BigInt x(s);

    cin >> s;
    BigInt y(s);

    cin >> s;
    BigInt m(s);

    BigInt ans = pow(x, y, m);
    cout << endl << "answer:" <<  ans << endl << endl;
    cout << endl << "answer:(binary)" <<  ans.to_binary_string() << endl << endl;
}