mathclass.h

大整数的四则运算算法 用vc.net2003编写

#include <iostream> 

#define MAX_LEN 100 
using namespace std;
class MEGA_INTEGER{ 
private: 
	int m_szNum1[MAX_LEN],m_szNum2[MAX_LEN],m_Result[MAX_LEN],m_Remain[MAX_LEN]; //the data
	int m_Num1L,m_Num2L,m_ResultL,m_RemainL; //the length of all the data


	void Add(int *szNum1,int *szNum2,int *szResult,int nNum1L,int nNum2L,int &nResultL) 
	{ 
		int i,j,k=0; 

		if(nNum1L>nNum2L)
		{ 
			nResultL=nNum1L; 
			for(i=0;i<nNum1L-nNum2L;i++)szNum2[MAX_LEN-nResultL+i]=0; 
		} 
		else 
		{ 
			nResultL=nNum2L; 
			for(i=0;i<nNum2L-nNum1L;i++)szNum1[MAX_LEN-nResultL+i]=0; //初始化数据1和2，长度为较长者，置零
		} 

		for(i=0;i<nResultL;i++)
		{ 
			j=szNum1[MAX_LEN-1-i]+szNum2[MAX_LEN-1-i]+k; 
			k=j/10; 
			szResult[MAX_LEN-1-i]=j%10; 
		} 
		if(k&&(MAX_LEN-nResultL>=1))
		{ 
			szResult[MAX_LEN-1-nResultL]=k; 
			nResultL++; 
		} 
	} 

	void Sub(int *szNum1,int *szNum2,int *szResult,int nNum1L,int nNum2L,int &nResultL) 
	{ 
		int i,j,k=0; //k为借位情况

		nResultL=nNum1L; 
		for(i=0;i<nNum1L-nNum2L;i++)szNum2[MAX_LEN-nResultL+i]=0; 

		for(i=0;i<nResultL;i++)
		{ 
			j=szNum1[MAX_LEN-1-i]-szNum2[MAX_LEN-1-i]-k; 
			if(j>=0)
			{ 
				k=0; 
				szResult[MAX_LEN-1-i]=j; 
			} 
			else
			{ 
				k=1; 
				szResult[MAX_LEN-1-i]=j+10; 
			} 
		} 


		for(i=0;i<nResultL-1&&szResult[MAX_LEN-nResultL+i]==0;i++); 
		nResultL-=i; //缩减结果的长度
	} 

	int Div(int *szNum1,int *szNum2,int *szResult,int nNum1L,int nNum2L,int &nResultL)//temp被除数，除数，余数，被除数长，除数长，余数长 
	{ 
		int i,k; 

		if(nNum1L>nNum2L)k=0; //被除数大于除数
		else if(nNum1L==nNum2L)
		{ 
			for(i=0,k=2;i<nNum1L;i++)
			{ 
				if(szNum1[MAX_LEN-nNum1L+i]>szNum2[MAX_LEN-nNum1L+i]){k=0;break;} 
				else if(szNum1[MAX_LEN-nNum1L+i]<szNum2[MAX_LEN-nNum1L+i]){k=1;break;}//少于被除数 
			} 
		} 
		else k=1; 
		if(k==1)
		{ 
			for(i=0;i<nNum1L;i++)szResult[MAX_LEN-1-i]=szNum1[MAX_LEN-1-i]; 
			nResultL=nNum1L; 
		} 
		if(k==2){szResult[MAX_LEN-1]=0;nResultL=1;} 
		if(k==0)Sub(szNum1,szNum2,szResult,nNum1L,nNum2L,nResultL);//试商每次减去除数 
		return k; 
	} 

	void Mul(int *szNum1,int *szNum2,int nNum1L,int &nNum2L,int xn) 
	{ 

		int i,j,k=0; 

		for(i=0;i<nNum1L;i++)
		{ 
			j=szNum1[MAX_LEN-1-i]*xn+k; 
			k=j/10; 
			szNum2[MAX_LEN-1-i]=j%10; 
		} 

		nNum2L=nNum1L; //nNum2L save the length of the number
		if(k&&(MAX_LEN-nNum2L>=1))
		{ 
			szNum2[MAX_LEN-1-nNum2L]=k; 
			nNum2L++; 
		} 
		//for(i=0;i<nNum2L-1&&szNum2[MAX_LEN-nNum2L+i]==0;i++); 
		//nNum2L-=i; 
	} 



public: 
	MEGA_INTEGER(char *,char *); 
	void I_Add(void); //Interface functions
	void I_Sub(void); 
	void I_Mul(void); 
	int I_Div(void); 
	void Display(int);
	int m_nLess;
}; 

MEGA_INTEGER::MEGA_INTEGER(char *y1="0",char *y2="0") 
{ 
	int i; 
	m_nLess=0;

	for(m_Num1L=0;m_Num1L<MAX_LEN&&y1[m_Num1L]>='0'&&y1[m_Num1L]<='9';m_Num1L++); 
	for(i=0;i<m_Num1L;i++)m_szNum1[MAX_LEN-m_Num1L+i]=*(y1+i)-48; 
	for(i=0;i<m_Num1L-1&&m_szNum1[MAX_LEN-m_Num1L+i]==0;i++); 
	m_Num1L-=i; 
	for(m_Num2L=0;m_Num2L<MAX_LEN&&y2[m_Num2L]>='0'&&y2[m_Num2L]<='9';m_Num2L++); 
	for(i=0;i<m_Num2L;i++)m_szNum2[MAX_LEN-m_Num2L+i]=*(y2+i)-48; 
	for(i=0;i<m_Num2L-1&&m_szNum2[MAX_LEN-m_Num2L+i]==0;i++); 
	m_Num2L-=i; 
} 

void MEGA_INTEGER::I_Add(void) 
{ 
	Add(m_szNum1,m_szNum2,m_Result,m_Num1L,m_Num2L,m_ResultL); 
} 

void MEGA_INTEGER::I_Sub(void) 
{ 

	int flag=0;
	if(m_Num1L>m_Num2L)
		Sub(m_szNum1,m_szNum2,m_Result,m_Num1L,m_Num2L,m_ResultL); 
	if(m_Num1L==m_Num2L)
	{
		for(int k=m_Num1L;k>=0;k--)
		{
			if(m_szNum1[MAX_LEN-k]!=m_szNum2[MAX_LEN-k])
			{
				
				flag=1?m_szNum1[MAX_LEN-k]>m_szNum2[MAX_LEN-k]:flag=0;
				break;
			}
		}
		
			if(flag!=1)
			{
				Sub(m_szNum2,m_szNum1,m_Result,m_Num2L,m_Num1L,m_ResultL);
				m_nLess=1;
			}
			else
			{
				Sub(m_szNum1,m_szNum2,m_Result,m_Num1L,m_Num2L,m_ResultL);
				m_nLess=0;
			}

			
	}


	if(m_Num1L<m_Num2L)
	{
		Sub(m_szNum2,m_szNum1,m_Result,m_Num2L,m_Num1L,m_ResultL);
		m_nLess=1;
	}


}

void MEGA_INTEGER::I_Mul(void) 
{ 
	int i,j,k,x[MAX_LEN],xn,y[MAX_LEN],yn=0; 

	for(i=0;i<m_Num2L;i++){ 
		Mul(m_szNum1,x,m_Num1L,xn,m_szNum2[MAX_LEN-1-i]); //m_szNum1被乘数，x为暂时保存乘数第k位与被乘数相乘的结果，xn长度
		for(j=0;j<i&&(MAX_LEN-xn>=1);j++)
		{ 
			for(k=0;k<xn;k++)x[MAX_LEN-1-xn+k]=x[MAX_LEN-xn+k]; //缩减位
			x[MAX_LEN-1]=0; 
			xn++; 
		} 
		Add(x,y,m_Result,xn,yn,m_ResultL); 
		for(j=0;j<m_ResultL;j++)y[MAX_LEN-1-j]=m_Result[MAX_LEN-1-j]; 
		yn=m_ResultL; 
	} 
	//for(i=0;i<m_ResultL-1&&m_Result[MAX_LEN-m_ResultL+i]==0;i++); 
	//m_ResultL-=i; 
} 

int MEGA_INTEGER::I_Div(void) 
{ 
	int x[MAX_LEN],xn=0,i,j,k,n; 

	if(m_Num2L==0||(m_Num2L==1&&m_szNum2[MAX_LEN-1]==0))
	{ 
		cout<<"\n错误！"; 
		return 1; 
	} 

	for(i=0,m_ResultL=m_Num1L;i<m_Num1L;i++)
	{ 
		for(j=0;j<xn;j++)x[MAX_LEN-1-xn+j]=x[MAX_LEN-xn+j]; 
		x[MAX_LEN-1]=m_szNum1[MAX_LEN-m_Num1L+i]; 
		xn++; 
		k=Div(x,m_szNum2,m_Remain,xn,m_Num2L,m_RemainL); 
		if(k==2)m_Result[MAX_LEN-m_Num1L+i]=1; 
		else if(k==1)m_Result[MAX_LEN-m_Num1L+i]=0; 
		else 
		{ 
			for(n=1;;n++)
			{ 
				for(j=0;j<m_RemainL;j++)x[MAX_LEN-1-j]=m_Remain[MAX_LEN-1-j]; 
				xn=m_RemainL; 
				k=Div(x,m_szNum2,m_Remain,xn,m_Num2L,m_RemainL); 
				if(k==1)break; 
			} 
			m_Result[MAX_LEN-m_Num1L+i]=n; 
		} 
		for(j=0;j<m_RemainL;j++)x[MAX_LEN-1-j]=m_Remain[MAX_LEN-1-j]; 
		xn=m_RemainL; 
	} 
	for(i=0;i<m_ResultL-1&&m_Result[MAX_LEN-m_ResultL+i]==0;i++); 
	m_ResultL-=i; 
	for(i=0;i<m_RemainL-1&&m_Remain[MAX_LEN-m_RemainL+i]==0;i++); 
	m_RemainL-=i; 
	return 0; 
} 

void MEGA_INTEGER::Display(int k) 
{ 
	int i; 

	for(i=0;i<m_ResultL;i++)cout<<m_Result[MAX_LEN-m_ResultL+i]; 
	if(k)
	{ 
		cout<<"\n"; 
		for(i=0;i<m_RemainL;i++)cout<<m_Remain[MAX_LEN-m_RemainL+i]; 
	} 
}