在計算機中，長整型(long int)變量的范圍是 -2147483648 至 2147483647，因此若用長整型變量做乘法運算，乘積最多不能超過 10位數(shù)。即便用雙精度型(double)變量，也僅能保證 16 位有效數(shù)字的精度。在某些需要更高精度的乘法運算的場合，需要用別的辦法來實現(xiàn)乘法運算。
比較容易想到的是做多位數(shù)乘法時列豎式進行計算的方法，只要寫出模擬這一過程的程序，就能實現(xiàn)任意大整數(shù)的乘法運算。經(jīng)過查閱資料，找到一種更易于編程的方法，即“列表法”。
下面先介紹“列表法”：
例如當計算8765 x 234時，把乘數(shù)與被乘數(shù)照如下列出，見表1：
8 7 6 5 8765
2 16 14 12 10 2
3 24 21 18 15 3
4 32 28 24 20 4
表 1 表 2
把每個空格所在的行列的數(shù)字的乘積填入空格中，得表2。把表2中的數(shù)按圖示斜線分組（橫縱坐標和相等的數(shù)分為一組），把每組數(shù)的累加起來所得的和記在表格下方，見表 3：
16 14 12 10
24 21 18 15
32 28 24 20
16 38 65 56 39 20
表 3
最后把表格下方一行數(shù)作如下處理，見表4：
從最低位的 20 開始，保留個位數(shù)字“0”，把個位以外的數(shù)“2”進到前一位；把次低位的 39 加上低位進上來的 2 得 41，保留個位數(shù)字“1”，把“4”進到前一位；以此類推，直至最高位的 16，16 加上低位進上來的4得 20，保留“0”，把2進到最高位，得乘積答數(shù) 2051010。
16 38 65 56 39 20
2 16+4=20 38+7=45 65+6=71 56+4=60 39+2=41
留0進2 留5進4 留1進7 留0進6 留1進4 留0進2
2 0 5 1 0 1 0
表 4
根據(jù)以上思路就可以編寫C 程序了，再經(jīng)分析可得：
1、一個m 位的整數(shù)與一個 n 位的整數(shù)相乘，乘積為m+n-1 位或m+n 位。
2、程序中，用三個字符數(shù)組分別存儲乘數(shù)、被乘數(shù)與乘積。由第 1 點分析知，存放乘積的字符數(shù)組
的長度應不小于存放乘數(shù)與被乘數(shù)的兩個數(shù)組的長度之和。
3、可以把第二步“計算填表”與第三四步“累加進位”放在一起完成，可以節(jié)省存儲表格 2所需的空間。
4、程序關(guān)鍵部分是兩層循環(huán)，內(nèi)層循環(huán)累計一組數(shù)的和，外層循環(huán)處理保留的數(shù)字與進位。
編寫的程序如下：
程序 1 清單：
/* multiply.c */
/* 11/20/2008 */
#define MAXLENGTH 1000
#include
#include
void compute(char *a, char *b, char *c);
void main(void)
{
char a[MAXLENGTH], b[MAXLENGTH], c[MAXLENGTH * 2];
puts("Input multiplier :");
gets(a);
puts("Input multiplicand :");
gets(b);
compute(a, b, c);
puts("Answer :");
puts(c);
getchar();
}
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--) /* i 為坐標和 */
{
sum = carry;
if ((j = i - m) < 0)
j = 0;
for ( ; j<=i && j<=n; j++) /* j 為縱坐標 */
sum += a[i-j] * b[j]; /* 累計一組數(shù)的和 */
c[i + 1] = sum % 10 + '0'; /* 算出保留的數(shù)字 */
carry = sum / 10; /* 算出進位 */
}
if ((c[0] = carry+'0') == '0') /* if no carry, */
c[0] = '\040'; /* c[0] equals to space */
}
效率分析：用以上算法計算 m位整數(shù)乘以n 位整數(shù)，需要先進行 m x n次乘法運算，再進行約 m
+ n次加法運算和 m + n次取模運算(實為整數(shù)除法)。把這個程序稍加修改，讓它自己產(chǎn)生乘數(shù)與被乘
數(shù)，然后計算隨機的 7200位整數(shù)互乘，在Cyrix 6x86 pr166機器的純DOS方式下耗時 7秒(用Borland C
3.1編譯)。
經(jīng)過改進，此算法效率可以提高約9 倍。
注意到以下事實：8216547 x 96785 將兩數(shù)從個位起，每 3位分為節(jié)，列出乘法表，將斜線間的
數(shù)字相加；
8 216 547
96 785
768 20736 52512
6280 169560 429395
768 27016 222072 429395
將表中最后一行進行如下處理：從個位數(shù)開始，每一個方格里只保留三位數(shù)字，超出 1000 的部
分進位到前一個方格里；
768 27016 222072 429395
768+27 27016+222 222072+429
=795 =27238 =222501 395
795 238 501 395
所以8216547 x 96785 = 795238501395
也就是說我們在計算生成這個二維表時，不必一位一位地乘，而可以三位三位地乘；在累加時也是滿1000進位。這樣，我們在計算 m位整數(shù)乘以 n位整數(shù)，只需要進行 m x n / 9次乘法運算，再進行約(m + n) / 3次加法運算和(m + n) /3 次取模運算。總體看來，效率約是前一種算法的 9倍。
有人可能會想：既然能夠三位三位地乘，為什么不4位 4位甚至5位5位地乘呢？那不是可以提高 16 乃至 25 倍效率嗎？聽我解來：本算法在累加表中斜線間的數(shù)字時，如果用無符號長整數(shù)(范圍 0至~4294967295)作為累加變量，在最不利的情況下(兩個乘數(shù)的所有數(shù)字均是 9)，能夠累加約4294967295/(999*999)=4300 次，也就是能夠準確計算任意兩個均不超過 12900(每次累加的結(jié)果"值"三位，故 4300*3=12900)位的整數(shù)相乘。如果 4 位 4 位地乘，在最不利的情況下，能夠累加約4294967295/(9999*9999)=43 次，僅能夠確保任意兩個不超過 172 位的整數(shù)相乘，沒有什么實用價值，更不要說5位了。
請看改進后的算法的實例程序：
該程序隨機產(chǎn)生兩個72xx位的整數(shù)，把乘數(shù)與積保存在 result.txt中。
在Borland C++ 3.1 中用
BCC -3 -O2 -G -mh -Z -f287 -pr -T- dashu.cpp
編譯生成的exe文件在Cyrix 6x86 pr166的機器上運行耗時0.82 秒。
程序 2 清單：
#include
#include
#include
#include
#include
#define N 7200 //作 72xx 位的整數(shù)乘法
int max(int,int,int);
int initarray(int a[]);
void write(int a[],int l);
FILE *fp;
void main()
{
int a[5000]={0},b[5000]={0},k[10001]={0}; //聲明存放乘數(shù)、被乘數(shù)與積的數(shù)組
clock_t start, end; //聲明用于計時的變量
unsigned long c,d,e; //聲明作累加用的無符號長整數(shù)變量
int i,j,la,lb,ma,mi,p,q,t; //聲明其它變量
randomize(); //初始化隨機數(shù)
la=initarray(a); //產(chǎn)生被乘數(shù)，并返回其長度
lb=initarray(b); //產(chǎn)生乘數(shù)，并返回其長度
if(lala)?lb:la;
for (q=0;q=0;i--) //累加斜線間的數(shù)，i 為橫縱坐標之和
{
c=d; //將前一位的進位標志存入累加變量 c
ma=max(0,i-la+1,i-lb+1); //求累加的下限
mi=(i>la-1)?(la-1):i; //求累加的上限
for(j=ma;j<=mi;j++) //計算出橫縱坐標之和為 i 的單元內(nèi)的數(shù),并累加到 C 中
c+=(long)a[j]*b[i-j];
d=c/1000; //求進位標志
if(c>999)
c%=1000; //取 c 的末三位
k[i]=c; //保存至表示乘積的數(shù)組 k[]
}
e=k[0]+1000*d; //求出乘積的最高位
end = clock();//停止計時
fp = fopen("result.txt", "w+"); //保存結(jié)果到 result.txt
printf("\nThe elapsed time was: %3.4f\n", (end - start) / CLK_TCK);
//打印消耗的時間
fprintf(fp,"%d",a[0]); //打印被乘數(shù)最高位
write(a,la); //打印被乘數(shù)其他位
fprintf(fp,"%d",b[0]); //打印乘數(shù)最高位
write(b,lb); //打印乘數(shù)其他位
fprintf(fp,"%ld",e); //打印乘積最高位
write(k,la+lb-1); //打印乘積其他位
fclose(fp);
}
max(int a,int b,int c)
{
int d;
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;iposted on 2009-12-06 23:26 chatler 閱讀(1138) 評論(0) 編輯 收藏 引用 所屬分類: Algorithm