玩算法----关于精确计算乘法(80分)

两个100位到500位的整数相乘，如何得到精确的结果？精确到个位。我只想到用字符串，但是，这样太复杂了，各位有什么好方法吗？

用浮点数做，保留所有的小数位。

以前有過這樣的帖子的。
人家好象算10000!幾秒就搞定了。
用數組。
最初級的當然是數組的每一就是數的一位。
厲害點的就是數組的每一項表示這個數的N位。N取什麼值有講究。查查以前的帖子吧。

楼上的，找得到以前的那张贴子吗？

當時就粗粗的看了一下。我看帖子常常只看個大概。
現在很難找。
難道不在數據結構裡面的？我找遍了也找不到
只能等哪位大俠出手了

说说实用价值！￣！！！！！！

外甥要参加计算机奥林匹克竞赛，以前的一道题，偶想找找好的算法。没有商业价值的。

奥林匹克一般不会出高精度运算，就是出也是第一道用来热身的。
通常是用字符串来做，也可以用整形数组做，效率要高一点，一个数可以表示5位。

最简单的模拟，就是O(n^2) 复杂度，很简单
#include <stdio.h>
#include <string.h>
#include <math.h>
class Bignum{
public:
int num[201];
int bit;
Bignum(int x=0){ // if x=1234567 then
num[0]=7
bit=0;
memset(num,0,sizeof(num));
if(x==0)bit=1;
while(x!=0) { num[bit++]=x%10;
x/=10;
}
};
void print();
Bignum operator +(const Bignum &amp;b);
Bignum operator -(const Bignum &amp;b);
Bignum operator *(const Bignum &amp;b);
Bignum operator *(const int &amp;b);
Bignum operator /(const Bignum &amp;b);
Bignum operator /(const int &amp;b);
bool operator >(const Bignum &amp;b);
};

void Bignum:rint(){
int i;
for(i=bit-1;i>=0;i--) printf("%d",num);
printf("/n");
}

bool Bignum:perator >(const Bignum &amp;b)
{
Bignum a;
a=*this;
if(a.bit > b.bit)return true;
if(a.bit < b.bit)return false;
for(int x=a.bit-1;x>=0;x--) {
if(a.num [x]>b.num [x])return true;
if(a.num [x]<b.num [x])return false;
}
return false;
}

Bignum Bignum:perator +(const Bignum &amp;b)
{
Bignum a;
a=*this;
Bignum temp(0);
int x,c;
int ct=0,e;
int top=0;
e = a.bit>b.bit ?a.bit:b.bit ;
for(x=0;x<e;x++)
{
c=(ct +a.num[x] +b.num[x] );
temp.num[x]=c%10;
ct =c/10;
}
top=e-1;
while(ct!=0){temp.num[++top]=ct%10;
ct=ct/10;}
temp.bit=top+1;
return temp;
}

Bignum Bignum:perator -(const Bignum &amp;b)
{
Bignum a;
a=*this;
Bignum temp(0);
int x,c;
int ct=0,e;
e = a.bit>b.bit ?a.bit:b.bit ;
for(x=0;x<e;x++)
{
if(a.num[x]>=(b.num[x]+ct))
{c=(a.num[x] -b.num[x]-ct );ct=0;}else

{c=(a.num[x]+10-b.num[x]-ct);ct=1;}
temp.num[x]=c%10;
}
for(x=e-1;x>=0;x--)if(temp.num[x]){temp.bit =x+1;break;}
return temp;
}

Bignum Bignum:perator *(const int &amp;b)
{
Bignum a;
a=*this;
Bignum temp(0);
int x,ct=0,top=a.bit-1;
for(x=0;x<a.bit ;x++){
temp.num [x]=(a.num [x]*b+ct)%10;
ct =(a.num [x]*b+ct)/10;
}
while(ct!=0){temp.num [++top]=ct%10;ct=ct/10;}
temp.bit =top+1;
return temp;
}

Bignum Bignum:perator *(const Bignum &amp;b)
{
Bignum a;
a=*this;
int x,y;
int ct,t,c;
int top=0;
Bignum temp(0);
for(ct=x=0;x<a.bit;x++,ct=0)
{
for(y=0;y<b.bit;y++)
{
t = temp.num[x+y];
c = ( ct + t + a.num[x]*b.num[y] );
temp.num[x+y]=c%10;
ct = c/10;
top=x+y;
}
while(ct!=0){temp.num[++top]=ct%10;ct=ct/10;}
}
for(x=top+1;x>=0;x--)if(temp.num[x]){temp.bit =x+1;break;}
return temp;
}

Bignum Bignum:perator /(const int &amp;b)
{
Bignum a;
a=*this;
Bignum temp(0);
int x, ct=0,t=0,qu,top=0,quotient=0;
for(x=a.bit -1;x>=0;x--)
{
qu=(ct*10+a.num[x])/b;
ct=(ct*10+a.num[x])%b;
if((qu!=0)&amp;&amp;(top==0)){top=x;t=x;quotient=1;}
if(quotient) { temp.num[t]=qu;t--;}
}
temp.bit = top+1;
return temp;
}

Bignum Bignum:perator /(const Bignum &amp;b)
{
Bignum a;
a=*this;
Bignum temp(0),remind(0);
int x;
for(x=b.bit-2,remind.bit=b.bit-1>0?b.bit-1:1;x>=0;x--)remind.num [remind.bit-1-x]=a.num [a.bit-1-x];
for(x=a.bit-b.bit;x>=0;x--)
{
remind=remind*Bignum(10);remind.num[0]=a.num[x];
while(remind>b)
{remind=remind-b;temp.num[x]++;}
}
for(x=a.bit-b.bit;x>=0;x--)if(temp.num[x]){temp.bit=x+1;break;}
return temp;
}

http://www.delphibbs.com/delphibbs/dispq.asp?lid=494104

你把这个运行一下，看看用时多少。完全是O(N^2)的。没
有任何优化
http://www.delphibbs.com/delphibbs/dispq.asp?lid=494104
10000! 要30s. 夸张
#include <stdio.h>
#include <time.h>
const int M = 10000;
const int N = 10000;
/*
N!
如果 N 再大点，就把M开大点
自己估计一下 N!有多少位就行了
*/
int mul(int a[],int n1,int b[],int n2,int c[]) {
int begin
c,inc;
int m,i,j;
m=n1+n2+3;
for( i=0;i<=m;i++) c=0;
for( i=1;i<=n2;i++) {
begin
c=i-1;
inc=0;
for( j=1;j<=n1;j++) {
begin
c++;
m=c[begin
c]+b*a[j]+inc;
inc=m/10000;
c[begin
c]=m-inc*10000;
}
if(inc>=1) c[begin
c+1]=inc;
}
if(inc>=1) {
begin
c++;
c[begin
c]=inc;
}
return begin
c;
}
void print(int a[],int len) {
int i;
if(!(len>1 &amp;&amp;
a[len]==0)) printf("%d",a[len]);
for(i=len-1;i>=1;i--) {
if(a>=1000) printf("%d",a);
else
if(a>=100) printf("0%d",a);
else
if(a>=10) printf("00%d",a);
else
if(a>=1) printf("000%d",a);
else
printf("0000");
}
printf("/n");
}
int main() {
freopen("output.out","w",stdout);
int p[2][M], con[2];
int l[2],i;
int pre,cur;
p[0][1]=l[0]=1;
pre = 0;
cur = 1;
for(i=2;i<=N;i++) {
con[1] = i;
l[cur] = mul(p[pre],l[pre],con,1,p[cur]);
pre = 1-pre;
cur = 1-cur;
}
print(p[pre],l[pre]);
double qq;
printf("use time = %.5lfs/n",(qq=clock())/CLK_TCK);
return 0;
}