stein.cpp

采用stein算法求两个任意大整数（超过计算机整形表示范围）的最大公约数。

#include<iostream.h>
#include<strstrea.h>
#include<string.h>
#include<stdlib.h>//atoi函数
#include<fstream.h>
class BigInterger
{
	int *IntData;
	int ILength;
public:
	BigInterger(char* CharData);
	BigInterger(BigInterger&);
	~BigInterger();
	BigInterger& operator = (BigInterger& bi);
	BigInterger& operator /= (int div);
	BigInterger& operator *= (int mul);
	BigInterger& operator *= (BigInterger&);
	friend bool operator > (BigInterger& bi1,BigInterger& bi2);
	BigInterger& operator -= (BigInterger& bi);//将两对象相减,取绝对值
	int operator % (int res);//求余
	bool operator != (int zero);
	bool operator == (int zero);
	int* GetIntData(void )
	{
		return IntData;
	}
	int GetILength(void )
	{
		return ILength;
	}
};

BigInterger::BigInterger(char* CharData)//大整数的构造函数,从参数CharData中得到输入,并把其值存入IntData数组中
{
	char buf[5];//缓存CharData的4个字符,后面的istrstream类要求其大小必须设为5
	istrstream DivideStr(CharData);
	int slen=strlen(CharData);
	int i;
	if(slen%4)
	{
		IntData=new int[slen/4+1];//万进制
		ILength=slen/4+1;
		DivideStr.get(buf,slen%4+1);
		IntData[0]=atoi(buf);
		for(i=1;i<ILength;i++)
		{
			DivideStr.get(buf,5);
			IntData[i]=atoi(buf);
		}
	}
	else
	{
		IntData=new int[slen/4];//万进制
		ILength=slen/4;
		for(i=0;i<ILength;i++)
		{
			DivideStr.get(buf,5);
			IntData[i]=atoi(buf);
		}
	}
}

BigInterger::~BigInterger()
{
	if(this->IntData)
		delete[] this->IntData;
	this->ILength=0;
}

BigInterger::BigInterger(BigInterger& bi)//复制构造函数
{
	this->ILength=bi.ILength;
	this->IntData=new int[this->ILength];
	for(int i=0;i<this->ILength;i++)
	{
		this->IntData[i]=bi.IntData[i];
	}
}

BigInterger& BigInterger::operator = (BigInterger& bi)
{
	if(this->IntData)
	{
		delete[] this->IntData;
	}
	this->IntData=new int[bi.ILength];
	this->ILength=bi.ILength;
	for(int i=0;i<this->ILength;i++)
	{
		this->IntData[i]=bi.GetIntData()[i];
	}
	return *this;
}

BigInterger& BigInterger::operator /= (int div)
{
	int OneResidue=0;//数组IntData的每一元素除参数div后的余数
	int temp;
	for(int i=0;i<this->ILength;i++)
	{
		temp=(this->IntData[i]+OneResidue*10000)/div;//万进制
		OneResidue=(this->IntData[i]+OneResidue*10000)%div;
		this->IntData[i]=temp;
	}
	//当大整数对象长度大于1而且高位又有0时,处理高位,如果大整数对象长度＝1,就不需要
	if(this->ILength>1)
	{
		for( i=0;i<this->ILength;i++)//用i来得到为0的高位数
		{
			if(this->IntData[i]!=0)
				break;
		}
		if(i!=0)//如果IntData的高位为0
		{	
			int count=i;
			for(int j=0;i<this->ILength;i++)//去掉高位的0
			{
				this->IntData[j]=this->IntData[i];
				j++;
			}
			this->ILength-=count;//将大整数对象长度变小
		}
	}

	return *this;
}

BigInterger& BigInterger::operator *= (int mul)
{
	//先乘,结果使得IntData的元素可能大于10000
	for(int i=this->ILength-1;i>=0;i--)
	{
		this->IntData[i]*=mul;
	}
	//后进位,由于是万进制,如果IntData的元素大于10000,就要逢万要进位.
	for(i=this->ILength-1;i>=0;i--)
	{
			if(this->IntData[i]>=10000)//在最高的那位(i=0时)不需要也不能进位,这种情况留在后面处理
				if(i>0)
				{
					this->IntData[i-1]+=this->IntData[i]/10000;
					this->IntData[i]%=10000;
				}
	}
	//如果最高的那位(i=0时)的值IntData[0]>=10000,那么要处理进位就要重新分配空间
	if(this->IntData[0]>=10000)
	{
		ILength+=1;//长度加1
		int* TempIntData=new int[ILength];//用一个名为TempInt的数组缓存this->IntData
		TempIntData[0]=this->IntData[0]/10000;
		this->IntData[0]%=10000;
		for(i=1;i<ILength;i++)//将IntData[0...ILength-1]拷贝到TempIntData[1...ILength]
		{
			TempIntData[i]=this->IntData[i-1];
		}
		delete[] this->IntData;
		this->IntData=new int[ILength];
		for(i=0;i<ILength;i++)
		{
			this->IntData[i]=TempIntData[i];
		}
		delete[] TempIntData;
	}
	return *this;
}

BigInterger& BigInterger::operator *= (BigInterger& c)
{
	int i,j,k;
	int ResultLen=this->ILength+c.ILength-1;
	int* result=new int[ResultLen];//采用result数组来缓存结果
	for(i=0;i<ResultLen;i++)
	{
		result[i]=0;
	}
	int* mul=new int[c.ILength];	
	//先乘,两个大数相乘,结果使得IntData的元素可能大于10000
	for(j=0;j<this->ILength;j++)
	{
		for(i=0;i<c.ILength;i++)
			mul[i]=c.IntData[i]*this->IntData[j];
		for(k=j;k<c.ILength+j;k++)
		{
			result[k]=result[k]+mul[k-j];
		}
	}
	//后进位,由于是万进制,如果IntData的元素大于10000,就要逢万要进位.
	for(i=ResultLen-1;i>=0;i--)
	{
		if(result[i]>=10000)//在最高的那位(i=0)不进位
		if(i>0)
		{
			result[i-1]+=result[i]/10000;
			result[i]%=10000;
		}
	}
	//将值从result复制到this->IntData
	delete[] this->IntData;
	if(result[0]>=10000)
	{
		this->ILength=ResultLen+1;
		this->IntData=new int[this->ILength];
		this->IntData[0]=result[0]/10000;
		this->IntData[1]=result[0]%10000;
		for(i=2;i<this->ILength;i++)
		{
			this->IntData[i]=result[i-1];
		}
	}
	else
	{
		this->ILength=this->ILength+c.ILength-1;
		this->IntData=new int[this->ILength];
		for(i=0;i<this->ILength;i++)
			this->IntData[i]=result[i];
	}
	delete[] result;
	delete[] mul;
	return *this;
}

bool operator > (BigInterger& bi1,BigInterger& bi2)
{
	if(bi1.ILength>bi2.ILength)
		return true;
	else if(bi1.ILength<bi2.ILength)
		return false;
	else
	{
		for(int i=0;i<bi1.ILength;i++)
		{
			if(bi1.IntData[i]>bi2.IntData[i])
				return true;
			if(bi1.IntData[i]<bi2.IntData[i])
				return false;
		}
		return false;//此时两对象的IntData相等
	}
}

BigInterger& BigInterger::operator -= (BigInterger& bi)//－(减号运算)重载为相减并求绝对值的运算
{
	int i,j;
	if((*this)>bi)
	{
		i=bi.ILength-1;
		j=this->ILength-1;
		while(i>=0)
		{
			if(this->IntData[j]-bi.IntData[i]<0)
			{
				this->IntData[j-1]--;
				this->IntData[j]+=10000;
			}
			this->IntData[j]-=bi.IntData[i];
			i--;
			j--;
		}
	}
	else//this小于bi
	{
		int* TempInt=new int[this->ILength];
		int TempLen=this->ILength;
		for(i=0;i<this->ILength;i++)
		{
			TempInt[i]=this->IntData[i];
		}
		*this=bi;//调用重载赋值符函数
		i=TempLen-1;
		j=this->ILength-1;
		while(i>=0)
		{
			if(this->IntData[j]-TempInt[i]<0)
			{
				this->IntData[j-1]--;
				this->IntData[j]+=10000;
			}
			this->IntData[j]-=TempInt[i];
			i--;
			j--;
		}
		delete[] TempInt;
	}
	//整理,如果IntData的高位元素为0,就必须去掉
	if(this->ILength>1)
	{
		for( i=0;i<bi.ILength;i++)
		{
			if(this->IntData[i]!=0)
				break;
		}

		if(i!=0)//如果IntData的高位为0
		{
			int count=i;
			for(int j=0;i<this->ILength;i++)//去掉高位的0
			{
				this->IntData[j]=this->IntData[i];
				j++;
			}
			this->ILength-=count;//将长度变小
		}
	}
	return *this;
}

int BigInterger::operator % (int res)//求余,res参数限制在9999以内
{
		return this->IntData[this->ILength-1]%res;
}

bool BigInterger::operator != (int zero)//判断大整数对象和参数zero(一般为0)的大小,当然,zero还可以为其它整数值
{
	if(this->IntData[0]!=zero)
		return true;
	else 
		return false;
}

bool BigInterger::operator == (int zero)//判断大整数对象和参数zero(一般为0)的大小,当然,zero还可以为其它整数值
{
	if(this->IntData[0]==zero)
		return true;
	else 
		return false;
}

BigInterger gcd(BigInterger& m,BigInterger& n)
{
	BigInterger c=("1");//创建大整数c,并赋初值1
	while(m!=0&&n!=0)
    { 
        if (m%2==0&&n%2==0)
        { 
           m/=2; //不可用"/"号,如果写成m=m/2形式,那么当m/2返回时,还要调用operator=,
           n/=2; //然而在operator=函数中,对每个对象是做深拷贝,(详见operator=)
           c*=2;//同"/"号
        } 
        if (m%2==0&&n%2!=0)
        { 
           m/=2;
        } 
        if (m%2!=0&&n%2==0)
        { 
           n/=2;
        } 
        if (m%2!=0&&n%2!=0)
        { 
           BigInterger i=m;
			m-=n; //－(减号运算)重载为相减并求绝对值的运算,不可用"-"号,同理"/"号
			if(n>i)//只重载了>运算符
				n=i;     
        }    
    }
    if (m==0)
	{
       return n*=c;
	}
    if (n==0)
	{
       return m*=c;
	}
}

void main(int argc,char *argv[])
{
	char buf1[100],buf2[100];
	cout<<"程序开始运行..."<<endl;

	char c;
	do{	
		cout<<"选择从文本文件inputdata.txt输入值,请按f,选择从控制台输入值按其它键"<<endl;
	//	c=cin.get();
		c=cin.get();
		char OutPutBuf[100];//将最终结果输入到一个字符型数组中并输出,数组大小可以任意调整
		if(c=='f'||c=='F')
		{
			ifstream fin(".\\debug\\inputdata.txt");
			ofstream fout(".\\debug\\outputdata.txt",ios::out);
			if(!fout)
				cout<<"error";
			for(int i=0;i<10;i++)
				fin.getline(buf1,sizeof(buf1));
			while(fin.good())//
			{
				fin.getline(buf1,sizeof(buf1));//得到第一个大整数
				fin.getline(buf2,sizeof(buf2));//得到第二个大整数
				BigInterger m(buf1);
				BigInterger n(buf2);
				BigInterger	result=gcd(m,n);	
				ostrstream OutPut(OutPutBuf,sizeof(OutPutBuf),ios::out);
				for(i=0;i<result.GetILength();i++)
				{
					int temp=result.GetIntData()[i];
					if(i>0)//如果IntData中的某一位长度小于4位，就应该在这个数前相应补0
					{
						if(temp<10)
							OutPut<<"000";
						else if(temp<100)
							OutPut<<"00";
						else if(temp<1000)
							OutPut<<"0";
					}
					OutPut<<result.GetIntData()[i];
				}
				OutPut<<'\0';
				fout.write("第一个大整数:",13);
				fout.write(buf1,strlen(buf1));
				fout.write("\n",1);

				fout.write("第二个大整数:",13);
				fout.write(buf2,strlen(buf2));
				fout.write("\n",1);

				fout.write("最大公因数:",11);
				fout.write(OutPutBuf,strlen(OutPutBuf));
				fout.write("\n",1);
			}//while
			cout<<"程序保存在outputdata.txt中"<<endl;
		}
		else
		{
			cout<<"输入一个大整数:";
			cin>>buf1;	
			cout<<"输入另一个大整数:";
			cin>>buf2;
			BigInterger m(buf1);
			BigInterger n(buf2);
			BigInterger	result=gcd(m,n);
			ostrstream OutPut(OutPutBuf,sizeof(OutPutBuf),ios::out);
			for(int i=0;i<result.GetILength();i++)
			{
				int temp=result.GetIntData()[i];
				if(i>0)
				{
					if(temp<10)//如果IntData中的某一位长度小于4位，就应该在这个数前相应补0
						OutPut<<"000";
					else if(temp<100)
						OutPut<<"00";
					else if(temp<1000)
						OutPut<<"0";
				}
					OutPut<<result.GetIntData()[i];
			}
			OutPut<<'\0';
			cout<<"OK,The Result is:"<<endl;
			cout<<OutPutBuf<<endl;
		}
		cout<<"按e键退出,按其它键继续测试"<<endl;
		cin.get();
		c=cin.get();
		cin.get();
	}while(c!='e');
}