0%

大整数的C++实现

Big Int

已经上传 githubhttps://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

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

(主要是除法用了试根法,导致计算时间大大增长)

1.png

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;
}