slnum.cpp

超长整数类及演示程序

// slnum.cpp: implementation of the slnum class.
//定义一个超高精度的类slnum的实现算法代码，用以实现超过20位有效数字整型数值
//的运算，并具有兼容已有整型数据int的能力，能与int数据混合运算。
//版权所有，贵州师范大学数学与计算机科学系2001成计本班罗国文（贵州天柱二中）
//          E-mail:  [e-mail]
//凡引用本文件不得删除上述信息
//////////////////////////////////////////////////////////////////////
#include<string.h>
#include "slnum.h"
#include <stdlib.h>
#include <math.h>

#define z1  "0"
#define z2  "00"
#define z3  "000"
#define z4  "0000"
#define R    10000


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//空初始化
slnum::slnum()
{
	sign=1;
	arr_n=1;
	sl=new long[arr_n];
	sl[0] =0;
	soure=new char[8];
	soure="0";

}
//把数值字符串设置值给slnum类对象
void slnum::setval(const char * s)
{
	char SIGN,temp[5];
	int len,i,j=4,k=0;
	SIGN=s[0];
	switch(SIGN)
	{
	case '-':
	case '+':
		{
			if(SIGN=='-')sign=-1;
			if(SIGN=='+')sign=+1;
			len=strlen(s);
			soure=new char[len+1];
			strcpy(soure,s);
			for(int n=0;n<=len;n++)soure[n]=soure[n+1];
			len=strlen(soure);
			if (len%4==0) arr_n=(int)len/4;
			else arr_n=(int)(len/4+1);
			sl=new long[arr_n];
			for(i=len;i>=0;i--)							//把数值串赋值给数组
			{
				temp[j]=soure[i];
				if(i==0&&j)
					for(int q=0;q<j;q++)temp[q]='0';
				if(j==0||i==0)
				{
					temp[4]='\0';
					sl[k]=atol(temp);
					j=4;k++;
				}
                                j--;
			} 
			break;
		}
	default:
		{	
			sign=+1;
			len=strlen(s);
			soure=new char[len+1];
			strcpy(soure,s);
			if (len%4==0) arr_n=(int)len/4;
			else arr_n=(int)(len/4+1);
			sl=new long[arr_n];
			for(i=len;i>=0;i--)							//把数值串赋值给数组
			{	
				temp[j]=soure[i];
				if(i==0&&j)
					for(int q=0;q<j;q++)temp[q]='0';
				if(j==0||i==0)
				{
					temp[4]='\0';
					sl[k]=atol(temp);
					j=4;k++;
				}
                                j--;
			}
			break;
		}
	}
}
//获取值,以字符串方式取出
char *  slnum::getval ()
{
	char * temp,*e="-";
	if(sign==-1)
	{
		temp=new char[strlen(soure)+2];
		strcpy(temp,e);
		strcat(temp,soure);
	}
	else	
	{
		temp=new char[strlen(soure)+1];
		strcpy(temp,soure);
	}
	return temp;
}
//以数值字符串进行初始化
slnum::slnum(const char * s)
{
	setval(s);
}

//大于比较：真值为ture；假值为flase
bool slnum::operator >(const slnum &num)
{
	if(sign >num.sign ) return true;
	if (sign==1&&num.sign==1)
	{
		if (strlen(soure) >strlen(num.soure) ) return true;
		if ((strlen(soure) ==strlen(num.soure))&&(strcmp(soure ,num.soure )>0)) return true;
	}
	if (sign==-1&&num.sign==-1)
	{
		if (strlen(soure) <strlen(num.soure) ) return true;
		if ((strlen(soure) ==strlen(num.soure))&&(strcmp(soure ,num.soure )<0)) return true;
	}
	return false;
}
//等于比较：真值为ture；假值为flase
bool slnum::operator ==(const slnum &num)
{
	if ((sign==num.sign)&&(strcmp(soure ,num.soure )==0)) return true;
	else return false;
}
//不等于比较：真值为ture；假值为flase
bool slnum::operator !=(const slnum &num)
{
	if ((sign!=num.sign)||(strcmp(soure ,num.soure )!=0)) return true;
	else return false;
}
//大于等于比较：真值为ture；假值为flase
bool slnum::operator >=(const slnum &num)
{
	if(*this>num||*this==num)return true;
	else return false;
}
//小于比较：真值为ture；假值为flase
bool slnum::operator <(const slnum &num)
{
	if(!(*this>=num))return true;
	else return false;
}
//小于等于比较：真值为ture；假值为flase
bool slnum::operator <=(const slnum &num)
{
	if(!(*this>num)) return true;
	else return false;
}


//进位、借位调整器
void regulator(slnum *num)		
{
   int i;
   for(i=0;i<num->arr_n ;i++)
   {
	   if(num->sl[i]>=R)				   //进位调整
	   {
		   num->sl[i+1]+=num->sl[i]/R;
		   num->sl[i]%=R;
	   }
	   if(num->sl[i]<0)				   //借位调整
	   {
		   num->sl[i+1]=num->sl[i+1]-1;
		   num->sl[i]+=R;
	   }
   }
}


void  regulator_sign(slnum *num) //符号调整
{
	int flag=1,i;
	if(num->sl[num->arr_n-1]<0)flag=-1;
	num->sign=flag*num->sign;
	for(i=0;i<num->arr_n ;i++)num->sl[i]=flag*num->sl[i];
}


//整理数组值到串soure
void sltostr(slnum *num)				
{
	int i;
	char * n_temp,*c_temp;
	n_temp=new char[5];
	c_temp=new char[5];
	num->soure =new char[num->arr_n *4+4];
	num->soure[0]='\0';
	i=num->arr_n-1;
	if(num->sl[i])				//处理高高位
	{
		ltoa(num->sl[i],n_temp,10)  ;
		strcpy(num->soure ,n_temp);
	}
	int l=0;
	while(i)				//处理高位后的各位数
	{
		i--;
		ltoa(num->sl[i],n_temp,10);
		l=4-strlen(n_temp);
		if(l>0)
		{
			if(l==1)strcpy(c_temp,z1);
			if(l==2)strcpy(c_temp,z2);
			if(l==3)strcpy(c_temp,z3);
			if(l==4)strcpy(c_temp,z4);
			strcat(num->soure,c_temp);
		}
		strcat(num->soure,n_temp);
	}
	int len;
        while(num->soure[0]=='0')//去除无效0的处理
        {
	len=strlen(num->soure );
	for(i=0;i<len; i++)
		num->soure [i]=num->soure [i+1];
        }
  	if(num->soure[0]=='\0')strcpy(num->soure,"0");
}
//与常规整数的加运算
slnum	slnum::operator +(int num)				
{
	char * s;
	s=new char[strlen(getval())+1];
	strcpy(s,getval());
	slnum temp(s);
	char * ss;
	ss=new char[31];
	itoa(num,ss,10);
	slnum AA(ss);
	slnum temp0;
	temp0=temp+AA;
	return temp0;
}
//与常规整数的减运算
slnum	slnum::operator -(int num)				
{
	char * s;									
	s=new char[strlen(getval())+1];
	strcpy(s,getval());
	slnum temp(s);								//取左操作数
	char * ss;
	ss=new char[31];
	itoa(num,ss,10);
	slnum A(ss);								//取右操作数
	slnum temp0;
	temp0=temp-A;
	return temp0;
}
//加运算
slnum slnum::operator +(const slnum &num)     
{
	int i;
	slnum temp;
	temp.arr_n =arr_n>num.arr_n ?arr_n:num.arr_n ;
	if((arr_n==num.arr_n )&&abs((sl[arr_n-1]*sign+num.sl[num.arr_n-1 ]*num.sign ))>=R) ++temp.arr_n ;
	temp.sl=new long[temp.arr_n ];
	for(i=0;i<temp.arr_n ;i++)temp.sl[i]=0;
	for(i=0;i<temp.arr_n ;i++)
	{
		if((i>=arr_n)&&(num.arr_n>arr_n ))temp.sl[i]=num.sl[i]*num.sign ;
		if((i>=num.arr_n )&&(arr_n >num.arr_n))temp.sl[i]=sl[i]*sign;
	        if((i<arr_n)&&(i< num.arr_n ))temp.sl[i]=sl[i]*sign+num.sl[i]*num.sign ;
        }
        regulator_sign(&temp);
	regulator(&temp);
	sltostr(&temp);
	return temp;
}
//求相反数
slnum slnum:: operator -()						
{
	char * s;
	s=new char[strlen(getval())+1];
	strcpy(s,getval());
	slnum temp(s);
	temp.sign *=-1;
	return temp;
}
//减运算
slnum slnum::operator -(const slnum &num)		
{
	slnum temp,A;
        A=num ;
        A.sign  *=-1 ;
	temp=*this+A;
	return temp;
}
//与常规整数的乘运算
slnum slnum::operator *(int num)				
{
	int i,j;
	char * ss;
	ss=new char [31];
	itoa(num ,ss,10);
	slnum temp,a(ss);
	temp.arr_n =arr_n+a.arr_n ;
	temp.sign =sign*a.sign ;
	temp.sl=new long[temp.arr_n ];
	for(i=0;i<temp.arr_n ;i++)temp.sl[i]=0;
    for(i=0;i<arr_n;i++)
	{
		for(j=0;j<a.arr_n ;j++)
		{
			temp.sl[i+j]+=sl[i]*a.sl[j];
		}
		regulator(&temp);
	}
	sltostr(&temp);
	return temp;
}
//乘运算
slnum slnum::operator *(const slnum &num)		
{
	int i,j;
	slnum temp;
	temp.sign =sign*num.sign ;
	temp.arr_n =arr_n+num.arr_n ;
	temp.sl=new long[temp.arr_n ];
	for(i=0;i<temp.arr_n ;i++)temp.sl[i]=0;
        for(i=0;i<arr_n;i++)
	{
		for(j=0;j<num.arr_n ;j++)
		{
			temp.sl[i+j]+=sl[i]*num.sl[j];
		}
		regulator(&temp);
	}
	sltostr(&temp);
	return temp;
}

//用常规整数进行赋值
void slnum::operator =(const int num)				
{
	char * ss;
	ss=new char[31];
	itoa(num,ss,10);
	setval(ss);
}
//用常规整数串进行赋值
void slnum::operator =(char * num)				
{
	setval(num);
}

slnum abs(const slnum &num)	//求绝对值
{
	slnum temp;
	temp=num;
	temp.sign*=num.sign;
	return temp;
}
//除运算：使用折半试商算法
slnum slnum::operator /(const slnum &num)
{
	int i,en,quot,A,T;
	slnum qt("0"),temp,num0;
        num0=abs(num);
	slnum sureplus("0");
	en=arr_n -num.arr_n ;
  	if(arr_n<num.arr_n )
		return qt;
        else {
		for( i=arr_n -1;i>en;i--)
		{
			sureplus=sureplus*R+sl[i];
		}
                ;
		do
		{
                        //取下一位
                        sureplus=sureplus*R+sl[i];
                        quot=0;A=0;
                        while(sureplus.sign<0||sureplus>=num0 )
			{
                         switch (sureplus.sign )
                         {
                         case 1 :
                         {
                         if (sureplus.arr_n >num0.arr_n )
                                quot=(sureplus.sl[sureplus.arr_n -1]*R+sureplus.sl[sureplus.arr_n -2])/num.sl[num.arr_n -1];
                         else   quot=sureplus.sl[sureplus.arr_n -1]/num.sl[num.arr_n -1];
                         } break;
                         case -1:
                         {
                         if (sureplus.arr_n <num0.arr_n )quot=2;
                            else if  (sureplus.arr_n >num0.arr_n )
                                        quot=(sureplus.sl[sureplus.arr_n -1]*R+sureplus.sl[sureplus.arr_n -2])/num.sl[num.arr_n -1];
                                 else   quot=sureplus.sl[sureplus.arr_n -1]/num.sl[num.arr_n -1];
                         } break;
                         }
			 T=(quot+1)/2;
                         T=T*sureplus.sign ;
                         temp=T;
                         temp=temp*num0;
                         A=A+T  ;
                         sureplus=sureplus-temp;
                        }
		qt=qt*R;
		qt=qt+A;
                --i;
		}
		while(i>=0);
		qt.sign=sign*num.sign ;
                return qt;
        }
}


//与整数的除运算
slnum slnum::operator /( int num)
{
	char * s;
	s=new char[strlen(getval())+1];
	strcpy(s,getval());
	slnum temp(s);
	slnum qt,a;
	a=num;
	qt=temp/a;
	return qt;

}

//求余运算
slnum slnum::operator %(const slnum &num)
{
	slnum temp,sp;
	sp=*this/num;
        temp=sp*num;
	temp=*this-temp;
	return temp;
}

//与常规整数的求余运算
slnum slnum::operator %(int num)
{
	char * s,*sp;
	s=new char[strlen(getval())+1];
	strcpy(s,getval());
	slnum temp(s);
	slnum surepl,a;
	a=num;
	surepl=temp%a;
	return surepl;
}

slnum::~slnum()
{

}