高精度.cpp

主要用于acm/icpc竞赛中的高精度计算

高精度运算专题

1.专题函数说明

说明：



本栏为本专题所有程序的公用部分，调用本专题任何一个程序必须加上本栏的代码


input/print为高精度数输入输出，调用格式为input(hp HightPoint,"123456")/print(hp HighPoint)


本栏为纯C++代码

源程序：



#include <iostream> 

using namespace std;

#define maxsize 100

struct hp
{
	int len;
	int s[maxsize+1];
};


void input(hp &a,string str)
{
	int i;
	while(str[0]=='0' && str.size()!=1)
		str.erase(0,1);
	a.len=(int)str.size();
	for(i=1;i<=a.len;++i)
		a.s[i]=str[a.len-i]-48;
	for (i=a.len+1;i<=maxsize;++i)
		a.s[i]=0;
}

void print(const hp &y)
{
	int i;
	for(i=y.len;i>=1;i--)
		cout<<y.s[i];
	cout<<endl;
}




2.高精度数比较

语法：int result=compare(const hp &a,const hp &b);

参数：

a,b：
进行比较的高精度数字

返回值：
比较结果，a>b返回正数，a=b返回0，a<b返回负数

源程序：



int compare(const hp &a,const hp &b)
{
	int len;
	if(a.len>b.len)
		len=a.len;
	else
		len=b.len;
	while(len>0 && a.s[len]==b.s[len]) len--;
	if(len==0)
		return 0;
	else
		return a.s[len]-b.s[len];
} 




3.高精度数加法

语法：plus(const hp &a,const hp &b,hp &c);

参数：

a,b：
进行加法的高精度数字

返回值：
返回相加结果到c中

源程序：



void plus(const hp &a,const hp &b,hp &c)
{
	int i,len;
	for(i=1;i<=maxsize;i++) c.s[i]=0;
	if(a.len>b.len) len=a.len;
	else len=b.len;
	for(i=1;i<=len;i++)
	{
		c.s[i]+=a.s[i]+b.s[i];
		if(c.s[i]>=10)
		{
			c.s[i]-=10;
			c.s[i+1]++;
		}
	}
	if(c.s[len+1]>0) len++;
	c.len=len;
}




4.高精度数减法

语法：subtract(const hp &a,const hp &b,hp &c);

参数：

a,b：
进行减法的高精度数字，a是被减数，b是减数，不支持负数

返回值：
返回结果到c中

源程序：



void subtract(const hp &a,const hp &b,hp &c)
{
	int i,len;
	for(i=1;i<=maxsize;i++) c.s[i]=0;
	if(a.len>b.len) len=a.len;
	else len=b.len;
	for(i=1;i<=len;i++)
	{
		c.s[i]+=a.s[i]-b.s[i];
		if(c.s[i]<0)
		{
			c.s[i]+=10;
			c.s[i+1]--;
		}
	}
	while(len>1&&c.s[len]==0) len--;
	c.len=len;
}




5.高精度乘10 

语法：multiply10(hp &a);

参数：

a：
进行乘法的高精度数字

返回值：
返回结果到 a 中

源程序：



void multiply10(hp &a)
{
	int i;
	for(i=a.len;i>=1;i--)
		a.s[i+1]=a.s[i];
	a.s[1]=0;
	a.len++;
	while(a.len>1&&a.s[a.len]==0) a.len--;
}




6.高精度乘单精度

语法：multiply(const hp &a,int b,hp &c);

参数：

a：
进行乘法的高精度数字

b：
进行乘法的单精度数字

返回值：
返回结果到 c 中

源程序：



void multiply(const hp &a,int b,hp &c)
{
	int i,len;
	for(i=1;i<=maxsize;i++) c.s[i]=0;
	len=a.len;
	for(i=1;i<=len;i++)
	{
		c.s[i]+=a.s[i]*b;
		c.s[i+1]+=c.s[i]/10;
		c.s[i]%=10;
	}
	len++;
	while(c.s[len]>=10)
	{
		c.s[len+1]+=c.s[len]/10;
		c.s[len]%=10;
		len++;
	}
	while(len>1&&c.s[len]==0) len--;
	c.len=len;
}




7.高精度乘高精度

语法：multiplyh(const hp &a,const hp &b,hp &c);

参数：

a,b：
进行乘法的高精度数字

返回值：
返回结果到 c 中

源程序：



void multiplyh(const hp &a,const hp &b,hp &c)
{
	int i,j,len;
	for(i=1;i<=maxsize;i++) c.s[i]=0;
	for(i=1;i<=a.len;i++)
		for(j=1;j<=b.len;j++)
		{
			c.s[i+j-1]+=a.s[i]*b.s[j];
			c.s[i+j]+=c.s[i+j-1]/10;
			c.s[i+j-1]%=10;
		}
		len=a.len+b.len+1;
		while(len>1&&c.s[len]==0) len--;
		c.len=len;
}




8.高精度除单精度

语法：divide(const hp &a,int b,hp &c,int &d);

参数：

a：
进行除法的高精度数字

返回值：
返回商到 c 中，余数到 d 中

源程序：



void divide(const hp &a,int b,hp &c,int &d)
{
	int i,len;
	for(i=1;i<=maxsize;i++) c.s[i]=0;
	len=a.len;
	d=0;
	for(i=len;i>=1;i--)
	{
		d=d*10+a.s[i];
		c.s[i]=d/b;
		d%=b;
	}
	while(len>1&&c.s[len]==0) len--;
	c.len=len;
}




9.高精度除高精度

语法：divideh(const hp &a,const hp &b,hp &c,hp &d);

参数：

a，b：
进行除法的高精度数字

返回值：
返回商到 c 中，余数到 d 中

注意：



需要compare、multiply10、subtract

源程序：



void divideh(const hp &a,const hp &b,hp &c,hp &d)
{
	hp e;
	int i,len;
	for(i=1;i<=maxsize;i++)
	{
		c.s[i]=0;
		d.s[i]=0;
	}
	len=a.len;
	d.len=1;
	for(i=len;i>=1;i--)
	{
		multiply10(d);
		d.s[1]=a.s[i];
		while(compare(d,b)>=0)
		{
			subtract(d,b,e);
			d=e;
			c.s[i]++;
		}
	}
	while(len>1&&c.s[len]==0) len--;
	c.len=len;
}