高精度库.cpp

西电内部用的高精度库,原是保密的!!!我奉献了出来

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

int const MAX = 300;
class BigInt
{
public:
	int data[MAX]; //用于存放该万进制数
	int num;  //该数有多少位
	bool neg;  //是否负数

public:
	void assign(const string &s); //f1: 用string型给BigInt赋值
	void assign(int n); //f2: 用int型给BigInt赋值

	//f3: 输出BigInt值,副作用输出该BigInt的输出流被setfill('0')
	friend ostream & operator << (ostream & outf, const BigInt &a);

	BigInt(BigInt &b); //f4: 拷贝构造函数,可以用'='给BigInt赋BigInt值,需要加上上面的构造函数
	BigInt(int a = 0){assign(a);} //f5: 构造函数

	void operator -() {if(!this->is_zero()) neg = !neg;} //f6: 对该对象取负
	bool is_zero() {return data[num - 1] == 0;} //f7: 判断是否为0


	void operator +=  (BigInt &a); //f11: 给当前BigInt 加上一个BigInt
	void operator +=  (int a){BigInt temp(a); *this += temp;} //f12: 给当前BigInt 加上一个int
	BigInt operator + (BigInt &a) {BigInt temp = *this; temp += a; return temp;} //f13: 两个BigInt相加
	BigInt operator + (int a) {BigInt temp = *this; temp +=a; return temp;} //f14: BigInt与int相加 

	void operator -=  (BigInt &a) {neg = !neg; *this += a; neg = !neg;}//f15: 给当前BigInt减去一个BigInt
	void operator -=  (int a) {BigInt temp(a); *this -= temp;} //f16: 给当前BigInt减去一个int
	BigInt operator - (BigInt &a) {BigInt temp = *this; temp -= a; return temp;} //f17: 两个BigInt相减
	BigInt operator - (int a) {BigInt temp = *this; temp -= a; return temp;} //f18: BigInt与int相加

	bool operator  >  (BigInt &a) {int i = Less(this, &a); return i == -1;} //f20: 判断a是否大于b
	bool operator  >= (BigInt &a) {int i = Less(this, &a); return i != 1;} //f21: 判断a是否大于等于b
	bool operator  <  (BigInt &a) {int i = Less(this, &a); return i == 1;} //f22: 判断a是否小于b
	bool operator  <= (BigInt &a) {int i = Less(this, &a); return i != -1;} //f23: 判断a是否小于等于b
	bool operator  == (BigInt &a) {int i = Less(this, &a); return i == 0;} //f24: 判断a是否等于b
	bool operator  != (BigInt &a) {int i = Less(this, &a); return i != 0;} //f25: 判断a是否不等于b

	void operator *=  (int a) {Positive_mul(this, abs(a)); neg = neg != a<0; if(a == 0) neg = false;} //f28: 给当前BigInt乘以int a
	//f29: 给当前BigInt乘以Bigint a
	void operator *=  (BigInt & a) 	{Positive_mul(this, &a); neg = neg != a.neg; if(a.is_zero()) neg = false;} 
	BigInt operator * (int a) {BigInt temp = *this; temp *= a; return temp;} //f30: BigInt乘以int a
	BigInt operator * (BigInt &a) {BigInt temp = *this; temp *= a; return temp;} //f31: BigInt乘以Bigint
	
	void operator /= (int a) {BigInt r, temp(a); div(*this, temp, r);} //f34: BigInt除等于int
	void operator /= (BigInt a) {BigInt r; div(*this, a, r);} //f35: BigInt除等于BigInt
	void operator %= (int a) {BigInt r, temp(a); div(*this, temp, r); *this = r;} //f36: BigInt对int取余
	void operator %= (BigInt a) {BigInt r; div(*this, a, r); *this = r;} //f37: 
	BigInt operator / (int a) {BigInt r,temp = *this, t(a); div(temp, t, r); return temp;} //f38: 
	BigInt operator / (BigInt a) {BigInt r, temp = *this; div(temp, a, r); return temp;} //f39: 
	BigInt operator % (int a) {BigInt r,temp = *this, t(a); div(temp, t, r); return r;} //f40: 
	BigInt operator % (BigInt a) {BigInt r, temp = *this; div(temp, a, r); return r;} //f41: 

	/*******************************************************************************************/
	//f8: 把BigInt b*10000^zero_after_b加到a上
	friend void Positive_add(BigInt *a, BigInt *b, int zero_after_b = 0); 
	friend int Positive_less(BigInt *a, BigInt *b); //f9: 比较两个BigInt有效位的大小,1:小于,-1:大于,0:等于
	friend void Positive_minus(BigInt *big, BigInt *small); //f10: 对BigInt big减去small,大正数减小正数
	friend int Less(BigInt *a, BigInt *b); //f19: 比较两个BigInt的大小,1:小于,0:大于,-1:等于
	friend void Positive_mul(BigInt *a, int b); //f26: 非负BigInt乘等于int, 0<=int<10000 
	friend void Positive_mul(BigInt *a, BigInt *b); //f27: 非负BigInt乘等于BigInt
	friend void Positive_div(BigInt &a, BigInt &divisor, BigInt &remainder); //f32: 带余非负数相除, b != 0
	friend void div(BigInt &a, BigInt &divisor, BigInt &remainder); //f33: BigInt相除
};

/*******************************************************************************************/
/*------------------------------f1: 用string型给BigInt赋值--------------------------------*/
void BigInt::assign(const string &s)
{
	neg = (s[0] == '-');
	num = 0;
	data[0] = 0;
	int j = 0;
	int t = 1;
	for(int i = s.size() - 1; i >= neg; i--)
	{
		j++;
		data[num] += (s[i] - '0') * t;
		t *= 10;
		if(j%4 == 0)
		{
			num++;
			data[num] = 0;
			t = 1;
		}
	}
	if(j%4)
		num++;
}


/*---------------------------f2: 用int型给BigInt赋值--------------------------------------*/
void BigInt::assign(int n)
{
	neg = false;
	if(n < 0)
	{
		neg = true;
		n *= -1;
	}
	num = 0;
	while(n / 10000)
	{
		data[num++] = n % 10000;
		n /= 10000;
	}
	data[num++] = n;
}

/*---------------f3: 输出BigInt值,副作用输出该BigInt的输出流被setfill('0')----------------*/
ostream & operator << (ostream &outf, const BigInt &a)
{
	if(a.neg) 
		outf<<'-';
	int i = a.num - 1;
	outf<<a.data[i];
	outf<<setfill('0');
	while(i > 0)
		outf<<setw(4)<<a.data[--i];
	return outf;
}
/*----------f4: 拷贝构造函数,可以用'='给BigInt赋BigInt值,需要加上上面的构造函数-----------*/
BigInt::BigInt(BigInt &b):neg(b.neg),num(b.num)
{
	for(int i = 0; i < num; i++)
		data[i] = b.data[i];
	//cout<<"Copy constructor Called"<<endl;
}

/*-------------------f8: 把BigInt b*10000^zero_after_b加到a上-------------------*/
void Positive_add(BigInt *a, BigInt *b, int zero_after_b)
{
	if(b->is_zero())
		return;

	//把该数据可能即将用到的数据进行初始化为0
	a->data[a->num] = 0;
	int i, bnum = b->num + zero_after_b;
	for(i = a->num + 1; i < bnum + 1; i++)
		a->data[i] = 0;

	//把b的数据加到该数据上,不进位
	for(i = 0; i < b->num; i++)
		a->data[i + zero_after_b] += b->data[i];

	//控制进位
	int num1 = (bnum > a->num) ? bnum : a->num;
	int teamp = 0; //暂时存放进位
	for(i = 0; i < num1; i++)
	{
		a->data[i] += teamp;
		teamp = a->data[i] / 10000;
		a->data[i] %= 10000;
	}
	if(teamp)
	{
		a->data[a->num] = teamp;
		a->num = num1 + 1;
	}
	else
		a->num = num1;
}

/*------------------------f9: 比较两个BigInt有效位的大小,1:小于,-1:大于,0:等于-------------------*/
int Positive_less(BigInt *a, BigInt *b)
{
	if(a->num > b->num)
		return -1;
	if(a->num < b->num)
		return 1;
	for(int i = b->num - 1; i >= 0 ; i--)
		if(a->data[i] < b->data[i])
			return 1;
		else if(a->data[i] > b->data[i])
			return -1;
	return 0; //表示等于
}

/*------------------------------f10: 对BigInt big减去small,大正数减小正数-------------------------*/
void Positive_minus(BigInt *big, BigInt *small)
{
	for(int i = 0; i < small->num; i++)
	{
		if(big->data[i] < small->data[i])
		{
			big->data[i + 1] --;
			big->data[i] += 10000;
		}
		big->data[i] -= small->data[i];
	}
	while(!big->data[big->num - 1])
		big->num --;
	if(big->num == 0) big->num = 1;
	if(big->is_zero())
		big->neg = false;
}

/*-------------------------------f11: 给当前BigInt 加上一个BigInt--------------------------------*/
void BigInt::operator +=(BigInt &a)
{
	if(!neg && a.neg)
		if(Positive_less(this, &a) == 1)
		{
			BigInt temp = a;
			Positive_minus(&temp, this);
			*this = temp;
			neg = true;
		}
		else
			Positive_minus(this, &a);
	else if(neg && !a.neg)
	{
		if(Positive_less(this, &a) == 1)
		{
			BigInt temp = a;
			Positive_minus(&temp, this);
			*this = temp;
			neg = false;
		}
		else
		{
			Positive_minus(this, &a);
			neg = true;
		}
	}
	else 
		Positive_add(this, &a); //只加有效位,符号不动
}

/*--------------------------f19: 比较两个BigInt有效位的大小,1:小于,-1:大于,0:等于------------------------*/
int Less(BigInt *a, BigInt *b)
{
	int i = Positive_less(a, b);
	if(!a->neg && !b->neg)
		return i;
	if(a->neg && b->neg)
		return - i;
	if(a->neg && !b->neg)
		return 1;
	if(!a->neg && b->neg)
		return -1;
}

/*------------------------------f26: BigInt乘等于int, 0<=int<10000 -----------------------------*/
void Positive_mul(BigInt *a, int b)
{
	if(b == 0)
	{
		a->assign(0);
		return;
	}

	//不进位乘法
	for(int i = 0; i < a->num; i++)
		a->data[i] *= b;

	//进位
	int t = 0;
	for(int j = 0; j < a->num; j++)
	{
		a->data[j] += t;
		t = a->data[j] / 10000;
		a->data[j] %= 10000;
	}
	if(t)
		a->data[a->num++] = t;
}

/*----------------------------------f27: 非负BigInt乘等于BigInt----------------------------------*/
void Positive_mul(BigInt *a, BigInt *b)
{
	BigInt result;
	for(int i = 0; i < b->num; i++)
	{
		BigInt temp = *a;
		temp *= b->data[i];
		Positive_add(&result, &temp, i);
	}
	bool boo = a->neg;
	*a = result;
	a->neg = boo;
}

/*---------------------------------f32: 带余非负数相除, b != 0------------------------------*/
void Positive_div(BigInt &a, BigInt &b, BigInt &r)
{
	//if(b.is_zero()) cout<<"Dived by zero!"<<endl;
	if(a < b){r = a; a.assign(0); return;}//处理特殊情况

	int n = a.num - b.num + 1; //结果的位数，可能多一位

	r.assign(0);
	r.num = b.num - 1;
	for(int i = 0; i < r.num; i++)
		r.data[i] = a.data[n + i];
	if(b.num == 1) //处理b只有一位的特殊情况
		r.num = 1;

	for(int i = n - 1; i >= 0; i--)
	{
		r *= 10000;
		r += a.data[i];
		a.data[i] = 0;
		while(b <= r)
		{
			int header = r.data[r.num - 1];
			if(r.num > b.num)
				header = header * 10000 + r.data[r.num - 2];
			int part_quotient = header/(b.data[b.num - 1] + 1);
			if(part_quotient < 1)
				part_quotient = 1;  //以上6行是“保守试商”的过程

			BigInt temp = b;
			temp *= part_quotient;
			r -= temp;

			a.data[i] += part_quotient;
		}
	}
	a.num = n;
	while(a.data[a.num - 1] == 0)
		a.num --;
}
/*--------------------------------------f33: BigInt相除--------------------------------------------*/
void div(BigInt &a, BigInt &divisor, BigInt &remainder)
{
	bool temp = a.neg != divisor.neg;
	divisor.neg = false;
	a.neg = false;
	Positive_div(a, divisor, remainder);
	if(temp)
	{
		-a;
		-remainder;
	}
}