biginteger.h

使用分治技术

				ret = false;
			else if (a.Length() < b.Length())
				ret = true;
			else
				for (int i = a.Length(); i >=1 ; i--) 
					if (a.GetData(i) > b.GetData(i)) {
						ret = false;
						break;
					}
					else if (a.GetData(i) < b.GetData(i)) {
						ret = true;
						break;
					}
		}
		else{											//a and b are minus 
			if (a.Length() > b.Length()) 
				ret = true;
			else if (a.Length() < b.Length())
				ret = false;
			else
				for (int i = 1; i <= a.Length(); i++) 
					if (a.GetData(i) > b.GetData(i)) {
						ret = true;
						break;
					}
					else if (a.GetData(i) < b.GetData(i)) {
						ret = false;
						break;
					}
		}

	return ret;
}

template <class T>
bool BigInteger<T>::operator == (const BigInteger<T>& obj){
	bool ret = true;
	BigInteger<T> a(*this), b(obj);
	a = standardize(a);
	b = standardize(b);
	if (a.GetSymbol() == b.GetSymbol() && a.Length() == b.Length()) {
		for (int i = 0; i <= Last; i++){
			if (Data[i] != obj.GetData(i + 1)) {
				ret = false;
				break;
			}
		}
	}
	else
		ret = false;
	
	return ret;	
}

template <class T>
void BigInteger<T>::Input(){
	cout<<"Please input the symbol of big integer('+' or 'minus'):";
	while (1) {
		char smbl;
		cin>>smbl;
		if ('+' == smbl) {
			Symbol = PLUS;
			break;
		}
		if ('-' == smbl) {
			Symbol = MINUS;
			break;
		}
		cout<<"Input symbol invalid,please input again."<<endl;
	}
	cout<<"please input the length of big integer:";
	while (1) {
		cin>>Last;
		if (Last <= MaxSize - 1) break;
		cout<<"Input length isn't allowed greater than maximal size: "<<MaxSize - 1
			<<"Please input again"<<endl;
	}
	
	for (int i = 0; i < Last; i++)
		cin>>Data[i];
}

template <class T>
void BigInteger<T>::Output(){
	cout<<"the big integer is: ";
	if (Symbol == MINUS)
		cout<<'-';
	for (int i = Last; i >= 0; i--)
		cout<<Data[i];
	cout<<endl;
}

template <class T>
ifstream& operator >>(ifstream& in, BigInteger<T>& obj){
	string str;
	getline(in,str,'\n');
	int bufSize = 0;
	int smblflag = 0;
	int strLen = str.length();
	SYMBOL smbl;

	switch(str[0]) {
	case '-':
		smbl =MINUS;
		smblflag = 1;
		bufSize = strLen;
		break;
	case '+':
		smbl = PLUS;
		smblflag = 1;
		bufSize = strLen;
		break;
	default:
		smbl = PLUS;
		bufSize = strLen + 1;
		smblflag = 0;
	}

	T* buf = new T[bufSize];
	buf[bufSize - 1] = 0;
	for (int i = smblflag; i < bufSize - 1 + smblflag; i++)
		buf[bufSize - 2 - i + smblflag] = str[i];
	
	BigInteger<T> num(buf,smbl);	
	obj = num;
	
	return in;
}

template <class T>
ofstream& operator <<(ofstream& out,const BigInteger<T>& obj){
	bool flag = true;

	if (obj.GetSymbol() == MINUS)
		out<<'-';
	
	for (int i = obj.Length(); i >= 1; i--){
		if (obj.GetData(i) == '0' && flag) continue;

		out<<obj.GetData(i);
		flag = false;
	}
	out<<endl;
	
	return out;
}

int MinKthPower(int a, int b, const int& k){
	int ret = 0;
	int n = 0;
	if (k <= 0){
		cerr<<"Invalid value of the third parameters!"<<endl;
		exit(1);
	}
	
	if (a < k || b < k)
		return k;

	if (k == 1)
		return a > b ? a : b;

	while (++n){
		ret = pow(k,n);
		if (ret >= a && ret >= b)
			break;
	}

	return ret;
}

template <class T>
BigInteger<T> abs(const BigInteger<T>& obj){
  BigInteger<T> ret(obj);
  if (ret.GetSymbol() == MINUS) {
	  ret.SetSymbol(PLUS);
  }
  return ret;
}

template <class T>
BigInteger<T> standardize(const BigInteger<T>& obj) {
	BigInteger<T> ret(obj);
	for (int i = ret.Length(); i >= 1; i--) {
		if (ret.GetData(i) != '0') break;
		
		ret.SetLength(i - 1);		
	}
	return ret;
}

template <class T>
BigInteger<T> PositiveIntSubstraction(const BigInteger<T>& X, const BigInteger<T> &Y) {
	BigInteger<T> ret, a(X), b(Y);
	SYMBOL sret = PLUS;

	if (a.GetSymbol() != PLUS || b.GetSymbol() != PLUS) {
		cerr<<"Invalid symbol of the parameter in PositiveIntSubstraction!"<<endl;
		exit(1);
	}

	if (a == b) 
		return a.ZERO();

	BigInteger<T> tmp;
	if (a < b) {			//如果a < b, 交换a，b
		tmp = a;
		a = b;
		b = tmp;
		sret = MINUS;
	}

	int Len1 = a.Length(), Len2 = b.Length();
	b.SetLength(Len1);
	ret.SetLength(Len1);

	char ch;
	bool* C =  new bool[Len1 + 1];
	C[0] = 0;
	for (int i = 1; i <= Len1; i++) {
		ch = a.GetData(i) - b.GetData(i) - C[i - 1] + 58;

		if (ch >= 48 && ch <= 57) {
			C[i] = 1;
		}
		else {
			C[i] = 0;
			ch -= 10;
		}
		ret.SetData(i,ch);
	}

	delete []C;

	ret.SetSymbol(sret);
	return ret;
}

template <class T>
BigInteger<T> TraditionalMultiplication(const BigInteger<T>& a, const BigInteger<T>& b){
	BigInteger<T> ret, tmp;
	int Len1 = a.Length();
	int Len2 = b.Length();
	ret.SetLength(Len1 + Len2);
	tmp.SetLength(Len1 + Len2);
	int* c = new int[Len1 + 1]; 
	int m;	

	for (int j = 1; j <= Len2; j++){
		c[0] = 0;
		tmp.FillNumber('0');
		for (int i = 1; i <= Len1; i++){
			m = (a.GetData(i) - 48) * (b.GetData(j) - 48) + c[i - 1];
			c[i] = m / 10;
			tmp.SetData(i + j - 1,m % 10 + 48);
		}

		if (c[Len1])
			tmp.SetData(Len1 + j, 48 + c[Len1]);

		ret = ret + tmp;
	}

	delete []c;

	ret.SetSymbol(a.GetSymbol() == b.GetSymbol() ? PLUS : MINUS);
	
	return ret;
}

template <class T>
BigInteger<T> OptimizedMultiplication(const BigInteger<T>& a, const BigInteger<T>& b, int div/* = 2*/){
	BigInteger<T> ret, X(a), Y(b);
	
	X = standardize(X);
	Y = standardize(Y);
	int originLen = MinKthPower(X.Length(), Y.Length(), div);	//返回大于len1和len2的最小的2幂次的整数
	X.SetLength(originLen);										//make up the shorted number same as the longer one
	Y.SetLength(originLen);

	if (div == 1 || originLen == div)							//对问题没有划分或问题规模达到默认的div长度时，直接运算
		ret = TraditionalMultiplication(X, Y);
	else{
		int dividedLen = originLen / div;

		BigInteger<T>* M = new BigInteger<T>[div];
		BigInteger<T>* N = new BigInteger<T>[div];

		for (int j = 0; j < div; j++) {
			M[j].SetLength(dividedLen);
			N[j].SetLength(dividedLen);
			for (int i = 1; i <= dividedLen; i++) {
				M[j].SetData(i, X.GetData(i + dividedLen * j)); 
				N[j].SetData(i, Y.GetData(i + dividedLen * j));
			}			
		}

		ret = OptimizedFuncion(M, N, originLen, div);
		
		ret.SetSymbol(X.GetSymbol() == Y.GetSymbol() ? PLUS : MINUS);
		
		delete []M;
		delete []N;
	}
		
	return ret;
}

template <class T>
BigInteger<T> LeftShift(const BigInteger<T>&a, int n) {
	BigInteger<T> ret;
	ret.SetSymbol(a.GetSymbol());
	ret.SetLength(a.Length() + n);
	for (int j = 1; j <= n; j++)
		ret.SetData(j,'0');

	for (int i = 1; i <= a.Length(); i++)
		ret.SetData(i + n, a.GetData(i));

	return ret;
}

template <class T>
BigInteger<T> OptimizedFuncion(BigInteger<T> M[], BigInteger<T> N[], int originLen, int div) {
	BigInteger<T> ret;
	int dividedLen = originLen / div;

	BigInteger<T> c0,c1,c2,c3,d0,d1,d2,d3,d4,d5,d6;
	switch(div) {
	case 2:
		//////////////////////////////////////////////////////////////////////////
		//Formula when divide with 2
		//def:n2 = dividedLen / div
		//M * N = (M0 + M1 * 10^n2) * (N0 + N1 * 10^n2)
		//		= M0 * N0 + (M0 * N1 + M1 * N0) * 10^n2 + M1 * N1 * 10^(2*N2)
		//		= M0 * N0 + [(M0 + M1) * (N0 + N1) - M0 * N0 - M1 * N1] * 10^n2 + M1 * N1 * 10^(2*N2)
		//////////////////////////////////////////////////////////////////////////
		
		c0 = M[0] * N[0];
		c1 = M[1] * N[1];
		d0 = c0;
		d1 = (M[0] + M[1]) * (N[0] + N[1]) - c0 - c1; 
		d2 = c1;
		ret = LeftShift(d2, 2 * dividedLen) + LeftShift(d1, dividedLen) + d0;			
		break;
	case 3:
		//////////////////////////////////////////////////////////////////////////
		//Formula when divide with 3
		//def:n3 = dividedLen / div
		//M * N = [M0 + M1 * 10^n3 + M2 * 10^(2*n3)] * [N0 + N1 * 10^n3 + N2 * 10^(2*n3)]
		//		= M0 * N0 + (M0 * N1 + M1 * N0) * 10^n3 + (M0 * N2 + M2 * N0 + M1 * N1) * 10^(2*n3) +
		//		  (M1 * N2 + M2 * N1) * 10^(3*n3) + M2 * N2 * 10^(4*n3) 
		//		= M0 * N0 + [(M0 + M1) * (N0 + N1) - M0 * N0 - M1 * N1] * 10^n3 + 
		//		  [(M0 + M2) * (N0 + N2) + M1 * N1 - M0 * N0 - M2 * N2) * 10^(2*n3) +
		//		  [(M1 + M2) * (N1 + N2) - M1 * N1 - M2 * N2] * 10^(3*n3) + M2 * N2 * 10^(4*n3)
		//////////////////////////////////////////////////////////////////////////
		
		c0 = M[0] * N[0];
		c1 = M[1] * N[1];
		c2 = M[2] * N[2];
		d0 = c0;
		d1 = (M[0] + M[1]) * (N[0] + N[1]) - c0 - c1;
		d2 = (M[0] + M[2]) * (N[0] + N[2]) + c1 - c0 - c2;
		d3 = (M[1] + M[2]) * (N[1] + N[2]) - c1 - c2;
		d4 = c2;
		ret = d0 + LeftShift(d1, dividedLen) + LeftShift(d2, 2 * dividedLen) + LeftShift(d3, 3 * dividedLen) + 
			LeftShift(d4, 4 * dividedLen);
		break;
	case 4:	
		// 算式错误！ [10/15/2008]
		c0 = M[0] * N[0];
		c1 = M[1] * N[1];
		c2 = M[2] * N[2];
		c3 = M[3] * N[3];
		d0 = c0;
		d1 = (M[0] + M[1]) * (N[0] + N[1]) - c0 - c1;
		d2 = (M[0] + M[2]) * (N[0] + N[2]) + c1 - c0 - c2;
		d3 = (M[0] + M[3]) * (N[0] + N[3]) + (M[1] + M[3]) * (N[1] + N[3]) - c0 - c1 - c2 -c3;
		d4 = (M[1] + M[3]) * (N[1] + N[3]) + c2 - c1 - c3;
		d5 = (M[2] + M[3]) * (N[2] + N[3]) - c2 - c3;
		d6 = c3;
		ret = d0 + LeftShift(d1,dividedLen) + LeftShift(d2, 2 * dividedLen) + LeftShift(d3, 3 * dividedLen) +
			LeftShift(d4, 4 * dividedLen) + LeftShift(d5, 5 * dividedLen) + LeftShift(d6, 6 * dividedLen);
		break;
 	default:
		cerr<<"can not deal with this partition, div = "<<div<<endl;
		exit(1);
		break;
	}

	return ret;
}

template <class T>
BigInteger<T> BigInteger<T>::ZERO() {
	BigInteger<T> ret(1);
	ret.SetLength(1);
	return ret;
}