hp.cpp

高精度源程序

#include <stdio.h>
#include <string.h>
#define Maxsize 30000

struct hp
{
    int len;
    int s[Maxsize+1];
};
typedef hp bignum;

void f_input(bignum &a, char *sa);
void f_plus(const bignum &a, const bignum &b, bignum &c);
void f_subtract(const bignum &a, const bignum &b, bignum &c);
void f_hdivision(const bignum &a, const bignum &b, bignum &c, bignum &d);
void f_hmultiply(const bignum &a, const bignum &b, bignum &c);
void f_print(const bignum &c);
void f_multiply10(bignum &a);
int f_cmp(const bignum &a, const bignum &b);

void f_multiply(const bignum &a, int n, bignum &c);
void f_division(const bignum &a, int n, bignum &c, int &residue);

int main()
{
	freopen("hp.txt","r",stdin);
	char sa[Maxsize+1],sb[Maxsize+1],op[10];
	bignum a,b,c,d;
	while((scanf("%s",sa)) != EOF && (scanf("%s",op)) != EOF && (scanf("%s",sb)) != EOF)
	{
		f_input(a,sa);
		f_input(b,sb);
		switch(op[0])
		{
		case '+': f_plus(a,b,c);
			break;
		case '-': f_subtract(a,b,c);
			break;
		case '*': f_hmultiply(a,b,c);
			break;
		case '%':
		case '/': f_hdivision(a,b,c,d);
			break;
		default: printf("\nOperator ERROR\n");
			break;
		}
		if(op[0] == '%')
			f_print(d);
		else
			f_print(c);
	}
	return (0);
}

void f_input(bignum &a, char *sa)
{
	int i;
	a.len=strlen(sa);
	for(i=1; i<=a.len; i++)
	{
		a.s[i]=sa[a.len-i]-'0';
	}
	for(i=a.len+1; i<=Maxsize; i++)
	{
		a.s[i]=0;
	}
}

void f_plus(const bignum &a, const bignum &b, bignum &c)
{
	int i,len;
	for(i=1; i<=Maxsize; i++)
		c.s[i]=0;
	len=a.len>=b.len ? a.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]+=1;
		}
	}
	if(c.s[len+1] >= 1)
		len=len+1;
	c.len=len;
}

void f_subtract(const bignum &a, const bignum &b, bignum &c)
{
	int i,len;
	for(i=1; i<=Maxsize; i++)
	{
		c.s[i]=0;
	}
	len=a.len>=b.len ? a.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]-=1;
		}
	}
	while(len > 1 && c.s[len] == 0) len--;
	c.len=len;
}

void f_print(const bignum &c)
{
	int i;
	for(i=c.len; i>=1; i--)
	{
		printf("%d",c.s[i]);
	}
	printf("\n");
}

void f_multiply(const bignum &a, int n, bignum &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]*n;
		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;
}

void f_division(const bignum &a, int n, bignum &c, int &residue)
{
	int i,len;
	__int64 re;
	for(i=1; i<=Maxsize; i++)
		c.s[i]=0;
	len=a.len;
	re=0;
	for(i=len; i>=1; i--)
	{
		re=re*10+a.s[i]; // re may exceed long
		c.s[i]=(int)(re/n);
		re%=n;
	}
	residue=(int)re;
	while(len > 1 && c.s[len] == 0) len--;
	c.len=len;
}

int f_cmp(const bignum &a, const bignum &b)
{
	int len;
	len=a.len>=b.len ? a.len:b.len;
	while(len >= 1 && a.s[len]==b.s[len]) len--;
	if(len == 0)
		return (0);
	else
		return (a.s[len]-b.s[len]);
}

void f_hmultiply(const bignum &a, const bignum &b, bignum &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;
}

void f_hdivision(const bignum &a, const bignum &b, bignum &c, bignum &d)
{
	int i,len;
	bignum e;
	for(i=1; i<=Maxsize; i++)
	{
		c.s[i]=0;
		d.s[i]=0;
	}
	d.len=1;
	len=a.len;
	for(i=len; i>=1; i--)
	{
		f_multiply10(d);
		d.s[1]=a.s[i];
		while(f_cmp(d,b) >= 0)
		{
			f_subtract(d,b,e);
			d=e;
			c.s[i]++;
		}
	}
	while(len > 1 && c.s[len] == 0) len--;
	c.len=len;
}

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