乘法計(jì)算列表法？
大整數(shù)的乘法
在計(jì)算機(jī)中，長整形（long int）變量的范圍是-2147483648至2147483647，因此若用長整形變量做乘法運(yùn)算，乘積最多不能超過10位數(shù)。即便用雙精度（double）變量，也僅能保證16位有效數(shù)字的精度。在某些需要更高精度的乘法運(yùn)算場合，需要用別的辦法來實(shí)現(xiàn)運(yùn)算。
比較容易想到的是做多位數(shù)乘法時(shí)列豎式進(jìn)行計(jì)算的方法，只要寫出模擬這一過程的程序，就能實(shí)現(xiàn)任意大整數(shù)的乘法運(yùn)算。經(jīng)過查閱資料，找到一種更易于編程的方法，即“列表法”。
下面先介紹“列表法”:
例如當(dāng)計(jì)算8765*234時(shí)，把乘數(shù)和被乘數(shù)照如下列出，見表1：
8
7
6
5
*
16
14
12
10
2
24
21
18
15
3
32
28
24
20
4
表一
16
14
12
10
24
21
18
15
32
28
24
20
16
38
65
56
39
20
16
38
65
56
39
20
2
16+4=20
38+7=45
65+6=71
56+4=60
39+2=41
留2
留0進(jìn)2
留5進(jìn)4
留1進(jìn)7
留0進(jìn)6
留1進(jìn)4
留0進(jìn)2
2
0
5
1
0
1
0
根據(jù)以上思路 就可以編寫C程序了，再經(jīng)分析可得：
1，一個(gè)m位的整數(shù)與一個(gè)n位的整數(shù)相乘，乘積為m+n-1位或m+n位。
2，程序中，用三個(gè)字符數(shù)組分別存儲(chǔ)乘數(shù)，被乘數(shù)與乘積。由第1點(diǎn)分析知，存放乘積的字符數(shù)組餓長度應(yīng)不小于存放乘數(shù)與被乘數(shù)的兩個(gè)數(shù)組的長度之和。
3，可以把第二步“計(jì)算填表”與第三四步“累加進(jìn)位”放在一起完成，可以節(jié)省存儲(chǔ)表格2所需的空間。
4，程序關(guān)鍵部分是兩層循環(huán)，內(nèi)層循環(huán)累計(jì)一數(shù)組的和，外層循環(huán)處理保留的數(shù)字和進(jìn)位。
[cpp] view plain copy
#define MAXLENGTH 1000
#include <stdio.h>
#include <string.h>
void compute(char * a, char * b,char *c)
{
int i,j,m,n;
long sum,carry;
m = strlen(a)-1;
n = strlen(b)-1;
for(i=m;i>=0;i--)
a[i] -= '0';
for(i=n;i >=0;i--)
b[i] -='0';
c[m+n+2] ='/0';
carry =0;
for(i=m+n;i>=0;i--)
{
sum=carry;
if((j=(i-m))<0)
j=0;
for(;j<=i&& j <=n;j++)
sum += a[i-j]b[j];
c[i+1] = sum %10 + '0'; /*算出保留的數(shù)字*/
carry = sum/10;
}
if((c[0]=carry+'0')=='0') /* if no carry*/
c[0] = '/040'; /* space */
}
int main()
{
char a[MAXLENGTH],b[MAXLENGTH],c[MAXLENGTH*2];
puts("Input multiplier");
gets(a);
puts("Input multiplier");
gets(b);
compute(a,b,c);
puts("Answer:");
puts(c);
getchar();
}
效率分析：用以上算法計(jì)算m位整數(shù)乘以n位整數(shù)，需要先進(jìn)行m*n次乘法，再進(jìn)行約m+n次加法運(yùn)算和m+n次取模運(yùn)算（實(shí)為整數(shù)除法）。把這個(gè)程序稍加修改，讓它自己生產(chǎn)乘數(shù)和被乘數(shù)，然后計(jì)算機(jī)隨機(jī)的7200為整數(shù)互乘。
經(jīng)過改進(jìn)，此算法效率可以提高約9倍。
注意到以下事實(shí)：8216547*96785 將兩數(shù)從個(gè)位起，每3位分為節(jié)，列出乘法表，將斜線間的數(shù)字相加：
8 216 547
96 785
8
216
547
*
768
20736
52512
96
6250
169560
429395
785
768
20736
52512
6250
169560
429395
768
27016
222072
429395
將表中最后一行進(jìn)行如下處理：從個(gè)位數(shù)開始，每一個(gè)方格里只保留三個(gè)數(shù)字，超出1000的部分進(jìn)位到前一個(gè)方格里：
768
27016
222072
429395
768+27=795
27016+222=27238
222072+429=222501
留395進(jìn)429
795
238
501
395
所以8216547*96785 = 795238501395
也就是說我們在計(jì)算生成這個(gè)二維表時(shí)，不必一位一位的乘，而可以三位三位的乘；在累加時(shí)也是滿1000進(jìn)位。這樣，我們計(jì)算m位整數(shù)乘以n位整數(shù)，只需要進(jìn)行m*n/9次乘法運(yùn)算，再進(jìn)行約（m+n）/3次加法運(yùn)算和（m+n）/3次去摸運(yùn)算。總體看來，效率是前一種算法的9倍。
有人可能會(huì)想：既然能用三位三位的乘，為什么不能4位4位的乘，甚至5位。聽我解來：本算法在累加表中斜線間的數(shù)字時(shí)，如果用無符號長整數(shù)（范圍0至~4294967295）作為累加變量，在最不利的情況下（兩個(gè)乘數(shù)的所有數(shù)字均為9），能夠累加約4294967295/（999*999）=4300次，也就是能夠準(zhǔn)確計(jì)算任意兩個(gè)約不超過12900（每次累加的結(jié)果“值”三位，故4300*3=12900）位的整數(shù)相乘。如果4位4位地乘，在最不利的情況下，能過累加月4294967295/(9999*9999)=43次，僅能夠確保任意兩個(gè)不超過172位的整數(shù)相乘，沒什么實(shí)用價(jià)值，更不要說5位了。
[cpp] view plain copy
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#define N 7200 //做72xx位的整數(shù)乘法
int max(int a,int b,int c)
{
int d = (a >b)?a:b;
return (d>c)?d:c;
}
int initarray(int a[])
{
int q,p,i;
q = N + random(100);
if(q%3 ==0)
p =q/3;
else
p =q/3+1;
for(i=0;i <p;i++)
a[i] = random(1000);
if(q%3 ==0)
a[0] = 100+random(900);
if(q%3 == 2)
a[0] = 10 + random(90);
if(q%3 == 1)
a[0] = 1 + random(9);
return p;
}
void write(int a[],int l)
{
int i;
char string[10];
for(i=1;i<l;i++)
{
itoa(a[i],string,10);
if(strlen(string)==1)
fprintf(fp,"00");
if(strlen(string)==2)
fprintf(fp,"0");
fprintf(fp,"%s",string);
if((i+1)%25 == 0)
fprintf(fp,"/n");
}
fprintf(fp,"/n");
fprintf(fp,"/n");
}
FILE * fp;
int main()
{
int a[5000]={0},b[5000]={0},k[10001]={0};
unsigned long c,d,e;//申明作累加用的無符號長整數(shù)變量
int i,j,la,lb,ma,mi,p,q,t;
randomize();//初始化隨機(jī)數(shù)
la = initarray(a);//被乘數(shù)
lb = initarray(b);//乘數(shù)
if(la < lb)//如果被乘數(shù)長度小于乘數(shù)，則交換被乘數(shù)與乘數(shù)
{
p = (lb > la)?lb:la;
for(q=0;q<p;q++)
t=a[q],a[q]=b[q],b[q]=t;
t =la,la=lb,lb =t;
}
c=d=0;
for(i=la+lb-2;i>=0;i--)//累加斜線間的數(shù)，i位橫縱坐標(biāo)之和
{
c=d;//將前一位的進(jìn)位標(biāo)志存入累加變量C
ma =max(0,i-la+1,i-lb+1);//求累加的下限
mi = (i > la)?(la-1):i;//求累加的上限
for(j=ma;;j<=mi;j++)
{
c+=a[j]b[i-j];
}
d=c/1000;//求進(jìn)位標(biāo)志
if(c>999)
c%=1000;//取c的后3位
k[i] = c;//保存至表示乘積的數(shù)組k[]
}
e = k[0] + 1000*d;//求出乘積的最高位
fp = fopen("res.txt","w+");
fprintf(fp,"%d",a[0]);//打印被乘數(shù)的最高位
write(a,la);//打印被乘數(shù)其他位數(shù)
fprintf(fp,"%d",b[0]);//打印乘數(shù)的最高位
write(b,lb);//打印乘數(shù)其他位數(shù)
fprintf(fp,"%d",e);//打印乘積的最高位
write(k,la+lb-1);//打印乘積其他位數(shù)
fclose(fp);
}