Question

求助 c语言实现高精度乘法

Answer 1

Hpre.h 文件

//HighPrecision
// 1234567890 高位存在数组最末
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
const int maxlen=300;
class HP{
public:

HP()
HP(int inte,int len);
~HP() ;//
HP(int inte);
HP(const char*str);
int HP_DectoB(int sum,int b,int *S);

friend ostream& operator << (ostream &cout,const HP &x)
{
if(x.sign_bit) cout<<"-";
for(int i=x.len;i>0;i--)
{
cout<<x.num.at(i);
if((i-1)%3==0 && i!=1) cout<<",";
}
return cout;
}
HP operator=(int inte);
HP operator=(const char* str);
HP operator*(const HP &b);
HP operator+(const HP &b);
HP operator-(const HP &b);
HP operator/(const HP &b);
HP operator%(const HP &b);
HP operator++();
HP operator++(int);//后置自增运算符
HP operator--();
HP operator--(int);

int Compare(const HP &b);
HP GCD(const HP b);

private:
int len;
vector<int> num;
bool sign_bit;//符号位 1 - 0 +
};

/////////////////////////////
Hpre.cpp 文件

#include "HPre.h"

#include "HPre.h"

HP::HP(int inte)
{
if(inte<0) sign_bit=1;
else sign_bit=0;
num.clear();
num.push_back(0);

if(inte==0)
for(len=0;inte>0;)

}

HP::HP(const char*str)
{
num.clear();
num.push_back(0);
if(str[0]!='-') sign_bit=0,str++;
else sign_bit=1;
len=strlen(str);
for(int i=1;i<=len;i++) num.push_back(str[len-i]-'0');
}

HP HP::operator=(int inte)
{
if(inte<0) sign_bit=1;
else sign_bit=0;
num.clear();
num.push_back(0);
if(inte==0)
for(len=0;inte>0;)
return (*this);
}

HP HP::operator=(const char *str)
{
if(str[0]!='-') sign_bit=0,str++;
else sign_bit=1;
len=strlen(str);
num.push_back(0);
for(int i=1;i<=len;i++) num.push_back(str[len-i]-'0');
return (*this);
}

HP HP::operator*(const HP &b)
{
int i,j;
int c_len=len+b.len;
HP c(0);
c.num.resize(c_len+1,0);
if(this->sign_bit!=b.sign_bit) c.sign_bit=1;
else c.sign_bit=0;

for(i=1;i<=len;i++)
for(j=1;j<=b.len;j++) c.num[i+j-1]+=num[i]*b.num[j];
for(i=1;i<c_len;i++)
while(c.num[i])
while(i>1 && !c.num[i]) i--;
c.len=i;
return c;
}

HP HP::operator-(const HP &b)
{
int i,j;
HP c;
int tlen=0;
if(b.len>this->len) tlen=b.len;
else tlen=this->len;
c.num.resize(tlen+1,0);
if(Compare(b)>=0) c.sign_bit=0;
else c.sign_bit=1;

for(i=1,j=0;i<=len;i++)
{
c.num[i]=num[i]-j;
if(i<=b.len) c.num[i]-=b.num[i];
if(c.num[i]<0)
else j=0;
}
c.len=len;
while(c.len>1 && !c.num[c.len]) c.len--;
return c;
}

HP HP::operator/(const HP &b)
{
int i,j;
HP d(0),c;
int tlen=0;
if(b.len>this->len) tlen=b.len;
else tlen=this->len;
c.num.resize(tlen+1,0);//商
d.num.resize(tlen+1,0);//余数
if(this->sign_bit!=b.sign_bit) c.sign_bit=1;
else c.sign_bit=0;

for(i=len;i>0;i--)
{
if(!(d.len==1 && d.num[1]==0))//除数不为0
{
for(j=d.len;j>0;j--)
d.num[j+1]=d.num[j];
++d.len;
}
d.num[1]=num[i];c.num[i]=0;
while( (j=d.Compare(b))>=0)
{ d=d-b; c.num[i]++;
if(j==0) break;
}
}
c.len=len;
while((c.len>1)&&(c.num[c.len]==0)) c.len--;
return c;
}

HP HP::operator+(const HP &b)
{
int i;
HP c;
int tlen=0;
if(b.len>this->len) tlen=b.len;
else tlen=this->len;
c.num.resize(tlen,0);
c.num[1]=0;
for(i=1;i<=len||i<=b.len || c.num[i];i++){
if(i<=len) c.num[i]+=num[i];
if(i<=b.len) c.num[i]+=b.num[i];
c.num.push_back(c.num[i]/10); c.num[i]%=10;
}
c.len=i-1; if(c.len==0) c.len=1;
return c;
}

int HP::Compare(const HP&y)
{
if(len>y.len) return 1;
if(len<y.len) return -1;
int i=len;
while((i>1) &&(num[i]==y.num[i])) i--;
return num[i]-y.num[i];
}

HP HP::operator %(const HP &b)
{
int i,j;
HP d(0);
int tlen=b.len;
d.num.resize(tlen+3,0);

for(i=len;i>0;i--)
{
if(!(d.len==1 && d.num[1]==0))
{
int t=d.num.size()-1;
if(t==d.len) d.num.push_back(0);
for (j=d.len;j>0;j--)
d.num[j+1]=d.num[j];
++d.len;
}
d.num[1]=num[i];

while ((j=d.Compare(b)>=0))
{
d=d-b;
if(j==0) break;
}
}
return d;
}

HP HP::GCD(HP b)
{
HP d(1);
const HP zero(0);
int d_len=0;
if(len>b.len) d_len=b.len;
else d_len=len;
d.num.resize(d_len+2);
d=*this%b;
if(d.Compare(zero)==0)

else return b.GCD(d);
}

//////////////////////
main.cpp文件

#include <iostream>
#include "HPre.h"
using namespace std;

#include <iostream>
#include "HPre.h"
using namespace std;

int main()
{
HP t("18446744073709551616");//2^64
HP a(12);
HP b(9);
HP c(3);
a=a*t;
b=b*t;
cout<<a.GCD(b)<<endl;
cout<<c*t<<endl;

return 1;
}

验算没错 不知道有其他错误没 自己写的类

Answer 2

最大位数不超过50000。

#include<stdio.h>
#include<string.h>
int main()
{
char a[50001],b[50001];
int a1[50001],b1[50001],c[100002];
int lena,lenb,i,j,flag;
while(scanf("%s",a)!=EOF)
{
scanf("%s",b);
getchar();
j=0;
memset(a1,0,sizeof(a1));
memset(b1,0,sizeof(b1));
memset(c,0,sizeof(c));
lena=strlen(a);
lenb=strlen(b);
for(i=lena-1;i>=0;i--)
a1[j++]=a[i]-'0';
j=0;
for(i=lenb-1;i>=0;i--)
b1[j++]=b[i]-'0';
for(j=0;j<lenb;j++)
{
for(i=0;i<lena;i++)
c[i+j]=b1[j]*a1[i];
}
for(i=0;i<lena+lenb;i++)
{
if(c[i]>=10)
{
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
flag=0;
for(i;i>=0;i--)
{
if(flag==1)printf("%d",c[i]);
else
{
if(c[i]!=0)
{
printf("%d",c[i]);flag=1;
}
}
}
if(flag==0)printf("0\n");
else printf("\n");
}
return 0;
}