C語(yǔ)言中超大整數(shù)乘法運(yùn)算

1、C語(yǔ)言中超大整數(shù)乘法運(yùn)算在計(jì)算機(jī)中，長(zhǎng)整型(longint)變量的范圍是-48至47,因此若用長(zhǎng)整型變量做乘法運(yùn)算，乘積最 多不能超過(guò)10位數(shù)。即便用雙精度型(double)變量，也僅能保證16位有效數(shù)字的精度。在某些 需要更高精度的乘法運(yùn)算的場(chǎng)合，需要用別的辦法來(lái)實(shí)現(xiàn)乘法運(yùn)算。比較容易想到的是做多位數(shù)乘法時(shí)列豎式進(jìn)行計(jì)算的方法，只要寫(xiě)出模擬這一過(guò)程的程序，就能 實(shí)現(xiàn)任意大整數(shù)的乘法運(yùn)算。經(jīng)過(guò)查閱資料，找到一種更易于編程的方法，即列表法。下面先介紹列表法: 例如當(dāng)”算8765x234時(shí)，把乘數(shù)與被乘數(shù)照如下列出，見(jiàn)表1：$7 I65X16141210242118153322824204表1把表

2、1中的數(shù)按圖示斜線(xiàn)分組(橫縱坐標(biāo)和相等的數(shù)分為一組)，把每組數(shù)的累加起來(lái)所得的 和記在表格下方，見(jiàn)表2：161412102421181532282420163865563920表2從最低位的20開(kāi)始，保留個(gè)位數(shù)字0，把個(gè)位以外的數(shù)2進(jìn)到前一位；把次低位的39加上低 位進(jìn)上來(lái)的2得41,保留個(gè)位數(shù)字1,把4進(jìn)到前一位；以此類(lèi)推,直至最高位的16, 16加 上低位進(jìn)上來(lái)的4得20,保留0，把2進(jìn)到最高位，得乘積答數(shù)2051010。163265563920216+4=2。38+7=4565+6=7156+4=6039+2=41留2留0進(jìn)2留5進(jìn)4留值7留說(shuō)6留1進(jìn)4留。進(jìn)22057010表3根據(jù)以上

3、思路就可以編寫(xiě)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ù)組的長(zhǎng)度應(yīng)不小于存放乘數(shù)與被乘數(shù)的兩個(gè)數(shù)組的長(zhǎng)度之和。3、可以把第二步計(jì)算填表與第三四步累加進(jìn)位放在一起完成，可以節(jié)省存儲(chǔ)表格2所需的 空間。4、程序關(guān)鍵部分是兩層循環(huán)，內(nèi)層循環(huán)累計(jì)一組數(shù)的和，外層循環(huán)處理保留的數(shù)字與進(jìn)位。編寫(xiě)的程序如下：#define MAXLENGTH 1000#include <>#include <>void compute(char *a, char

4、 *b, char *c);void main(void)(char alMAXLENGTH, bMAXLENGTH, cMAXLENGTH * 2;puts(Mlnput multiplier :n);gets(a);puts(Mlnput multiplicand :”)； gets(b);compute(a, b, c);puts(MAnswer :n);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(

5、b) -1;for (i = m; i >= 0; i-)ai -= 'O'；for (i = n; i >= 0; i-)bi -= 'O'cm + n + 2 = l0l;carry = 0;for (i = m + n; i >= 0; i-) /* i 為坐標(biāo)和 */sum = carry;if (O = i-m)<0)j = 0;for (; j<=i &&j<=n; j+) /* j 為縱坐標(biāo) */sum += ai-j * bj；/* 累計(jì)一組數(shù)的和 7ci + 1 = sum % 10 + &#

6、39;O' /* 算出保留的數(shù)字 */carry = sum /10;/* 算出進(jìn)位 */)if «c0 = carry+'O') = '0') /* if no carry, */c0 = '040' /* c0 equals to space */)效率分析：用以上算法計(jì)算m位整數(shù)乘以n位整數(shù)，需要先進(jìn)行mxn次乘法運(yùn)算，再進(jìn)行約 m + n次加法運(yùn)算和m + n次取模運(yùn)算(實(shí)為整數(shù)除法)。把這個(gè)程序稍加修改，讓它自己產(chǎn)生乘數(shù) 與被乘數(shù)，然后計(jì)算隨機(jī)的7200位整數(shù)互乘，在Cyrix 6x86 prl66機(jī)器的純DOS方式下

7、耗時(shí)7 秒(用Borland編譯)。經(jīng)過(guò)改進(jìn)，此算法效率可以提高約9倍。注意到以下事實(shí)：8216547x96785將兩數(shù)從個(gè)位起，每3位分為節(jié)，列出乘法表，將斜線(xiàn)間的 數(shù)字相加；8 216 54796 7858216547X76820736525129662501695604293957857682073652512625016956042939576827016222072429385將表中最后一行進(jìn)行如下處理：從個(gè)位數(shù)開(kāi)始，每一個(gè)方格里只保留三位數(shù)字，超出1000的部分進(jìn)位到前一個(gè)方格里;76827016222072429385768+2727016十222222072十429取395進(jìn)4

8、29=795=27238=222501395795238501395所以 8216547 x 96785 = 1395也就是說(shuō)我們?cè)谟?jì)算生成這個(gè)二維表時(shí)，不必一位一位地乘，而可以三位三位地乘；在累加時(shí)也 是滿(mǎn)1000進(jìn)位。這樣，我們?cè)谟?jì)算m位整數(shù)乘以n位整數(shù)，只需要進(jìn)行mxn/9次乘法運(yùn)算， 再進(jìn)行約(m + n)/3次加法運(yùn)算和(m + n)/3次取模運(yùn)算?？傮w看來(lái)，效率約是前一種算法的9 倍。有人可能會(huì)想：既然能夠三位三位地乘，為什么不4位4位甚至5位5位地乘呢那不是可以提 高16乃至25倍效率嗎聽(tīng)我解來(lái)：本算法在累加表中斜線(xiàn)間的數(shù)字時(shí)，如果用無(wú)符號(hào)長(zhǎng)整數(shù)(范 圍0至95)作為累加變量，在

9、最不利的情況下(兩個(gè)乘數(shù)的所有數(shù)字均是9),能夠累加約 95/(999*999)=4300次，也就是能夠準(zhǔn)確計(jì)算任意兩個(gè)均不超過(guò)12900(每次累加的結(jié)果,值11三 位，故4300*3=12900)位的整數(shù)相乘。如果4位4位地乘，在最不利的情況下,能夠累加約 95/(9999*9999)=43次，僅能夠確保任意兩個(gè)不超過(guò)172位的整數(shù)相乘，沒(méi)有什么實(shí)用價(jià)值，更 不要說(shuō)5位了。請(qǐng)看改進(jìn)后的算法的實(shí)例程序：該程序隨機(jī)產(chǎn)生兩個(gè)72xx位的整數(shù)，把乘數(shù)與積保存在中。在BorlandC"中用BCC -3 -02 -G -mh -Z -f287 -pr -T-編譯生成的exe文件在Cyrix 6

10、x86 prl66的機(jī)器上運(yùn)行耗時(shí)秒。 程序2清單：#include<>#include<>#include<>#include<>#include<>#define N 7200 作72xx位的整數(shù)乘法int max(int,int,int);int initarrayfint a);void write(int a,int I);FILE *fp;void main()(int a5000=0,b5000=0,k10001=0; 聲明存放乘數(shù)、被乘數(shù)與積的數(shù)組 clock_t start, end; 聲明用于計(jì)時(shí)的變量unsign

11、ed long c,d,e; 聲明作累力口用的無(wú)符號(hào)長(zhǎng)整數(shù)變量int聲明其它變量randomize。; /初始化隨機(jī)數(shù)la=initarray(a); 產(chǎn)生被乘數(shù),并返回其長(zhǎng)度lb=initarray(b); 產(chǎn)生乘數(shù)，并返回其長(zhǎng)度if(la<lb) 如果被乘數(shù)長(zhǎng)度小于乘數(shù)，則交換被乘數(shù)與乘數(shù) (p=(lb>la)lb:la;for (q=0；q<p；q+) 交換被乘數(shù)與乘數(shù)t=aq/aq=bq,bq=t;t=la,la=lbjb=t; 交換被乘數(shù)的長(zhǎng)度與乘數(shù)的長(zhǎng)度 )start = clock();開(kāi)始計(jì)時(shí)c=d=0;清空累加變量，其中CH于累加斜線(xiàn)間的數(shù)，d用作進(jìn)位標(biāo)志f

12、or(i=la+lb-2;i>=0;i-) 累加斜線(xiàn)間的數(shù)，i為橫縱坐標(biāo)之和 (c=d; 將前一位的進(jìn)位標(biāo)志存入累加變量cma=max(O,i-la+l,i-lb+l); 求累加的下限mi=(i>la-l)(la-l):i; 求累加的上限for(j=ma;j<=mi;j+) 計(jì)算出橫縱坐標(biāo)之和為i的單元內(nèi)的數(shù)，并累加到C中c+=(long)aj*bi-j;d=c/1000; 求進(jìn)位標(biāo)志if(c>999)c%=1000; 取c的末三位ki=c; 保存至表示乘積的數(shù)組k)e=k0+1000*d; 求出乘積的最高位end = clock();停止計(jì)時(shí)fp = fopenR ”

13、w+“); 保存結(jié)果到printf(HnThe elapsed time was: %nH, (end - start) / CLK_TCK);打印消耗的時(shí)間一fprintf(fpJ%d，aO);打印被乘數(shù)最高位write(aja); 打印被乘數(shù)其他位fprintf(fp,"%d，bO);打印乘數(shù)最高位write(bjb); 打印乘數(shù)其他位fprintf(fpj%ld”,e); 打印乘積最高位write(k,la+lb-l); 打印乘積其他位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;elsep=q/3+l;for(i=0;i<p;i+) ai=random(1000);if(q%3=0)a0=100+random(900);if(q%3=2)a0=10+random(90);if(q%3=l)a0=l+random(9);return p;) void write(int a,int I) int i;